Depth-First Search (DFS) Traversal in Graphs

Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as deep as possible along each branch before backtracking. Unlike Breadth-First Search (BFS), which spreads outward level by level, DFS plunges straight down into the depth of the graph, making it heavily reliant on the mechanics of recursion.

1. Why Do We Need Depth-First Search (DFS)?

Level vs. Depth Exploration: While BFS explores neighbor nodes level by level using a queue, DFS travels down a single path to its absolute limit before turning around.
Exhaustive Pathfinding: DFS is essential when you need to visit every reachable vertex in a graph, detect cycles, find connected components, or perform topological sorting.
Recursive Nature: DFS naturally mirrors recursive execution, utilizing the system call stack to remember where to return when a dead end or fully explored branch is reached.

2. Core Mental Model: The Deep-Dive Explorer Analogy

Real-Life Analogy: Imagine exploring a massive cave system with multiple tunnels. In BFS, you would look at all immediate tunnels branching from the entrance, take a step into each, and look around. In DFS, you pick one tunnel, walk all the way down until you hit a dead end, then retrace your steps backward until you find an unexplored branch, and plunge down that one. You keep repeating this until every single tunnel in the cave system has been walked.

3. Step-by-Step Traversal Walkthrough

Let's consider an undirected graph with vertices numbered $1$ to $8$ . Assume our starting node is $1$ .

CODE

Graph structure overview:
Node 1 connected to: 2, 3
Node 2 connected to: 1, 5, 6
Node 3 connected to: 1, 4, 7
Node 4 connected to: 3, 8
Node 5 connected to: 2
Node 6 connected to: 2
Node 7 connected to: 3, 8
Node 8 connected to: 4, 7

Execution Starting at Node 1:

Visit Node 1: Mark $1$ as visited and add it to our traversal list.
Explore Neighbors of 1: Node $1$ has neighbors $2$ and $3$ . We pick the first available unvisited neighbor: $2$ .
Dive into Node 2: Mark $2$ as visited. Its neighbors are $1, 5, 6$ . Node $1$ is already visited, so we pick the next unvisited neighbor: $5$ .
Dive into Node 5: Mark $5$ as visited. It has no unvisited neighbors (only $2$ , which is visited). We hit a dead end!
Backtrack to 2: From Node $2$ , we check the remaining neighbor $6$ . Mark $6$ as visited. Node $6$ has no further unvisited neighbors.
Backtrack to 1: Node $2$ and all its descendants are fully explored. We return to Node $1$ and pick its next unvisited neighbor: $3$ .
Dive into Node 3: Mark $3$ as visited. Its neighbors are $1, 4, 7$ . We pick $4$ .
Dive into Node 4: Mark $4$ as visited. Its neighbors are $3$ and $8$ . We pick $8$ .
Dive into Node 8: Mark $8$ as visited. Its neighbors are $4$ and $7$ . We pick $7$ .
Check Node 7: Mark $7$ as visited. Its neighbors ( $3, 8$ ) are already visited. We hit a dead end and backtrack all the way up as all branches are now fully explored.

Final DFS Traversal Sequence: 1 -> 2 -> 5 -> 6 -> 3 -> 4 -> 8 -> 7 (Note: Sequence may vary depending on the order of neighbors stored in the adjacency list).

4. Initial Configuration and Visited Array Setup

Just like BFS, DFS requires a tracking mechanism to prevent infinite loops in cyclic graphs.

Visited Array: Create a boolean/integer array of size $N + 1$ (for 1-based indexing) or size $N$ (for 0-based indexing), initialized entirely to 0 (unvisited).
Starting Node: Mark the starting node as visited (1) immediately before triggering the recursive traversal function.

Structure & Concept Flow

Index: 0 1 2 3 4 5 6 7 8

Visited: [0] [1] [0] [0] [0] [0] [0] [0] [0] <-- Starting node 1 marked as 1

5. Recursive DFS Mechanics & Code Implementation

DFS relies fundamentally on recursion. When a node is visited, we immediately iterate through its adjacency list. For every unvisited neighbor, we make a recursive call.

C++ Implementation

C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    void dfs(int node, vector<int> adj[], int visited[], vector<int>& ls) {
        visited[node] = 1;          // Mark current node as visited
        ls.push_back(node);         // Add node to traversal result list
        
        // Traverse all neighbors of the current node
        for (auto it : adj[node]) {
            if (!visited[it]) {     // If neighbor is unvisited, make recursive call
                dfs(it, adj, visited, ls);
            }
        }
    }

public:
    vector<int> dfsOfGraph(int V, vector<int> adj[]) {
        int visited[V] = {0};       // Initialize visited array with 0
        int start = 0;              // Assuming 0-based indexing start node
        vector<int> ls;
        
        dfs(start, adj, visited, ls);
        return ls;
    }
};

Java Implementation

JAVA

import java.util.ArrayList;
import java.util.List;

class Solution {
    public void dfs(int node, ArrayList<ArrayList<Integer>> adj, boolean[] visited, ArrayList<Integer> ls) {
        visited[node] = true;
        ls.add(node);
        
        // Traverse through all neighbors
        for (Integer it : adj.get(node)) {
            if (!visited[it]) {
                dfs(it, adj, visited, ls);
            }
        }
    }

    public ArrayList<Integer> dfsOfGraph(int V, ArrayList<ArrayList<Integer>> adj) {
        boolean[] visited = new boolean[V];
        ArrayList<Integer> ls = new ArrayList<>();
        
        // Start DFS from node 0
        dfs(0, adj, visited, ls);
        return ls;
    }
}

6. Comprehensive Flow Walkthrough

Let's trace how the recursive stack processes the calls when executing dfs(0, adj, visited, ls):

Structure & Concept Flow

dfs(0) called

+--> Marks visited[0] = 1, adds 0 to ls

+--> Loops through neighbors of 0 (e.g., neighbor 1)

+--> dfs(1) called

+--> Marks visited[1] = 1, adds 1 to ls

+--> Loops through neighbors of 1 (e.g., neighbor 2)

+--> dfs(2) called ... (continues deep)

When a node has no unvisited neighbors remaining, its recursive stack frame pops, returning control back to the parent node, which then checks its next adjacent neighbor.

7. Complexity Analysis

Complexity Metric	Undirected Graph	Directed Graph	Explanation
Time Complexity	$O(V + 2E)$	$O(V + E)$	Every vertex is visited once ( $O(V)$ ), and across all recursive calls, every edge is traversed twice in an undirected graph ( $2E$ ) and once in a directed graph ( $E$ ).
Space Complexity	$O(V)$	$O(V)$	Space required for the `visited` array ( $O(V)$ ), the result list ( $O(V)$ ), and the recursive system call stack in the worst-case skewed graph scenario ( $O(V)$ ).

Summary and Key Takeaways

Depth-First Priority: DFS explores a graph by going as deep down a branch as possible before backtracking.
Recursion Core: The algorithm is naturally implemented using recursion, leveraging the call stack to manage backtracking.
Visited Array Protection: Always maintain a visited array to mark processed nodes and prevent infinite loops in cyclic graphs.
Adjacency List Dependency: The exact traversal path depends strictly on the ordering of neighbors stored within the adjacency list.
Time Complexity ( $O(V + 2E)$ ): Linear with respect to the number of vertices and edges, as every node is visited once and every edge is inspected from both endpoints in undirected graphs.
Stack Space Risk: In worst-case linear/skewed graphs (like a linked list), recursion stack depth equals $O(V)$ , which can trigger stack overflow errors if recursion limits are exceeded.