1.6. Data Structures to Represent Graphs

So, again I am explaining in the context of undirected graphs, but you can easily generalize this data structure to represent directed graphs as well, so we have what we call as the adjacency matrix representation, so this is a boolean matrix.

So, if your graph G is consisting of vertex set V and edge set E and if the cardinality of the vertex set is n, then this matrix is an n x n boolean matrix and the (i, j)th entry is 1 if (i, j) is in E, and 0 otherwise. And this representation is preferred for dense graphs. What do we mean by dense graph? A graph which has a lot of edges, that means it is not the case that you have very few edges, that means you have lots of edges in the graph in which case a majority of the entries in your matrix will be 1.

An adjacency matrix is a square matrix used to represent a graph, where each entry in the matrix indicates whether a pair of vertices is connected by an edge. If there are 'n' vertices in the graph, the adjacency matrix has dimensions n x n. Each cell (i, j) of the matrix will be '1' if there is an edge between vertex i and vertex j, and '0' if there is no edge. This structure is ideal for dense graphs, which have many edges because a high proportion of matrix entries will be non-zero (1). In such graphs, this representation allows quick access to check for the existence of edges between any two vertices.

Think of an adjacency matrix like a seating chart in a restaurant where each table can accommodate a certain pair of guests. If two guests are at a table together, you mark that seat as full (1); if there is an empty table, you mark it as zero (0). In a busy restaurant where most tables are occupied (a dense graph), it makes sense to use a seating chart (adjacency matrix) to quickly check if two guests at different tables are connected.

Whereas a sparse graph is a graph which has lots of vertices but very few edges, for such a graph the adjacency list is the preferred data structure for representation of the graph. So, what is this adjacency list? So, it is a collection of linked lists, each link is basically a collection of n linked lists, so you will have the first linked list with v as the starting node, second linked list as with v1 as the starting node and nth linked list with vn as the starting node and in v you will now link all the nodes which are incident. You link all the nodes which are the endpoints of an edge with v as its one of the endpoints.

An adjacency list is an efficient way to represent sparse graphs. This structure consists of an array or a list of lists. Each list at index i contains the nodes that are directly connected to vertex i. This means if vertex i is connected to vertices j and k, the list at index i will store j and k. This approach is efficient for graphs with many vertices but few edges, as it uses less space than an adjacency matrix, especially when the number of edges is significantly less than the number of vertices squared.

Imagine a social network where people represent vertices and friendships represent edges. Instead of using a huge grid (like an adjacency matrix) to represent every possible connection (including non-existing ones), you could simply maintain a list for each person that shows only their friends. Thus, if Alice has friends Bob and Charlie, her list would reflect just those two names, making it easier to see and manage actual connections.

So, what is this incidence matrix? It is so again I am explaining, assuming an undirected graph, so this will be a matrix with |V| x |E|. And it basically represents the relationship between the edge and its endpoint. So, what it means is the following if you have an edge e = (u, v) then the entry number (u, e) = 1 and (v, e) = 1, otherwise and the remaining entries will be 0.

The incidence matrix is another way of representing graphs. It is a matrix where rows correspond to vertices and columns correspond to edges. For an edge connecting vertices u and v, the matrix will have '1' in the positions corresponding to u and v (the row entries) under the column of that edge, while all other positions remain '0'. This is particularly useful for analyzing the relationship between vertices and edges more directly.

Consider an airport where the rows are different terminals (vertices) and the columns are flights (edges). If a flight departs from Terminal A to Terminal B, the entry in the incidence matrix corresponding to those terminals and that flight would be marked (1s indicating the flight service). This setup efficiently shows which terminals are linked by which flights.

--