Recursion for Coding Interviews in C++/

...

/

Depth First Search in Graphs

Depth First Search in Graphs

This lesson will teach you how to write a recursive code for depth first search in graphs.

We'll cover the following...

Depth First Search is a way to traverse and search all nodes in a graph. This traversal algorithm works in such a way that it starts from the root node and then traverses all the way down that branch until it reaches the leaf, i.e., the last node with no other children, and then backtracks. This follows until all nodes are traversed. The illustration below shows a better understanding of DFS.

Implementing the Code

The code below shows how to do this with recursion. First, let’s see the code, then we can go on to its explanation.

Change the edges, the number of nodes n to create your own graphs, g, and run DFS on them for a better understanding.

Press + to interact
#include <iostream>
#include <vector>
using namespace std;
class edge{//This class is to create an edge between two nodes
  public:
  int src, dst;
  
  edge(){};
  edge(int s,int d){ // Constructor
    src=s;
    dst=d;
  }
  edge(const edge &e2){//Copy constructor for the edge class
    src = e2.src;
    dst = e2.dst;
  }
};
class graph{ //The graph class which creates the graph
private:
  int nodes;
  vector<edge> edges;
public:
  //Copy constructor for the graph
  graph(int n,vector<edge> e){ 
    nodes=n;
    for(int i=0;i<e.size();i++){
      edges.push_back(e[i]);
    }   
    
  }
  //The Depth First Search function
  void DFS(int v, vector<int>&visited)
  {
    
    if (visited[v]==1){return;}
    else
    {
      cout<<"current node: "<<v<<endl;
      visited[v]=2;
      for(int i=0;i<edges.size();i++)
      {
        if(edges[i].src==v)
        { int dest=edges[i].dst;
          if(visited[dest]==0)
         {
           DFS(dest,visited);
         }
        }
       }
    visited[v]=1;
    }
  }
};
int main() {
  edge one(0,1);
  edge two(0,2);
  edge three(1,3);
  edge four(1,4);
  edge five(2,5);
  
  vector<edge> e;
  e.push_back(one);
  e.push_back(two);
  e.push_back(three);
  e.push_back(four);
  e.push_back(five);
  
  int n=5;
  graph g(n,e);
  vector<int> visit={0,0,0,0,0};
  
  for(int i=0;i<n;i++){
    g.DFS(i,visit);
  }
}

Understanding the Code

The code above runs a Depth First Search on the graph created. The illustration below shows the graph that we use for the code snippet above and the result that the search should give.

The recursive code can be broken down into two parts. ...