Graph Adjacency Matrix

In this article, we will learn what an adjacency matrix is, its properties, how to represent undirected and directed graphs in an Adjacency Matrix, and some advantages and disadvantages of using an Adjacency Matrix.

Definition of Adjacency Matrix

In graph theory, an adjacency matrix is a way of describing the graph data structure. The two-dimensional matrix is used to map the relationship between the graph nodes.

If a graph has m number of vertices, then the adjacency matrix of that graph is m x m, and each matrix entry represents the number of edges from one vertex to another.

There is another name for Adjacency Matrix, which is called Connection Matrix. In some places, the adjacency matrix is referred to as the vertex matrix.

An adjacency matrix is a matrix of booleans (0’s and 1’s), where the boolean value of the matrix indicates if there is a direct path between two vertices.

For example, we have a graph below:

Now matrix representation of the above graph is like the one below:

Each cell in the above matrix is represented as A[i][j], where i and j are vertices. The value of A[i][j] is either 1 or 0 depending on whether there is an edge from vertex i to vertex j.

If there is an edge from i to j, then the value of A[i][j] is 1 otherwise it’s 0. For instance, there is an edge from vertex 1 to vertex 4, so A[1][4] is 1, and since our graph is undirected, the value of A[4][1] is also 1. No edge from vertex 1 to 3, so A[1][3] is 0.

Properties of Adjacency Matrix

Some of the properties of the adjacency matrix are mentioned as follows:

• An adjacency matrix is a matrix that contains rows and columns which represent a graph with the numbers 0 and 1 in the position of A[i][j], according to the condition of whether or not the two vertexes i ­and j are adjacent.
• For a directed graph, if there is an edge that exists between vertex i to Vertex j, then the value of A[i][j] = 1, otherwise the value will be 0.
• For an undirected graph, if there is an edge that exists between vertex i and Vertex j, then the value of A[i][j] = 1 and A[j][i] = 1, otherwise, the value will be 0.

Now, let’s see the matrix representation for undirected and directed graphs.

Adjacency Matrix for Undirected Graph

In an undirected graph, edges are not related to the directions. In an undirected graph, if an edge exists between Vertex i and Vertex j, then the vertices can be transferred from i to j as well as j to i.

Let us consider an undirected graph and try to generate its adjacency matrix.

In the above graph, no self-loop is present, so the diagonal entries of the adjacency matrix will be 0. The adjacency matrix of the above-undirected graph will be –

Adjacency Matrix for a Directed Graph

In a directed graph, edges represent a specific path from some vertex A to another vertex B. Vertex A is called the initial node, while Vertex B is called the terminal node.

Let us consider a directed graph and try to build its adjacency matrix:

In the above graph, no self-loop is present, so the diagonal entries of the adjacency matrix will be 0. The adjacency matrix of the above-directed graph will be –

Pros of using Adjacency Matrix

The adjacency matrix has several advantages for representing graph data:-

1. Space efficiency: Adjacency matrices use a fixed amount of space, regardless of the number of edges in the graph. This makes them well suited for dense graphs, where the number of edges is close to the maximum possible.
2. Constant time edge lookup: Adjacency matrices allow for constant time lookup of whether an edge exists between two vertices, making them efficient for graphs where edges are queried frequently.
3. Simple to implement: Adjacency matrices are easy to implement and understand, making them a popular choice for beginners learning about graph data structures.
4. Simple to traverse: Adjacency matrices can be easily traversed using simple loops, making them suitable for simple graph algorithms.
5. Directly related to the matrix algebra: Some graph problems can be represented in a matrix algebraic way, this direct relation makes it easier to solve the problem by using matrix operations.
6. easy to implement parallel algorithms.

Cons of using Adjacency Matrix

1. Adjacency matrix requires V x V space which makes its memory hog.
2. Graphs usually don’t have too many connections and this is the primary reason why adjacency lists are preferred over Adjacency Matrix for most tasks.
3. Graph traversal algorithms like DFS/BFS requires O(V^2) time in the case of an adjacency matrix whereas we can traverse the graph in O(V+E) time using an adjacency list.

When to use Adjacency Matrix?

1. If the graph contains edges in order of O(V^2), then it is better to use an adjacency matrix in comparison to an adjacency list. This is because the size of both the adjacency list and adjacency matrix will be comparable so using the adjacency matrix doesn’t necessarily waste a lot of memory.
2. If we want to perform operations like addition or deletion or checking if the vertices are adjacent or not, very frequently, then it is recommended to use an adjacency matrix since we can perform these operations in constant time.

Applications of Adjacency Matrix

1. For the creation of a routing table in networks.
2. For Navigation purposes.