Algorithms for Coding Interviews in C++/

...

/

Solution: Depth First Graph Traversal

Solution: Depth First Graph Traversal

In this review, we learn how to write code for the Depth-First Traversal of a Graph

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.

Press + to interact
main.cpp
Graph.cpp
Graph.h
#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 ...

Access this course and 1400+ top-rated courses and projects.