DFS (Depth First Search) on a Graph

Given a directed or undirected graph, write a program to perform Depth First Traversal (DFS) starting from a given source node. In DFS, we start from a node and explore as far as possible along each branch before backtracking. The traversal explores each node and its descendants before moving to other adjacent nodes.

Input/Output Examples

plaintext
Example 1 (Undirected Graph):
Input:

  0 --- 1
   |     \
   |      2
   |     /
  3 --- 4

Output: 0 1 2 4 3
Explanation: Starting from node 0, DFS explores nodes in depth-first manner. The nodes are visited in the order 0 -> 1 -> 2 -> 4 -> 3.

Example 2 (Directed Graph):
Input:

    0
   / \
  1   2
   \   \
    3 - 4

Output: 0 1 3 4 2
Explanation: Starting from node 0, DFS explores nodes in depth-first manner, visiting nodes in the order 0 -> 1 -> 3 -> 4 -> 2.

Approach to Perform Depth First Traversal (DFS) on a Graph

  1. Graph Representation:
    • We represent a graph using an adjacency list, where each node points to a list of its adjacent nodes (neighbors).
    • The graph can be either directed or undirected. In both cases, we need to visit each node exactly once during DFS.
  2. DFS Using Recursion:
    • Start from the given source node.
    • Visit the node and mark it as visited.
    • For each neighbor of the current node, if it hasn't been visited yet, recursively visit it.
  3. Handling Disconnected Components:
    • In a graph, it’s possible that not all nodes are reachable from the starting node. To handle disconnected components, we may need to run DFS for every unvisited node.
  4. Edge Cases:
    • If the graph is empty, return an empty traversal.
    • If the graph has only one node, return that node as the traversal.

C++ Program for Depth First Traversal of a Graph

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

// Function to perform DFS traversal on a graph
void dfs(int node, vector<int> adj[], vector<bool>& visited) {
    visited[node] = true;
    cout << node << " ";  // Visit the node

    // Explore all neighbors of the current node
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, adj, visited);
        }
    }
}

int main() {
    // Number of vertices
    int V = 5;
    
    // Create an adjacency list for the graph
    vector<int> adj[V];

    // Adding edges (Undirected graph)
    adj[0].push_back(1);
    adj[1].push_back(0);
    
    adj[0].push_back(3);
    adj[3].push_back(0);
    
    adj[1].push_back(2);
    adj[2].push_back(1);
    
    adj[1].push_back(4);
    adj[4].push_back(1);
    
    adj[3].push_back(4);
    adj[4].push_back(3);

    vector<bool> visited(V, false);

    // Perform DFS starting from node 0
    cout << "DFS Traversal starting from node 0: ";
    dfs(0, adj, visited);
    cout << endl;

    return 0;
}

Java Program for Depth First Traversal of a Graph

java
import java.util.*;

// DFS Traversal on a Graph
public class DFSGraph {

    // Function to perform DFS traversal on the graph
    public static void dfs(int node, List<List<Integer>> adj, boolean[] visited) {
        visited[node] = true;
        System.out.print(node + " ");  // Visit the node

        // Explore all neighbors of the current node
        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                dfs(neighbor, adj, visited);
            }
        }
    }

    public static void main(String[] args) {
        // Number of vertices
        int V = 5;

        // Create an adjacency list for the graph
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }

        // Adding edges (Undirected graph)
        adj.get(0).add(1);
        adj.get(1).add(0);
        
        adj.get(0).add(3);
        adj.get(3).add(0);
        
        adj.get(1).add(2);
        adj.get(2).add(1);
        
        adj.get(1).add(4);
        adj.get(4).add(1);
        
        adj.get(3).add(4);
        adj.get(4).add(3);

        boolean[] visited = new boolean[V];

        // Perform DFS starting from node 0
        System.out.print("DFS Traversal starting from node 0: ");
        dfs(0, adj, visited);
        System.out.println();
    }
}

Python Program for Depth First Traversal of a Graph

python
# Function to perform DFS traversal on a graph
def dfs(node, adj, visited):
    visited[node] = True
    print(node, end=" ")  # Visit the node

    # Explore all neighbors of the current node
    for neighbor in adj[node]:
        if not visited[neighbor]:
            dfs(neighbor, adj, visited)

# Example usage
if __name__ == "__main__":
    # Number of vertices
    V = 5

    # Create an adjacency list for the graph
    adj = [[] for _ in range(V)]

    # Adding edges (Undirected graph)
    adj[0].append(1)
    adj[1].append(0)
    
    adj[0].append(3)
    adj[3].append(0)
    
    adj[1].append(2)
    adj[2].append(1)
    
    adj[1].append(4)
    adj[4].append(1)
    
    adj[3].append(4)
    adj[4].append(3)

    visited = [False] * V

    # Perform DFS starting from node 0
    print("DFS Traversal starting from node 0:", end=" ")
    dfs(0, adj, visited)
    print()
  • Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges. Each vertex and each edge is processed once during the traversal.
  • Space Complexity: O(V) for the visited array and the recursive call stack (in the case of recursion).

DSA

7266

737

Related Articles