Depth First Search (DFS) Algorithm

Methods to Implement the DFS Algorithm

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

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

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

#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

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:

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.
    

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

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

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

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

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.
 

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.
 

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

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

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

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

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.
 

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.
 

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

Depth First Search (DFS) is a fundamental graph traversal algorithm that explores as far down a branch as possible before backtracking. It uses a stack (explicit or implicit via recursion) to manage exploration. DFS is ideal for tasks like pathfinding, cycle detection, and topological sorting, making it a versatile and essential tool in computer science. 

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

You may also refer to the following blogs:

• Design and Analysis of Algorithms
   
• BFS vs DFS for a binary tree
   
• Kadane's Algorithm
   
• Graph Traversal Techniques

Happy Reading!