Depth First Search

Used to traverse a tree or a graph in depth first manner

// globally we have a Graph G of lets say 100 nodes
vector<int>* G = new vector<int>[100];
// globally we also have a vector to store weather or not a node has been visited
vector<bool> visited(100, false);


void DFS( int node ){
  // mark the current node as visited
  visited[node] = true;
  
  // for all the adjacent nodes of the current node
  for( int adj : G[node] ){
    // if the adjacent node is not already visited then visit it
    if( !visited[adj] )
      DFS( adj );
  } 
}

Fully Working Code Here

Applications:

• Traversal of Graph, explore Nodes and Edges of a Graph. code

• Used as a building block in other Algorithms:

  • Count Connected Components
  • Determine Connectivity
  • Find Bridges and Articulation Points in a Graph

• For a unweighted graph DFS traversal produces

  • Minimum Spanning Tree
  • All Pair Shortest Path

• Path Finding between two vertex

• Determine Cycle in a Graph

• To test if a graph is Bipartite

• Topological Sort