Graphs Data Structures

Graphs

The graph is one of the most important data structures in computer science.

Definition:

A graph (defined as $G=(V, E)$)is simply a set of vertices(V) and edges(E; storing the connectivity information between vertices in V).

We will now discuss the three basic ways to represent a graph G with vertices V and edges E.

Adjacency Matrix:

If the number of vertices is known, we can build a connectivity table as a static 2d array: 

                                                                         \[arr[V][V]\] This will have $O(V^2)$ space complexity. For an unweighted graph. set arr[i][j] to one if there is an edge between vertex i-j or zero otherwise.

For a weighted graph, set it to the weight of the edge if there is an edge else zero in case there is no edge.

For a simple graph without self-loops, the main diagonal of the matrix contains only zeros.

An adjacency Matrix is a good choice if the connectivity between two vertices in a small dense graph is frequently required.

For a large sparse graph, not a good choice. It takes O(V) time to enumerate the list of neighbors of a vertex v. You would have to scan the complete row/column corresponding to that vertex.

Adjacency List:

In the adjacency list, we have a vector of vector of pairs. Defined as vector<vector<pair<int, int> > >.

It stores the list of neighbors of each vertex u as edge information pairs. Each pair contains two pieces of information, the index of the neighboring vertex and the weight of the edge.

The space complexity of the Adjacency List is O(V+E). As E is usually much smaller than $V^2$ adjacency list are much more space-efficient than Adjacency Matrix.

With Adjacency Lists, enumeration the list of neighbors of a vertex v. If v has k neighbors it will only require O(k) time.

This is suggested the first choice of graph representation.

The Edge List: 

Is usually in the form of a vector of triples vector< pair<int, pair<int, int> >.

In the edge list, we store a list of all E edges usually in some sorted order. For directed graphs, we can store a bi-directional edge twice, one for each direction.

The space complexity is O(E). Storing graph information in Edge List complicates many graph algorithms that require enumeration of edges incident to a vertex.