DFS Graph Traversal by Recursion

June 27, 2023

What is DFS?

 

Depth First Search or in short DFS is an algorithm to traverse the graph by exploring its nodes in a depth ward way. It is like going to the extreme way possible each time, and if you can not go farther, returning to the node you started from and trying to explore further, until all the nodes are visited. Here We will see how we can perform DFS Traversal using a recursive function.

DFS Graph Traversal by Recursion | PrepInsta

DFS Graph Traversal using Adjacency list

If we represent the graph by Adjacency list, we have two ways to traverse the whole graph. Either we can reach all the nodes recursively, or we can use a stack data structure to keep track all the last visited node. Recursion does use the stack, as functions are called by stack memory which operates the same way a stack data structure does.

Prerequisites: Graph Representation by Adjacency list

DFS Graph Traversal by Recursion

Here we are about to write a function to do these following things;

  • Starting from the node we want to start traversing (Lets say i-th node)
  • Putting the i-th node in the argument.
  • Marking the i-th as node visited.
  • Defining the function that goes to the next possible nodes from i-th node.
  • If cannot go farther, return.

 

Explanation

Let us say we have 6 nodes, and they are 0,1,2,3,4,5 respectively. And There are 7 edges, in between the following nodes : (1,2), (2,3), (1,0), (1,5), (5,2), (5,4), (0,3). So,

  • Starting traversal from node 0.
  • from node 0,  we can directly visit the nodes namely 1 and 3. So calls the function with 1 and 3 in arguments respectively.
  • from node 1,  we can directly visit the nodes namely 0, 2, 5, but the 0 is visited. So it recursively calls for the rests, and so on.

 

The code to implement this:

#include<bits/stdc++.h>
using namespace std;
int *vis; // Declaring the array globally so that we can use it by any function and manipulate.
// Declaring it dynamically as we don’t know the number of vertices.
void dfs(int i, vector<int> *Adj) // The recursive function
{
    if(vis[i]) {return;} // If the node is visited, return
    vis[i]=1;
    cout<<“Visiting the node named “<<i<<endl;
    for(int j=0;j<Adj[i].size();j++) // tracking all the directly connected nodes through adjacency list
    dfs(Adj[i][j],Adj); // Recursion happening
}
void Addedges(int a,int b, vector<int> *Adj) // TO add two nodes
{
    Adj[a].push_back(b);
    Adj[b].push_back(a);
}
int main()
{
    int v=6; // Declaring number of vertices
    vector<int> Adj[v]; // Declaring the adjacency list
    Addedges(1,2,Adj); // Adding Edges
    Addedges(2,3,Adj);
    Addedges(1,0,Adj);
    Addedges(1,5,Adj);
    Addedges(5,2,Adj);
    Addedges(5,4,Adj);
    Addedges(0,3,Adj);
 
    vis = new int[v];
    for(int i=0;i<v;i++) // Marking all nodes as unvisited in the start
    vis[i]=0;
    dfs(0,Adj); //Calling the recursive function
}

Output :

Visiting the node named 0
Visiting the node named 1
Visiting the node named 2
Visiting the node named 3
Visiting the node named 5
Visiting the node named 4