Graph Representation: Adjacency List and Matrix

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.

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

      // Adjacency list representation in C++
// Author: Algorithm Tutor

// std::map has running time of O(log n) for dynamic set operations.
// use std::unordered_map if you want the constant time complexity

#include 
#include 
#include 

class Graph {
private:
    std::map<int, std::map<int, int> > graph;
public:
    void addEdge(int u, int v, int weight = 1, int isDirected = true) {
        std::map<int, std::map<int, int> >::iterator it;
        it = graph.find(u);
        if (it == graph.end()) {
            std::map<int, int> edge_map;
            edge_map[v] = weight;
            graph[u] = edge_map;

        } else {
            graph[u][v] = weight;
        }

        if (!isDirected) {
            it = graph.find(v);
            if (it == graph.end()) {
                std::map<int, int> edge_map;
                edge_map[u] = weight;
                graph[v] = edge_map;

            } else {
                graph[v][u] = weight;
            }
        }
    }

    void printGraph() {
        std::map<int, std::map<int, int> >::iterator it;
        std::map<int, int>::iterator it2;
        for (it = graph.begin(); it != graph.end(); ++it) {
            std::cout<first<<": ";
            for (it2 = it->second.begin(); it2 != it->second.end(); ++it2) {
                std::cout<<"("<first<<","<second<<")";
                std::cout<<"   ";
            }
            std::cout<<std::endl;
        }
    }
};

int main() {
    Graph g;
    g.addEdge(1, 2, 7, false);
    g.addEdge(1, 3, 2, false);
    g.addEdge(2, 3, 1, false);
    g.addEdge(2, 4, 5, false);
    g.addEdge(2, 5, 3, false);
    g.addEdge(3, 5, 11, false);
    g.addEdge(4, 5, 10, false);
    g.addEdge(4, 6, 7, false);
    g.addEdge(5, 6, 4, false);
    g.printGraph();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

// Adjacency list representation in Java
// Author: Algorithm Tutor

import java.util.Map;
import java.util.HashMap;
import java.util.Iterator;

class Graph {
    private HashMap> graph;

    public Graph() {
        graph = new HashMap<>();
    }

    public void addEdge(int u, int v, int weight, boolean isDirected) {
        if(graph.containsKey(u)) {
            HashMap edge_map = graph.get(u);
            edge_map.put(v, weight);
        } else {
            HashMap edge_map = new HashMap<>();
            edge_map.put(v, weight);
            graph.put(u, edge_map);
        }

        if (isDirected == false) {
            if(graph.containsKey(v)) {
            HashMap edge_map = graph.get(v);
            edge_map.put(u, weight);
            } else {
                HashMap edge_map = new HashMap<>();
                edge_map.put(u, weight);
                graph.put(v, edge_map);
            }
        }
    }

    @Override
    public String toString() {
        String to_return = "";
        Iterator it = graph.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry me = (Map.Entry)it.next();
            System.out.print(me.getKey() + ": ");
            HashMap value = (HashMap)me.getValue();
            Iterator it1 = value.entrySet().iterator();
            while (it1.hasNext()) {
                Map.Entry me1 = (Map.Entry) it1.next();
                System.out.print("(" + me1.getKey() + "," + me1.getValue() + ")");
                System.out.print("   ");
            }
            System.out.println();
        }
        return to_return;
    }

    public static void main(String [] args) {
        Graph g = new Graph();
        g.addEdge(1, 2, 7, false);
        g.addEdge(1, 3, 2, false);
        g.addEdge(2, 3, 1, false);
        g.addEdge(2, 4, 5, false);
        g.addEdge(2, 5, 3, false);
        g.addEdge(3, 5, 11, false);
        g.addEdge(4, 5, 10, false);
        g.addEdge(4, 6, 7, false);
        g.addEdge(5, 6, 4, false);
        System.out.println(g);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

  # adjacency list representation of a Graph in Python
# Author: Algorithm Tutor

import collections

class Graph:
    def __init__(self):
        self.graph = collections.defaultdict(dict)

    def add_edge(self, u, v, weight = 1, directed = True):
        self.graph[u][v] = weight
        if not directed:
            self.graph[v][u] = weight

    def __str__(self):
        to_return = ''
        for vertex in self.graph:
            to_return += str(vertex) + ': '
            for edge in self.graph[vertex]:
                to_return +=  '(' + str(edge) + ', ' + str(self.graph[vertex][edge]) + ')'
                to_return += '   '

            to_return += '\n'
        return to_return

if __name__ == '__main__':
    g = Graph()
    g.add_edge(1, 2, 7, False)
    g.add_edge(1, 3, 2, False)
    g.add_edge(2, 3, 1, False)
    g.add_edge(2, 4, 5, False)
    g.add_edge(2, 5, 3, False)
    g.add_edge(3, 5, 11, False)
    g.add_edge(4, 5, 10, False)
    g.add_edge(4, 6, 7, False)
    g.add_edge(5, 6, 4, False)
    print g

References

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (n.d.). Introduction to algorithms (3rd ed.). The MIT Press.
2. Jeff Erickson. Algorithms (Prepublication draft). http://algorithms.wtf
3. Steven S. Skiena. 2008. The Algorithm Design Manual (2nd ed.). Springer Publishing Company, Incorporated.