Posted on

Depth First Search (DFS)

Depth First Search / Depth First Traversal

Depth First Search technique first explores all possibly reachable nodes from a given starting node ‘s’ and then backtracks to the starting point.It can be implemented using recursion call stacks(implicit) or by external usage of stack data structure.We also maintain a boolean visited array to keep track of already visited nodes.

Depth First Search full explanation with code
/** This function ensures traversal in case of cycles in graph **/
void DFSfunc( vector<int>adj[] , int V )
{
     bool visited[V];
     memset(visited , false , sizeof(visited) );
     for( int i = 0 ; i < V ; i++ )
     {
          if( visited[i] == false )
               DFS( adj , i , visited );
     }
}


void DFS( vector<int> adj[] , int s , bool visited[] )
{
     visited[s] = true;
     cout << s <<" ";
     
     for( int x : adj[s] )
     {
          if( visited[x] == false )
               DFS( adj , x , visited );
     }
}

Applications of DFS:-

  • Cycle detection
  • Path finding problems
  • Solving mazes and other similar problems
  • Topological Sort

This article has been contributed by Prashant Singh Thakur

Write a comment