Depth First Search (DFS) Traversal of a Graph

Approach

Since we will be traversing the graph iteratively, we will replace the recursive stack with a stack of nodes. Rest all things will be similar to the recursive approach only.

1. Make a visited array of size V where V=number of nodes present in the given graph.
2. Make a stack and push any node in the stack.
3. Run a while loop till the stack is not empty.
   1. Pop the element and print it if it is not visited.
   2. If the node was unvisited, mark it as visited and push all the unvisited neighbors of this node to the stack.

Note - Since a graph can be disconnected too, we must perform the above steps for every component. 

Code Implementation

#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
void dfs(vector<bool>& visited,int i,vector<int> adjList[]){
	stack<int> s;
    s.push(i);
    while(!s.empty()){
	    int front = s.top();
	    s.pop();
	    if(visited[front]==false){
	    	visited[front] = true;
	    	cout<<front<<" ";
	    	for(int j=(adjList[front].size()-1);j>=0;j--){
	    		int neighbour = adjList[front][j];
	    		if(visited[neighbour]==false){
	    			// push it into the stack
	    			s.push(neighbour);
	            }
	        }
	    }
	}
}

void printDFS(int V, vector<int> adjList[]) {
    vector<bool> visited(V+1, false);
    for(int i=1;i<=V;i++){
        if(visited[i]==false){
            // do DFS from this node iteratively.
            dfs(visited,i,adjList);
        }
    }
}

void addEdge(vector<int> adjList[],int i,int j){
	adjList[i].push_back(j);
	adjList[j].push_back(i);
}


int main(){

	// 6 --- 4 --- 5 \
	// 	     |	   |  1
	// 	     |     | /
	//       3 --- 2 

	int V = 6;
	vector<int> adjList[V+1];

	// Inputing this graph
	addEdge(adjList,6,4);
	addEdge(adjList,4,3);
	addEdge(adjList,4,5);
	addEdge(adjList,5,2);
	addEdge(adjList,2,3);
	addEdge(adjList,1,2);
	addEdge(adjList,1,5);

	printDFS(V,adjList);
}

You can also try this code with Online C++ Compiler

Run Code

Output

1 2 5 4 6 3 

Time Complexity 

Since we visit all the nodes once and for every node, we traverse all its neighbours, T(n) = O(V+E), where V is the total number of vertices and E is the number of edges in the graph. 
 

Space Complexity 

Since we are making an extra array to store the visited vertex, the space complexity contributed by this array is O(V), where V is the number of vertices in the graph. 
We are also making an extra stack to traverse it. But since in the worst case, too, it can have only V vertices, therefore overall space complexity is O(V).

Frequently Asked Questions

1. What is the difference between a tree and a graph?
   Trees and graphs are different since there can never be loops in a tree, but we can have loops in a graph. Also, all the nodes in a tree are always connected, but that is not true for a graph.
    
2. What is the difference between a DFS Traversal and a BFS Traversal?
   In a DFS traversal of a graph, we begin from any random node and travel down each branch as far as feasible before returning to the current node. In contrast, in a BFS traversal, we visit each node before visiting their children nodes. 
   DFS Traversal is performed using a stack, whereas a BFS Traversal is performed using a queue.
    
3. Are there more Data Structures and Algorithms problems in Coding Ninjas Studio?
   Yes, Coding Ninjas Studio is a platform that provides both practice coding questions and commonly asked interview questions. The more we’ll practice, the better our chances are of getting into a dream company of ours.

Key Takeaways

This article taught us how to do a DFS traversal of a graph iteratively.

Since graphs and stacks are frequently asked in interviews, we recommend you practice more problems based on graphs and stack on Coding Ninjas Studio. 

Recommended problems -

• Zig Zag Tree Traversal 
• Preorder Traversal

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!