**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.

- Make a visited array of size V where V=number of nodes present in the given graph.
- Make a stack and push any node in the stack.
- Run a while loop till the stack is not empty.
- Pop the element and print it if it is not visited.
- 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**

**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.

**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__.

**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!