What is an adjacency matrix?

An adjacency matrix is a square matrix that represents a finite graph. The matrix denotes whether a particular pair of nodes in a graph is adjacent or not. In brief, an adjacency matrix is an array of size N x N, where N is the number of vertices in the graph. The adjacency matrix can be used to represent a directed graph, undirected graph or a weighted graph.

An adjacency matrix is referred to as a connection matrix or vertex matrix.

Representation of adjacency matrix

Assume an undirected graph G having N vertices. Use the following rules to represent this graph by using an n x n adjacency matrix A = [a_ij].

a_ij = 1 {if there exists a path from the vertex V_i to V_j }

a_ij = 0 {Otherwise}

Important points regarding adjacency matrix:

• a_ij = 1, where i is row, and j is a column and if an edge between vertices V_i and V_j exists. 
• If no edge is present between vertices V_i and V_j, then a_ij = 0.
• If no self-loops exist in a simple graph, the adjacency matrix will have 0 in the diagonal.
• In an undirected graph, the value in the i^th row and j^th column will be equal to the value in the j^th row and i^th column. The adjacency matrix will be symmetric for such undirected graphs.
• If an adjacency matrix is multiplied by itself, and the i^th row and j^th column have a non-zero value, then there exists a path from V_i to V_j with a length of 2. (The non-zero value shows the number of distinct paths.)
• If an adjacency matrix has a zero value, there is no connection between the two nodes. Similarly, if it has a non-zero (positive) value, the nodes have a connection.

Variations of an adjacency matrix

The conventions of representing an adjacency matrix of undirected, directed, and weighted graphs are different.

Adjacency matrix representation for undirected graph

An undirected graph is one in which the edges don’t have any directions. If an edge exists from vertex A to vertex B, the vertices can be traversed from A to B or from B to A.

The adjacency matrix representation for an undirected graph is explained using an example.

Consider the undirected graph below.

Now, construct the adjacency matrix for the graph.

The graph does not contain any self-loop, so the values in the diagonal will be zero. The remaining values will be represented in the matrix as follows:

Adjacency matrix representation for directed graph

A directed graph is the one in which the edges form an ordered pair. These edges indicate a path from one node, say node A to a different node, say node B. Here, the node from which the edge begins (node A in this case) is the initial node, whereas the node where the edge ends (node B in this case) is the terminal node.

Refer to the example below to understand the adjacency matrix representation for a directed graph.

Now, construct the adjacency matrix for this graph.

The graph does not have self-loops, so the values in the diagonal will be zero. The rest of the values will be represented in the matrix as follows:

Adjacency matrix representation for weighted graph

In a weighted graph, every edge is given a positive number. The number indicates the weight of the edge. The graph can be directed or undirected. The weights (numbers) on the edges are represented as the entries in the adjacency matrix.

Consider the following weighted directed graph.

This graph does not contain self-loops, so the values in the diagonal will be zero. Now, the adjacency matrix for this weighted graph will be as given below.

The adjacency matrix consists of rows and columns representing a labeled graph with 0s and 1s in the position of V_i and V_j, depending on the adjacency.

• For an undirected graph, the adjacency matrix is symmetric.
• In a directed graph, if an edge is present between vertex i (V_i) to vertex j (V_j), then in the adjacency matrix C, C[V_i][V_j] = 1. Otherwise, it will be 0.
• In an undirected graph, if there is an edge between vertex i (V_i) to vertex j (V_j), then C[V_i][V_j] and C[V_j][V_i] = 1. Otherwise, it will be 0.

Advantages of an adjacency matrix

• Adjacency matrix makes it easier to implement and track the relation between two edges. Operations like removing an edge, adding an edge, or the existence of an edge between two nodes take O(1) time.
• If the graph has multiple edges (dense graph), representing it using an adjacency matrix must be preferred. Likewise, sparse graphs can also be expressed using an adjacency matrix easily.
• We can learn about the nature of the graph, the relationship between the vertices, and so forth with its adjacency matrix.

Disadvantages of an adjacency matrix

• Due to the requirement of V x V representation, the memory consumed to represent a graph using adjacency matrix representation is higher than adjacency list representation.
• Adjacency matrix uses algorithms like depth-first search and breadth-first search for traversing through a graph. The time complexity of these algorithms is O(V²) which is higher than that of the adjacency list which has a time complexity of O(V+E).
• Consider a graph G (V, E) having n vertices, represented using an adjacency matrix a[i][j]. To implement the operations inEdge and outEdge all the entries n, of the corresponding row or column of matrix a[i][j] will have to be scanned. The operations will return the following output:
  • inEdge: It will scan over the vertex j to verify if an edge (i, j) exists. If there is an edge, it will return a list of all integers j where $(j, i) ϵ E$.
  • outEdge: It will work similar to inEdge, but will return a list of all integers j where $(j, i) ϵ E$.

Since all the entries of the matrix need to be scanned during these operations, they take O(n) time for every operation. As a result, they consume more time and memory. Hence, an adjacency matrix is not recommended for operations like inEdges and outEdges.

Context and Applications

• Masters in Computer Application
• Bachelors in Computer Application

Practice Problems

1. How many elements will be there in an adjacency matrix consisting of 7 vertices?

1. 7
2. 21
3. 49
4. 35

Correct option- c

Explanation: An adjacency matrix contains N x N elements. Therefore, if the graph has N vertices, the number of elements will be N². In this case, it will be 7x7 = 49.

2. Which of the following is a disadvantage of using an adjacency matrix representation?

1. It depends on the number of traversal edges.
2. It depends on the number of asymptotic vertices.
3. It uses less memory and cannot be used for operations like void addEdge.
4. It consumes more memory and time.

Correct option- d

Explanation: Adjacency matrix representation requires VxV representation. Hence, they consume more memory space and time.

3. What will be the order of the adjacency matrix for a graph having n nodes and m edges?

1. n x m
2. n x n
3. m x m
4. n x 2m

Correct option- b

Explanation: Adjacency matrix of a graph having n nodes contains n x n elements. If the value of A[i][j] = 1, then there is a relation between the two nodes. Otherwise, it has no relation. Here, the number of nodes is n, and the edges are m. Therefore, the order of the adjacency matrix will be n x n.

4. If a graph is represented in the form of an adjacency matrix, what will be the time complexity to calculate the number of edges?

1. O(V²)
2. O(V)
3. O(E²)
4. O(E)

Correct option- a

Explanation: the V entries will be 0 in an adjacency matrix. Hence, the total number of entries to check will be V² - V = V².

5. What will be the space required to store an adjacency matrix of a graph having n vertices?

1. In order of int j n
2. In order of n/2
3. In order of a permutation of n log n
4. In order of n squared

Correct option- d

Explanation: An adjacency matrix for a graph with n vertices contains n x n elements. So, the representation of the adjacency matrix is in order of n squared.

Common Mistakes

• Not understanding the difference between a weighted directed graph and weighted undirected graph.
• Misinterpretation of the direction of the edges in a directed graph.

Related Concepts

• Graph data structure
• Graph representations
• Bipartite graph
• Data structures and algorithms in Kotlin
• Adjacency list
• Topological sorting
• Depth First Search (DFS) for a graph
• Breadth-First Search (BFS) for a graph