Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
4.
Code Implementation
4.1.
C++
4.2.
Java
4.3.
Python
4.4.
JS
5.
Frequently Asked Questions
5.1.
What is DFS and how it works?
5.2.
What are the two types of DFS?
5.3.
What are the benefits of DFS?
5.4.
What are the features of DFS?
5.5.
What is the difference between a DFS Traversal and a BFS Traversal?
6.
Conclusion
Last Updated: Jan 7, 2025
Medium

Depth First Search (DFS) Traversal of a Graph

Author Gaurish Anand
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Depth First Search (DFS) is a graph traversal algorithm that explores as far down a branch as possible before backtracking. Starting from a node, DFS visits unvisited adjacent nodes recursively, diving deeper into the graph. It is useful for searching, pathfinding, and solving problems like connectivity and cycle detection in both directed and undirected graphs.

Depth First Search (DFS) Traversal of a Graph

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  

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

Below is the implementation of the approach:

  • C++
  • Java
  • Python
  • JS

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 -

Live masterclass