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
Below is the implementation of the approach:
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]) {
visited[front] = true;
cout << front << " ";
for (int j = (adjList[front].size() - 1); j >= 0; j--) {
int neighbour = adjList[front][j];
if (!visited[neighbour]) {
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]) {
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() {
int V = 6;
vector<int> adjList[V + 1];
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
Java
import java.util.*;
public class GraphDFS {
static void dfs(List<List<Integer>> adjList, boolean[] visited, int start) {
Stack<Integer> stack = new Stack<>();
stack.push(start);
while (!stack.isEmpty()) {
int node = stack.pop();
if (!visited[node]) {
visited[node] = true;
System.out.print(node + " ");
List<Integer> neighbours = adjList.get(node);
for (int i = neighbours.size() - 1; i >= 0; i--) {
int neighbour = neighbours.get(i);
if (!visited[neighbour]) {
stack.push(neighbour);
}
}
}
}
}
static void printDFS(int V, List<List<Integer>> adjList) {
boolean[] visited = new boolean[V + 1];
for (int i = 1; i <= V; i++) {
if (!visited[i]) {
dfs(adjList, visited, i);
}
}
}
static void addEdge(List<List<Integer>> adjList, int u, int v) {
adjList.get(u).add(v);
adjList.get(v).add(u);
}
public static void main(String[] args) {
int V = 6;
List<List<Integer>> adjList = new ArrayList<>();
for (int i = 0; i <= V; i++) adjList.add(new ArrayList<>());
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 Java Compiler
Run Code
Python
def dfs(visited, graph, node):
stack = [node]
while stack:
current = stack.pop()
if not visited[current]:
visited[current] = True
print(current, end=" ")
for neighbor in reversed(graph[current]):
if not visited[neighbor]:
stack.append(neighbor)
def printDFS(V, graph):
visited = [False] * (V + 1)
for i in range(1, V + 1):
if not visited[i]:
dfs(visited, graph, i)
def add_edge(graph, u, v):
graph[u].append(v)
graph[v].append(u)
if __name__ == "__main__":
V = 6
graph = [[] for _ in range(V + 1)]
add_edge(graph, 6, 4)
add_edge(graph, 4, 3)
add_edge(graph, 4, 5)
add_edge(graph, 5, 2)
add_edge(graph, 2, 3)
add_edge(graph, 1, 2)
add_edge(graph, 1, 5)
printDFS(V, graph)

You can also try this code with Online Python Compiler
Run Code
JS
function dfs(graph, visited, start) {
let stack = [start];
while (stack.length > 0) {
let node = stack.pop();
if (!visited[node]) {
visited[node] = true;
console.log(node + " ");
let neighbours = graph[node];
for (let i = neighbours.length - 1; i >= 0; i--) {
if (!visited[neighbours[i]]) {
stack.push(neighbours[i]);
}
}
}
}
}
function printDFS(V, graph) {
let visited = Array(V + 1).fill(false);
for (let i = 1; i <= V; i++) {
if (!visited[i]) {
dfs(graph, visited, i);
}
}
}
function addEdge(graph, u, v) {
graph[u].push(v);
graph[v].push(u);
}
let V = 6

You can also try this code with Online Javascript 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 DFS and how it works?
DFS (Depth First Search) is an algorithm for traversing or searching graph/tree structures. It starts at a root node and explores as far as possible along each branch before backtracking. It uses a stack (explicit or recursion) for implementation.
What are the two types of DFS?
The two types of DFS are Recursive DFS and Iterative DFS. Recursive DFS uses function calls to traverse nodes, while Iterative DFS employs an explicit stack for traversal, making it suitable for handling deeper graphs without risking stack overflow.
What are the benefits of DFS?
DFS efficiently explores deep graphs, requires less memory compared to BFS, and is useful for solving problems like cycle detection, pathfinding, and connected components in a graph. It is particularly effective for backtracking and puzzle-solving.
What are the features of DFS?
DFS uses a stack for traversal, explores nodes deeply before backtracking, and works on both directed and undirected graphs. It is optimal for traversing connected components and is implemented with either recursion or an explicit stack.
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.
Conclusion
In this article, we learned about the iterative approach to the DFS traversal of a graph. We discussed on how an explicit stack replaces recursion, ensuring efficient traversal of nodes. This method proves effective for large graphs, offering better control and flexibility during graph exploration.
Recommended problems -