We have already discussed Depth first search on the link http://wikistack.com/depth-first-traversal-of-graph/. This link has pictorial representation of DFS using stack data structure. Here we are going to implement  recursive version of depth first search algorithm, however using stack for DFS is similar to using recursion but the implementation of recursive version is easier and it does not require stack data structure. Let us see an example graph.

A recursive implementation of DFSIn Depth first traversal of a graph , we visit the child node before visiting its sibling nodes. Visiting child nodes before its siblings nodes means , DFS explores its depth rather than breadth. For example Let us start visiting from node 0 , After reaching at 0 node look its immediate connected child nodes , child of 0 node is 1 and 2. In this case we visit any node either 1 or 2. Let us we have visited node 1. Each visited node is marked as visited node. This will help to track unvisited and visited node. Again after reaching at 1,  look at all its immediate connected nodes, which is 3 only, then visit the node 3 mark it visited. After reaching at node 3, again look at its immediate connected child nodes, which is 5, visit at 5. As we can see in above graph that there is no nodes which are connected from 5. In this case we have to backtrack the nodes to find out non visited nodes. This process will go until we visit all nodes in the graph.

Here is step summarized.

1 void DFS(graph,vertex):
2      mark v as visited
3      for all edges from v to u in graph.adjacentEdges(v) do
4          if vertex u is not visited then
5              call DFS(graph,u)
#include<iostream>
#include<stdio.h>
#include <cstdlib>
#include <cstring>
using namespace std;
int count = 0;

void dfs (int u, bool visited[], bool graph[][6])
{

  visited[u] = true;
  // print u
  cout<<u<<"  ";

  for (int v = 0; v < 6; v++)
    if (!visited[v] && graph[u][v])
      dfs (v, visited, graph);
}

int main ()
{
  bool visited[6];
  memset(visited,false,sizeof(visited));

                     //0  1  2  3  4  5
  bool graph[6][6] = {{0, 1, 1, 0, 0, 0}, //0
                      {0, 0, 1, 1, 0, 0}, //1
                      {0, 0, 0, 1, 0, 0}, //2
                      {0, 0, 0, 0, 0, 1}, //3
                      {0, 0, 1, 0, 0, 0}, //4
                      {0, 0, 0, 0, 0, 0}};//5
  

  for (int v = 0; v < 6; v++)
    if (!visited[v])
      dfs (v, visited, graph);
  cout<<endl;
  return 0;
}

Output:
0 1 2 3 5 4



Related Contents to follow