Implementation Of DFS Using Adjacency Matrix

Harsh Goyal
Last Updated: May 13, 2022
Difficulty Level :
EASY

Introduction

This blog will discuss the implementation of DFS using an adjacency matrix. Before jumping on the approach, let’s first understand the Adjacency matrix,

The Adjacency matrix is a simple integral matrix of size ‘V * V’, where ‘V’ represents the number of vertices in the graph. Basically, it is the representation of the graph in matrix form where the index of row and column represents the vertex, and the value at index [row][column] in adjacency matrix states whether there exists an edge between the two vertices same as the value of row and column.

In this problem, we need to print all the vertices while traversing the whole graph using the DFS algorithm. 

 

For Example:

Graph as Matrix: 
0 1 1 0 1 0 0
1 0 1 1 0 0 0
1 1 0 1 0 1 1   
0 1 1 0 0 0 0 
1 0 0 0 0 1 0
0 0 1 0 0 1 0
0 0 1 0 0 0 0

 

Output:

0

1

2

3

5

4

6

 

 

 

Explanation:

In this above-given graph, we can see that there are no disconnected components in the graph, and while starting from 0, we shift to 1, then after checking the adjacency matrix each time, we shift to 2, then we shift to 3. Now while checking for 3, we got to know that all the vertices that are directly connected to 3 are already visited, so we backtracked to vertex 2, now we’ll check for other connected edges with 2. In this, we shift to 5 and check for the vertices connected with 5, and we, therefore, shift to 4. Now at 4, we again found the same that no vertex is left not visited that are directly connected to 4. So we again backtracked to 5, now we again found the same and backtracked to 2, and got to know that 6 is still left, so we visit 6. In this way, we traversed the whole graph using DFS. 

Approach 

This approach considers traversing the complete graph using the Depth First Search algorithm, in which we use recursive calls to complete the task. In this implementation, we need to create an array of integers globally that will keep track of all the visited vertices, and we need to implement an adjacency matrix that will represent the edge between two vertices. In this implementation, we need to make an iteration using the ‘for’ loop, which will call the ‘get_Result’ function for all the components of the graph, whether it’s a disconnected or connected graph. If in the iteration, if the value at index ‘i’ in the ‘visited’ vector, then it means that it is the disconnected component and needs to be traversed.

Steps of algorithm

Step 1. In the ‘main()’ function, initialize an adjacency matrix ‘adj’ with zero of size ‘V * V’, where this ‘V’ is the number of vertices in the graph.

Step 2. Store all the edges data in two arrays, ‘a’ and ‘b’, where vertices on ‘ith’ index of both ‘a’ and ‘b’ represent an edge between both the vertices, and mark the element at index same as the pair of vertices as 1, representing that an edge exists between these two vertices.

Step 3. Print the adjacency matrix. 

Step 4. Initialize a global array of integers ‘visited’ to keep track of already visited vertex with zero, representing that the vertex is not visited.

Step 5. Make an iteration using the ‘for’ loop to cover the disconnected component of the graph. If the value at ‘ith’ index of ‘visited’ vector is 0, representing that the vertex is not visited, then make a call to ‘get_result()’ function, passing 4 parameters:- first one is the number of vertices ‘V’, the second one is the adjacency matrix ‘adj’, and third is the vertex ‘i’ from which we need to traverse.

Step 6. In the ‘get_result()’ function, print the vertex ‘x’ received along with marking it as visited in the ‘visited’ array, and then make an iteration using ‘for’ loop using a variable ‘i’ to check all the edges, in this, if the value of ‘i’ is equal to ‘x’ then we need to continue, and if the edge exists between the ‘x’ vertex and ‘ith’ vertex and the ‘ith’ vertex is still not visited, then make a recursive call to ‘get_result()’ function, passing ‘i’ as the vertex to be traversed.

Note:- Initialize the size of the global ‘visited’ array according to the number of vertices in the graph.

Implementation in C

#include <stdio.h>

// Array to keep the track of all the visited vertices
int visited[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

void get_result(int v, int adj[][v], int x)
{
 // print the current vertex
 printf("%d, ", x);

 // Mark the current vertex as visited
 visited[x] = 1;
 
 for(int i = 0; i < v; i++)
 {
     if(i == x)
     {
         continue;
     }
   
     // If there exists an edge between both the vertices and the other vertex is still not visited
     if(adj[x][i] && !visited[i])
     {
        get_result(v, adj, i);
     }
 }
 return;
}
int main()
{
 // V represents the number of vertices in the graph and e represents the number of edges in the graph
 int v = 10 , e = 11;

 // Adjacency matrix
 int adj[v][v];
 for(int i = 0 ; i < v ; i++)
 {
     for(int j = 0 ; j < v; j++)
     {
         adj[i][j] = 0;
     }
 }

 // Describes edge between both the vertices of a and b array
 int a[] = {0, 0, 0, 1, 1, 2, 2, 2, 4, 7, 9};

 int b[] = {1, 2, 4, 2, 3, 3, 5, 6, 5, 9, 8};

 // Mark the edge in the adjacency matrix
 for(int i = 0 ; i < e ; i++)
 {
     adj[a[i]][b[i]] = 1;
     adj[b[i]][a[i]] = 1;
 }

 printf("Adjacency matrix of the above mentioned graph is as follows:- \n");
 for(int i = 0; i < v ; i++)
 {
     for(int j = 0 ; j < v; j++)
     {
         printf("%d ", adj[i][j]);
     }
     printf("\n");
 }
 printf("\n");
 printf("DFS using an adjacency matrix of the above graph gives following order:- ");
 printf("\n");

 // Check for all the disconnected components
 for(int i = 0 ; i < v ; i++)
 {
     if(!visited[i])
     {
         get_result(v, adj, i);
     }
 }
}

 

Input:

 

Output:

Adjacency matrix of the above mentioned graph is as follows:- 
0 1 1 0 1 0 0 0 0 0 
1 0 1 1 0 0 0 0 0 0 
1 1 0 1 0 1 1 0 0 0 
0 1 1 0 0 0 0 0 0 0 
1 0 0 0 0 1 0 0 0 0 
0 0 1 0 1 0 0 0 0 0 
0 0 1 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 1 1 0 


DFS using an adjacency matrix of the above graph gives following order:- 
0, 1, 2, 3, 5, 4, 6, 7, 9, 8,

Complexity Analysis

Time Complexity for DFS using an adjacency matrix: O(V ^ 2)

Incall to ‘getResult()’, we are checking the whole adjacency matrix in the iterations, and the size of the adjacency matrix is ‘V ^ 2’, therefore, the overall time complexity is O(V * 2), where ‘V’ is the number of the vertices.

Space Complexity for DFS using an adjacency matrix: O(V ^ 2)

As we are implementing DFS using adjacency matrix of size ‘V ^ 2’, where ‘V’ is the number of vertices, therefore, the overall space complexity will be O(V ^ 2).

Frequently Asked Questions

  1. What is the DFS traversal?
    The DFS refers to Depth First Search. In this type of traversal, we use recursion to traverse the graph. We start from a node in this traversal and go as far as possible before backtracking.
     
  2. Why are the alternates of the adjacency matrix?
    We can use Adjacency List to store the edges. In the adjacency list, we store the vertices directly connected to the ‘ith’ vertex in the ‘ith’ vertex list.
     
  3. What is the computational time of the implementation of DFS using the adjacency list?
    The computational time of the implementation of DFS using the adjacency list is ‘V + E’, where this ‘V’ is the number of vertices and ‘E’ is the number of edges.

Conclusion

In this article, we discussed the implementation of DFS using an adjacency matrix and the approach to solve this problem programmatically. 

If you think that this blog helped you share it with your friends!. Refer to the DSA C++ course for more information.

Until then, all the best for your future endeavors, and Keep Coding.

Was this article helpful ?
0 upvotes