In this article, we will explore on how to convert from adjacency list representation of a graph to adjacency matrix representation and vice versa.
What is an Adjacency List?
An adjacency list is a way of representing a graph, where each node is associated with a list of its neighboring nodes (the nodes it is connected to). This representation is often more efficient for sparse graphs, where each node has only a few connections.
For the same example graph above, the adjacency list would be:
A: [B]
B: [A, C]
C: [B, D]
D: [C]
Refer to this article for more information: Adjacency List representation of a Graph
What is an Adjacency Matrix?
An Adjacency Matrix is another way of representing a graph. It is a square matrix where the rows and columns represent the nodes of the graph, and the values in the matrix indicate whether there is an edge between the corresponding nodes.
For example, if we have the same graph as before, with nodes A, B, C, and D, and the edges (A, B), (B, C), and (C, D), the adjacency matrix would look like this:
A B C D
A 0 1 0 0
B 1 0 1 0
C 0 1 0 1
D 0 0 1 0
In this matrix, a value of 1 indicates that there is an edge between the corresponding row and column nodes, and a value of 0 indicates that there is no edge. This representation is more suitable for dense graphs where the number of edges are more.
Refer to this article for more information: Adjacency Matrix representation of a Graph
Example Graph Used For Conversion
For the examples below, a graph with the following nodes/vertices and edges is considered:
vertices = ['A', 'B', 'C', 'D', 'E', 'F']
edges = [['A','B'], ['A','C'], ['B','C'], ['B','D'], ['C','E'], ['C','F']]
In programmatic representation of a graph, each node or vertex is typically assigned a number between 0 and N-1, where N is the total number of nodes in the graph. This numbering is efficient in terms of storage and also allows us to use an array to represent the adjacency list or matrix, rather than a dictionary or hash table. This approach is more efficient because accessing elements in an array using the node ID/number as index is generally faster than accessing elements in a hash table or dictionary. Below is how the vertices and edges look like after optimizing the representation:
A B C D E F
vertices = [0, 1, 2, 3, 4, 5]
edges = [[0,1], [0,2], [1,2], [1,3], [2,4], [2,5]]
Converting from Adjacency List to Adjacency Matrix
To convert from an adjacency list to an adjacency matrix, we first initialize an N x N matrix with all elements set to 0, where N is the number of nodes. Then, we iterate through each node and its list of neighbors in the adjacency list. For each neighbor, we set the corresponding elements in the matrix to 1 (or the weight of the edge, if applicable).
Converting from Adjacency Matrix to Adjacency List
To convert from an adjacency matrix to an adjacency list, we initialize an array of size N with an empty list of neighbors for each node. Then, we iterate through each element in the N x N matrix. For each non-zero element at position [i, j], we add node j to the adjacency list of node i. In the code below, source variable refers to index i and destination variable refers to index j.