Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is the Depth First Search or DFS Algorithm?
3.
Methods to Implement the DFS Algorithm
3.1.
Recursive Approach
3.2.
Iterative Approach
4.
Implementation of DFS Algorithm
4.1.
Python
4.2.
Python
4.3.
Java
4.4.
Java
4.5.
C++
4.6.
C++
5.
PseudoCode of DFS Algorithm
6.
Complexity of DFS Algorithm
6.1.
Time Complexity
6.2.
Space Complexity
7.
Example of DFS Algorithm
8.
Applications of DFS Algorithm
9.
Frequently Asked Questions
9.1.
What is the DFS algorithm?
9.2.
What is DFS vs BFS? 
9.3.
What is the use of DFS?
9.4.
What is the space complexity of DFS? 
10.
Conclusion
Last Updated: Mar 27, 2024
Medium

Depth First Search (DFS) Algorithm

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

This article will discuss one of the most popular graph algorithms, the DFS algorithm.

DFS algorithm, which stands for Depth-First Search, is a popular algorithm used to search or traverse a graph or tree Data Structures

 dfs algorithm

The algorithm commences at a selected node and explores the graph as far as possible before backtracking. In this article, you will learn different methods to implement DFS, its pseudocode with implementation, and some of its applications.

What is the Depth First Search or DFS Algorithm?

Depth First Search (DFS) is a graph traversal algorithm that explores a graph or tree by visiting as far as possible along each branch before backtracking. It starts at a chosen node, explores all its unvisited neighbors, and repeats the process recursively. DFS is like navigating a maze, going down one path until you hit a dead-end, then retracing your steps and exploring another path. It's commonly used for tasks like finding connected components, detecting cycles, and searching for paths or routes in various applications, including computer networks, Artificial Intelligence, and solving puzzles.

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

Methods to Implement the DFS Algorithm

DFS recursive and iterative approach

The following two methods are typically employed to implement DFS efficiently- recursive and iterative.

Recursive Approach

In the recursive approach, the algorithm starts at the source vertex and marks it as visited. It recursively explores every unvisited neighbor of the source vertex. When no more unvisited neighbors are left, the algorithm backtracks to the previous vertex in the stack and repeats the process until all vertices in the graph are visited.

Iterative Approach

In the iterative approach, the algorithm uses a stack to keep track of the vertices that need to be visited next. It starts at the source vertex, marks it as visited, and pushes it onto the stack. Then, it repeatedly pops the top vertex from the stack, explores its unvisited neighbors, and makes them onto the stack until all are visited.

Implementation of DFS Algorithm

DFS is a well-known algorithm used for searching and traversing graphs and trees. It employs a systematic approach of visiting all nodes or vertices, beginning from a specified starting point and proceeding as far as possible along each branch before backtracking.

Python

  • Python

Python

def dfs(node, adj, vis):
# Mark the node as visited
vis[node] = True

# Print the node
print(node, end=" ")

# Check if the node has neighbors (is in the adjacency list)
if node in adj:
# Call for neighbors
for nbr in adj[node]:
if not vis[nbr]:
dfs(nbr, adj, vis)

if __name__ == "__main__":
# Number of nodes
n = 9

# List of edges
edges = [[0, 2], [0, 1], [1, 4], [2, 5], [2, 3], [3, 8], [5, 6], [6, 7]]

# Create an adjacency list
adj = {}
for u, v in edges:
if u not in adj:
adj[u] = []
adj[u].append(v)

# Create a visited array
vis = [False] * n

# Perform DFS for unvisited nodes
for i in range(n):
if not vis[i]:
dfs(i, adj, vis)

 

Java

  • Java

Java

import java.util.*;

public class Main {
static void dfs(int node, Map<Integer, List<Integer>> adj, boolean[] vis) {
// Mark the node as visited
vis[node] = true;

// Print the node
System.out.print(node + " ");

// Call for neighbors
for (int nbr : adj.getOrDefault(node, new ArrayList<>())) {
if (!vis[nbr]) {
dfs(nbr, adj, vis);
}
}
}

public static void main(String[] args) {
// Number of nodes
int n = 9;

// List of edges
int[][] edges = {{0, 2}, {0, 1}, {1, 4}, {2, 5}, {2, 3}, {3, 8}, {5, 6}, {6, 7}};

// Create an adjacency list
Map<Integer, List<Integer>> adj = new HashMap<>();
for (int[] i : edges) {
int u = i[0], v = i[1];
adj.putIfAbsent(u, new ArrayList<>());
adj.get(u).add(v);
}

// Create a visited array
boolean[] vis = new boolean[n];

// Perform DFS for unvisited nodes
for (int i = 0; i < n; i++) {
if (!vis[i]) {
dfs(i, adj, vis);
}
}
}
}

 

C++

  • C++

C++

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

void dfs(int node, unordered_map<int, vector<int>> &adj, vector<bool> &vis){
// mark visited as true
vis[node] = true;

// print node
cout<<node<<" ";

// call for neighbours
for(auto nbr: adj[node]){
if(!vis[nbr]){
dfs(nbr, adj, vis);
}
}
}

int main() {
// number of nodes
int n = 9;

// list of edges
vector<vector<int>> edges = {{0,2}, {0,1}, {1,4}, {2,5}, {2,3}, {3, 8}, {5, 6}, {6, 7}};

// create adjacency list
unordered_map<int, vector<int>> adj;
for(auto i:edges){
int u = i[0], v = i[1];
adj[u].push_back(v);
}

// take a visited array
vector<bool> vis(n, false);

// perform dfs for unvisited nodes
for(int i=0; i<n; i++){
if(!vis[i]){
dfs(i, adj, vis);
}
}

return 0;
}

 

Output

output

 

PseudoCode of DFS Algorithm

The pseudocode of the DFS algorithm goes as follows-

DFS(graph, start_node):
    // Mark the starting node as visited
    visited = {}
    visited[start_node] = true

    // Visit the starting node
    visit(start_node)

    // Get all adjacent nodes of the starting node
    adjacent_nodes = graph.get_adjacent_nodes(start_node)

    // Loop through all the adjacent nodes
    for next_node in adjacent_nodes:
        // If the adjacent node is not visited, mark it as visited and perform DFS on it
        if next_node not in visited:
            visited[next_node] = true
            DFS(graph, next_node)

This algorithm explores as far as possible along each branch before backtracking. The stack keeps track of the visited nodes and ensures that vertices are processed in a depth-first order.
 

  • It's important to note that the DFS algorithm may only sometimes visit all nodes in a graph, particularly if disconnected. The algorithm must be applied separately to each connected graph component to ensure all nodes are visited.

Complexity of DFS Algorithm

Let's see the time and space complexity of the DFS Algorithm.

Time Complexity

The time complexity of DFS depends on the structure of the graph or tree being traversed. In the worst-case scenario, where you have to visit every node and edge of the graph, DFS takes O(V + E) time, where V represents the number of vertices (nodes) in the graph, and E represents the number of edges in the graph.

Space Complexity

The space complexity of DFS is determined by the maximum depth of the Recursion stack. In the worst case, if the graph is a long chain or a deep tree, the space complexity is O(V), where V is the number of vertices.

Example of DFS Algorithm

Consider the following graph with five nodes (A, B, C, D, and E) and edges connecting them:

Example


Assume we want to traverse this graph using the DFS algorithm starting from node A. Here's how we can apply the algorithm to this graph step by step:

  1. Mark node A as visited and push it onto the stack.
     
A        

2. Process the children of node A. Check its adjacent nodes B and C.
 

A        

3. Mark node B as visited and push it onto the stack.
 

B A      

4. Read node B and process it. Check its adjacent node D.
 

B A      

5. Mark node D as visited and push it onto the stack.
 

D B A    

6. Pop node D from the stack and process it. Since node D has no adjacent nodes, we backtrack by popping it from the stack.
 

B A      

7. Read node B from the stack and process it. Since node B has no other adjacent nodes, we backtrack by popping it from the stack.
 

A        

8. Read the top node A from the stack and process it. Check its adjacent node C.
 

A        

9. Mark node C as visited and push it onto the stack.
 

C A      

10. Read node C from the stack and process it. Check its adjacent node E.
 

C A      

11. Mark node E as visited and push it onto the stack.
 

E C A    

12. Pop node E from the stack and process it. Since node E has no other adjacent nodes, we backtrack by popping it from the stack.
 

C A      

13. Pop node C from the stack and process it. Since node C has no other adjacent nodes, we backtrack by popping it from the stack.
 

A        

14. Read the top node A from the stack and process it. Since all the children of A are visited, pop it. The stack is now empty, and all nodes in the graph have been visited.

         

Applications of DFS Algorithm

DFS (Depth-First Search) is a robust algorithm with various applications across various domains. DFS, or Depth-First Search, is a versatile algorithm that finds applications across multiple domains. Some of the standard applications of DFS are:

1. Path Finding

PathFinding using DFS involves exploring all possible paths in a graph to identify the shortest or longest path between two nodes. This technique is helpful in navigation systems, where we need to find the most efficient route between two locations.
 

2. Topological Sorting 

DFS performs topological sorting of a directed acyclic graph (DAG). DFS helps to order the nodes in a graph so that no node comes before that node. This technique is used in project dependency graphs or scheduling problems.
 

3. Cycle Detection

DFS is used to detect cycles in a graph. By exploring all the edges in the graph, DFS can identify if a cycle is present. If we encounter a visited child who is not the immediate parent of the current node during traversal, cycle detection occurs. It can be helpful in various applications, such as detecting deadlock in a computer system.
 

4. Lowest Common Ancestor(LCA)

DFS comes in handy to find the LCA of two vertices in a tree. We start at the tree's root and perform a DFS until we reach one of the two nodes. We backtrack and mark the visited nodes on the path to the first node. We then continue the DFS until we reach the second node. At this point, we can backtrack again and find the lowest marked node, the LCA.

 

5. Finding Strongly Connected Components

DFS can find strongly connected components in a directed graph. Strongly connected components are a set of nodes that are all reachable from each other by applying DFS on the transposed graph. It is helpful in applications such as detecting communities in social networks or image processing.
 

6. Maze Generation

DFS is used to generate mazes. By randomly selecting a starting point and exploring all possible paths in a grid, DFS can create a unique maze that can be solved using graph algorithms.
 

7. Finding Bridges and Articulation Points

DFS finds bridges and articulation points in a graph. Bridges are edges that, when removed, increase the number of connected components in the graph. Articulation points are nodes that, when removed, disconnect the graph. It can be helpful in network analysis and designing resilient computer systems.

Frequently Asked Questions

What is the DFS algorithm?

The depth-first search (DFS) algorithm traverses or searches tree or graph data structures. The algorithm starts at the root node and travels as far as possible along each branch before coming to the root node.

What is DFS vs BFS? 

DFS and BFS are algorithms used in graph traversal. DFS explores a graph by going deep into a branch before backtracking, while BFS explores a graph level by level, examining neighboring vertices before moving to the next level. 

What is the use of DFS?

DFS is used for a variety of reasons, but it is most commonly employed for recognising cycles in a graph and locating strongly connected components in a directed graph. It is also used in topological sorting.

What is the space complexity of DFS? 

The space complexity of DFS depends on the implementation, but it typically requires O(V) space to store the visited nodes, where V is the number of vertices in the graph.

Conclusion

In conclusion, the Depth-First Search or DFS Algorithm is a simple yet powerful technique for graph traversal. It starts from a starting node, explores as far as possible along each branch before backtracking, and uses a stack to keep track of visited nodes. DFS is widely used in various applications such as maze generation, topological sorting, and cycle detection. However, it may not necessarily visit all nodes in a graph, especially if the graph is disconnected. Despite its limitations, DFS is a fundamental computer science algorithm widely used in numerous real-world applications.
 

We hope the blog was helpful enough to understand the Depth-First Search algorithm.
 

You may also refer to the following blogs:


Happy Reading!

Previous article
DFS Traversal of a Graph - Iteratively
Next article
DFS for an n-ary Tree(Acyclic Graph) Represented as an Adjacency List
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass