Introduction
In the previous post, we introduced the concept of graphs. In this post, we discuss how to store them inside the computer. There are two popular data structures we use to represent graph: (i) Adjacency List and (ii) Adjacency Matrix. Depending upon the application, we use either adjacency list or adjacency matrix but most of the time people prefer using adjacency list over adjacency matrix.
Adjacency Lists
Adjacency lists are the right data structure for most applications of graphs.
Adjacency lists, in simple words, are the array of linked lists. We create an array of vertices and each entry in the array has a corresponding linked list containing the neighbors. In other words, if a vertex 1 has neighbors 2, 3, 4, the array position corresponding the vertex 1 has a linked list of 2, 3, and 4. We can use other data structures besides a linked list to store neighbors. I personally prefer to use a hash table and I am using the hash table in my implementation. You can also use balanced binary search trees as well. To store the adjacency list, we need $O(V + E)$ space as we need to store every vertex and their neighbors (edges).
To find if a vertex has a neighbor, we need to go through the linked list of the vertex. This requires $O(1 + deg(V))$ time. If we use balanced binary search trees, it becomes $O(1 + \log(deg(V))$ and using appropriately constructed hash tables, the running time lowers to $O(1)$.
Figure 1 shows the linked list representation of a directed graph.
In an undirected graph, to store an edge between vertices $A$ and $B$, we need to store $B$ in $A$’s linked list and vice versa. Figure 2 depicts this.
Adjacency Matrices
An adjacency matrix is a $V \times V$ array. It is obvious that it requires $O(V^2)$ space regardless of a number of edges. The entry in the matrix will be either 0 or 1. If there is an edge between vertices $A$ and $B$, we set the value of the corresponding cell to 1 otherwise we simply put 0. Adjacency matrices are a good choice when the graph is dense since we need $O(V^2)$ space anyway. We can easily find whether two vertices are neighbors by simply looking at the matrix. This can be done in $O(1)$ time. Figure 1 and 2 show the adjacency matrix representation of a directed and undirected graph.
Representing Weighted Graphs
We can modify the previous adjacency lists and adjacency matrices to store the weights. In the adjacency list, instead of storing the only vertex, we can store a pair of numbers one vertex and other the weight. Similarly, in the adjacency matrix, instead of just storing 1 we can store the actual weight. Figure 3 illustrates this.
Comparison
The table below summarizes the operations and their running time in adjacency list and adjacency matrix.
Operation | Adjacency List (Linked List) | Adjacency List (Hash Table) | Adjacency Matrix |
---|---|---|---|
Test if $uv$ is an edge (directed) | $O(V)$ | $O(1)$ | $O(1)$ |
Test if $uv$ is an edge (undirected) | $O(V)$ | $O(1)$ | $O(1)$ |
List $v$’s neighbor | $O(V)$ | $O(V)$ | $O(V)$ |
List all edges | $O(V + E)$ | $O(V + E)$ | $O(V^2)$ |
Insert edge $uv$ | $O(1)$ | $O(1)$ | $O(1)$ |
Implementation
Since I will be doing all the graph related problem using adjacency list, I present here the implementation of adjacency list only. You can find the codes in C++, Java, and Python below.
1 | // Adjacency list representation in C++ |
1 | // Adjacency list representation in Java |
1 | # adjacency list representation of a Graph in Python |
References
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (n.d.). Introduction to algorithms (3rd ed.). The MIT Press.
- Jeff Erickson. Algorithms (Prepublication draft). http://algorithms.wtf
- Steven S. Skiena. 2008. The Algorithm Design Manual (2nd ed.). Springer Publishing Company, Incorporated.