An Adjacency matrix is a type of graph representation which uses a square matrix (two dimensional array of values) to indicate presence of edges. The row index correspond to the node from which an edge starts and column index correspond to node at which an edge ends, and the matrix elements indicate if there’s an edge for a given start and end node.
For example, if the value in the adjacency matrix at position [i][j] is 1/True, it indicates that there is an edge which starts at node i and ends at node j.
Representing an Un-Directed Graph Using Adjacency Matrix
Let’s consider the below graph and represent it using an adjacency matrix:
Below is the programmatic representation of the graph using adjacency matrix:
# Vertices in the graph
#. 0 1 2 3 4 5
vertices = ['A', 'B', 'C', 'D', 'E', 'F']
adjacency_matrix = [
[0, 1, 1, 0, 0, 0],
[1, 0, 1, 1, 0, 0],
[1, 1, 0, 0, 1, 1],
[0, 1, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0],
[0, 0, 1, 0, 0, 0]
]
Each node present in the graph is assigned with a 0 based ID. Next an adjacency matrix is declared where if there’s an edge between nodes 2 and 1 (Nodes C and B), the value mat[2][1] will be 1/True.
If there is no edge between two nodes, for example there is no node between C (id = 2) and D (id = 3), the corresponding entry in adjacency matrix is 0, so mat[2][3] is 0.
Also notice that the matrix is symmetric along the diagonal since the above graph is un-directed. If mat[i][j] is 1, mat[j][i] is also 1 and vice versa. But for a directed graph, the matrix is not symmetrical unless all the nodes have edges in both directions.
Representing a Directed Graph Using Adjacency Matrix
Let’s consider the directed graph shown below and represent it using an adjacency matrix:
This is the representation of the above graph using an adjacency matrix:
# Vertices in the graph
#. 0 1 2 3 4 5
vertices = ['A', 'B', 'C', 'D', 'E', 'F']
adjacency_matrix = [
[0, 1, 1, 0, 0, 0],
[0, 0, 1, 1, 0, 0],
[0, 1, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0]
]
Notice that there are no nodes which are reachable from nodes D, E, F and so all the values against their corresponding rows in the Adjacency Matrix are 0. This means there are no edges starting from those nodes.
Pros and Cons
With adjacency matrices, finding out if a particular edge is present or not is very fast as it involves directly accessing a corresponding entry in the matrix. However, getting the list of all edges from a particular node takes O(V) time complexity which is in-efficient for sparse graphs when each node is connected to very few elements.