Search⌘ K
Home
Courses
Algorithms for Coding Interviews in C++

Solution: Depth First Graph Traversal

Learn how to implement depth first graph traversal in C++ through detailed iterative and recursive solutions. Understand the backtracking approach, use of stacks, and recursion with clear pseudocode. This lesson explains the traversal process and its time complexity to help you master graph algorithms for coding interviews.

We'll cover the following...

Solution #1: Iterative

The Depth-First Graph algorithm uses the idea of backtracking. We exhaustively search all the nodes by going ahead, if possible, or else by backtracking.

Here, the word ‘backtrack’ means to move forward as long as there are no more nodes in the current path, then move backwards on the same path to find nodes to traverse.

In the following solution, we have used a stack to implement Depth-First Graph Traversal.

C++
#include "Graph.h"
void Graph::depthFirstTraversal(int source) { 
  vector<bool> visited(vertices, false); 
	stack<int> stack; 
	stack.push(source); 
	while (!stack.empty()) { 
		source = stack.top(); 
		stack.pop(); 
		if (!visited[source]) { 
			cout << source << " "; 
			visited[source] = true; 
		} 
		for (auto i = adjacencyList[source].begin(); i != adjacencyList[source].end(); ++i) 
			if (!visited[*i]) 
				stack.push(*i); 
	} 
} 
int main() 
{ 
	Graph g(6);
  g.addEdge(0,1);
  g.addEdge(1,2);
  g.addEdge(1,3);
  g.addEdge(2,4);
 	g.addEdge(3,4);
  g.addEdge(3,5); 
	g.depthFirstTraversal(0); 
	return 0; 
}

Psuedocode

Let’s have a look at the pseudocode of depth-first traversal, both iterative and recursive

Input: root is a node in the graph
Output: all nodes visited in breadth-first order

 DFS-iterative (G, s):                            //Where G is graph and s is source vertex
      let S be stack
      S.push(s)     //Insert s in stack 
      mark s as visited.
      while ( S is not empty):
          //Pop a vertex from stack to visit next
          v  =  S.top()
         S.pop( )
         //Push all the neighbours of v in stack that are not visited   
        for all neighbours w of v in Graph G:
            if w is not visited :
                     S.push( w )         
                    mark w as visited

Note: As for Breadth-First Traversal, before running the algorithm, all ...