Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
4.
Code in C++
4.1.
Output
4.2.
Time Complexity 
4.3.
Space Complexity 
5.
Frequently Asked Questions
6.
Key Takeaways
Last Updated: Mar 27, 2024

DFS Traversal of a Graph - Iteratively

Author Gaurish Anand
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

Before beginning with this question, let’s recap what a Depth First Traversal means. 

 

                    

Source

 

Depth First Traversal is an algorithm used to traverse a graph or a tree. DFS Algorithm is similar to a DFS traversal in a tree. But the main difference is in graphs, you can have cycles, but in trees, we can’t have them. 

So to do a DFS traversal in a graph, we begin from any random node and travel down each branch as far as feasible before returning to the current node. 

Since here we can have cycles, therefore we need to maintain a visited array too so that we can avoid an infinite loop. For further reference, you can go through this article.
Example: Depth First Traversal for the above graph is: 1 2 3 4 5 6 

Problem Statement

Perform the DFS Traversal on a graph iteratively.

Example: Output for the above tree will be - 

1 2 3 4 5 6  
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 in C++

#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);
}

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 -


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!

Previous article
Check if the given permutation is a valid BFS of a given tree
Next article
Depth First Search (DFS) Algorithm
Live masterclass