An adjacency matrix is a square matrix that is used to represent a graph. The rows and columns of the matrix are labeled as per the graph vertices. So, if the graph vertices are 1,2,...5, then the rows and columns of the adjacency matrix will be labeled as 1,2,...5. Initially, the matrix is filled with all zeros (0). Then, the 0 at the mat[i][j] location (where i and j refer to the vertices) is replaced by 1 if there is an edge between the vertices of i and j. For example, if there is an edge from vertex 2 to vertex 3, then at the mat[2][3] index location, the value of 0 will be replaced by 1. In short, the elements of the adjacency matrix indicate whether pairs of vertices are adjacent or not in the graph.
Consider the following directed graph:
Its adjacency matrix representation is as follows:
5,5 1 2 3 4 5
-----------------------------------------------------------------------------
1 0 1 1 0 0
2 0 0 0 0 0
3 0 0 0 1 1
4 0 1 0 0 1
5 1 1 0 0 0
The first row and the first column represent the vertices. If there is an edge between two vertices, then there will be a 1 value at the intersection of their respective row and column. The absence of an edge between them will be represented by 0. The number of nonzero elements of an adjacency matrix indicates the number of edges in a directed graph.
Here are two drawbacks of adjacency matrix representation:
- This representation requires n2 elements to represent a graph having n vertices. If a directed graph has e edges, then (n2-e) elements in the matrix would be zeros. Therefore, for graphs with a very low number of edges, the matrix becomes very sparse.
- Parallel edges cannot be represented by an adjacency matrix.
In this recipe, we will learn how to make an adjacency matrix representation of a directed graph.