Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Depth-First Search

MEDIUMProblemSolveExternal Links

Description

You are given a connected undirected graph with V vertices numbered from 0 to V−1. The graph is represented as an adjacency list, where adj[i] contains all the vertices directly connected to vertex i.

Your task is to perform a Depth-First Search (DFS) traversal starting from vertex 0 and return the order in which vertices are visited.

DFS explores the graph by going as deep as possible along one path before backtracking. Starting from the source vertex, it visits the first unvisited neighbor, then the first unvisited neighbor of that neighbor, and so on. When it reaches a vertex with no unvisited neighbors (a dead end), it backtracks to the most recent vertex that still has unexplored neighbors and continues from there.

When visiting the neighbors of any vertex, visit them in the same order they appear in the adjacency list.

Return a list of all vertices in the order they are visited during the DFS traversal.

Undirected graph with 5 nodes showing the structure for DFS traversal, with node 0 highlighted as the starting vertex
Undirected graph with 5 nodes showing the structure for DFS traversal, with node 0 highlighted as the starting vertex

Examples

Example 1

Input: adj = [[2, 3, 1], [0], [0, 4], [0], [2]]

Output: [0, 2, 4, 3, 1]

Explanation:

  • Start at vertex 0. Its neighbors in adjacency list order are [2, 3, 1].
  • Visit 0, then go deep into its first neighbor: vertex 2.
  • From vertex 2, neighbors are [0, 4]. Node 0 is visited, so go to 4.
  • From vertex 4, the only neighbor is 2 (visited). Dead end → backtrack to 2, then to 0.
  • Back at 0, the next unvisited neighbor is 3. Visit 3.
  • From 3, the only neighbor is 0 (visited). Dead end → backtrack to 0.
  • The last unvisited neighbor of 0 is 1. Visit 1.
  • From 1, the only neighbor is 0 (visited). Dead end → backtrack to 0. All done.
  • DFS went deep first: 0 → 2 → 4, then backtracked to explore 3 and 1.

Example 2

Input: adj = [[1, 2], [0, 2], [0, 1, 3, 4], [2], [2]]

Output: [0, 1, 2, 3, 4]

Explanation:

  • Start at 0. First neighbor: 1. Visit 1.
  • From 1, neighbors [0, 2]. Node 0 visited, visit 2.
  • From 2, neighbors [0, 1, 3, 4]. Nodes 0 and 1 visited. Visit 3.
  • From 3, neighbor [2] is visited. Dead end → backtrack to 2.
  • Next unvisited neighbor of 2: 4. Visit 4.
  • From 4, neighbor [2] is visited. Dead end → backtrack all the way.
  • DFS path: 0 → 1 → 2 → 3 (backtrack) → 4.

Example 3

Input: adj = [[1], [0]]

Output: [0, 1]

Explanation:

  • The graph has only two vertices connected by a single edge.
  • Start at vertex 0, go to its only neighbor 1.
  • From 1, the only neighbor is 0 (visited). Backtrack and finish.
  • DFS completes in two visits.

Constraints

  • 1 ≤ V = adj.size() ≤ 10^4
  • 0 ≤ adj[i][j] < V
  • The graph is connected and undirected
  • The adjacency list does not contain duplicate edges
  • There are no self-loops

Editorial

Brute Force

Intuition

The most natural way to implement DFS is through recursion. Think of it like exploring a maze: at every junction, you always take the first unexplored path. You walk down that path as far as you can. When you hit a dead end (no more unexplored corridors), you walk back to the previous junction and try the next unexplored path.

Recursion mirrors this perfectly. When we visit a node, we immediately try to visit its first unvisited neighbor — which triggers another function call. That call visits the neighbor's first unvisited neighbor, and so on. When a function call has no unvisited neighbors to explore, it simply returns — which is the 'backtracking' step. The system call stack automatically remembers where we left off at each junction.

The approach is elegant and easy to write, but it has a hidden limitation: every recursive call adds a frame to the system's call stack, which has a fixed size limit. For a graph shaped like a long chain (0→1→2→...→V−1), the recursion would go V levels deep. With V up to 10^4, this may exceed the default stack size in many programming environments.

Step-by-Step Explanation

Let's trace through Example 1 with adj = [[2, 3, 1], [0], [0, 4], [0], [2]]:

Step 1: Call dfs(0)

  • Mark 0 as visited, add to result.
  • Call stack: [dfs(0)], visited = {0}, result = [0]
  • Neighbors of 0: [2, 3, 1]. First unvisited: 2.

Step 2: Call dfs(2)

  • Mark 2 as visited, add to result.
  • Call stack: [dfs(0), dfs(2)], visited = {0, 2}, result = [0, 2]
  • Neighbors of 2: [0, 4]. Node 0 is visited. First unvisited: 4.

Step 3: Call dfs(4)

  • Mark 4 as visited, add to result.
  • Call stack: [dfs(0), dfs(2), dfs(4)], visited = {0, 2, 4}, result = [0, 2, 4]
  • Neighbors of 4: [2]. Node 2 is visited. No unvisited neighbors — dead end.

Step 4: Backtrack from dfs(4) to dfs(2)

  • dfs(4) returns. Call stack: [dfs(0), dfs(2)].
  • Back in dfs(2): neighbor 0 was visited, neighbor 4 was visited. All neighbors done.

Step 5: Backtrack from dfs(2) to dfs(0)

  • dfs(2) returns. Call stack: [dfs(0)].
  • Back in dfs(0): first neighbor (2) fully explored. Move to next neighbor: 3.

Step 6: Call dfs(3)

  • Mark 3 as visited, add to result.
  • Call stack: [dfs(0), dfs(3)], visited = {0, 2, 3, 4}, result = [0, 2, 4, 3]
  • Neighbors of 3: [0]. Node 0 is visited. Dead end.

Step 7: Backtrack from dfs(3) to dfs(0)

  • dfs(3) returns. Call stack: [dfs(0)].
  • Back in dfs(0): next unvisited neighbor: 1.

Step 8: Call dfs(1)

  • Mark 1 as visited, add to result.
  • Call stack: [dfs(0), dfs(1)], visited = {0, 1, 2, 3, 4}, result = [0, 2, 4, 3, 1]
  • Neighbors of 1: [0]. Node 0 is visited. Dead end.

Step 9: Backtrack from dfs(1) to dfs(0)

  • dfs(1) returns. Call stack: [dfs(0)].
  • All neighbors of 0 explored (2 ✓, 3 ✓, 1 ✓).

Step 10: dfs(0) returns

  • Call stack: []. DFS complete.
  • Final result: [0, 2, 4, 3, 1]
  • Maximum recursion depth reached: 3 (dfs(0) → dfs(2) → dfs(4)).
  • In a chain graph of V=10^4 nodes, this depth would be 10^4 — potentially causing a stack overflow.

Algorithm

  1. Create a visited array of size V, initialized to false
  2. Create an empty result list
  3. Call the recursive helper function dfs(0):
    a. Mark the current node as visited
    b. Add the current node to the result
    c. For each neighbor of the current node (in adjacency list order):
    • If the neighbor is not visited, recursively call dfs(neighbor)
  4. Return the result list

Code

#include <vector>
using namespace std;

class Solution {
public:
    void dfsHelper(vector<vector<int>>& adj, int node,
                   vector<bool>& visited, vector<int>& result) {
        visited[node] = true;
        result.push_back(node);

        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                dfsHelper(adj, neighbor, visited, result);
            }
        }
    }

    vector<int> dfsOfGraph(vector<vector<int>>& adj) {
        int V = adj.size();
        vector<bool> visited(V, false);
        vector<int> result;
        dfsHelper(adj, 0, visited, result);
        return result;
    }
};
import sys
sys.setrecursionlimit(10001)

class Solution:
    def dfsHelper(self, adj, node, visited, result):
        visited[node] = True
        result.append(node)

        for neighbor in adj[node]:
            if not visited[neighbor]:
                self.dfsHelper(adj, neighbor, visited, result)

    def dfsOfGraph(self, adj):
        V = len(adj)
        visited = [False] * V
        result = []
        self.dfsHelper(adj, 0, visited, result)
        return result
import java.util.*;

class Solution {
    private void dfsHelper(ArrayList<ArrayList<Integer>> adj, int node,
                           boolean[] visited, ArrayList<Integer> result) {
        visited[node] = true;
        result.add(node);

        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                dfsHelper(adj, neighbor, visited, result);
            }
        }
    }

    public ArrayList<Integer> dfsOfGraph(ArrayList<ArrayList<Integer>> adj) {
        int V = adj.size();
        boolean[] visited = new boolean[V];
        ArrayList<Integer> result = new ArrayList<>();
        dfsHelper(adj, 0, visited, result);
        return result;
    }
}

Complexity Analysis

Time Complexity: O(V + E)

Each vertex is visited exactly once (the visited check prevents re-entry). For each vertex, we iterate through its adjacency list to check all neighbors. Since each edge appears twice in an undirected graph's adjacency list (once per endpoint), the total neighbor-checking work across all vertices is O(2E) = O(E). Combined with visiting V vertices: O(V + E).

Space Complexity: O(V)

The visited array takes O(V) space. The recursion stack can grow up to O(V) deep in the worst case (a chain graph where every node connects to the next). The result array stores V elements. Total auxiliary space: O(V).

Practical concern: The O(V) recursion depth means the system call stack must accommodate up to 10^4 frames. Python's default limit is 1000 (requires sys.setrecursionlimit), and even C++/Java may hit limits for very deep chains.

Why This Approach Is Not Efficient

The recursive DFS produces the correct result and has optimal O(V + E) time complexity. However, it has a serious practical limitation: stack overflow risk.

Every recursive call adds a frame to the system call stack. Each frame stores local variables, the return address, and function parameters. For a chain graph with V = 10^4 nodes (0→1→2→...→9999), the recursion goes 10^4 levels deep.

Default stack limits by language:

  • Python: 1000 recursive calls (crashes without sys.setrecursionlimit)
  • C++: ~10^4–10^5 frames depending on OS stack size (typically 1–8 MB)
  • Java: ~10^3–10^4 frames depending on thread stack size

Even when we increase the limit, the system call stack cannot grow beyond a fixed memory allocation. If a problem had V up to 10^6, recursive DFS would almost certainly crash.

The fundamental issue is that we are relying on an implicit, fixed-size stack (the system call stack) instead of managing our own. An explicit stack data structure has no such limit — it can grow as large as the heap memory allows, which is typically hundreds of megabytes or more.

The solution: replace the recursive calls with an explicit stack and a while loop. This gives us full control over memory and eliminates any risk of stack overflow, while maintaining the same O(V + E) time and O(V) space complexity.

Optimal Approach - Iterative DFS with Explicit Stack

Intuition

Recursion is just a convenient way to use a stack — the system call stack. Every time we call dfs(neighbor), we are essentially pushing the current state onto the stack. When the function returns, we pop it back. We can do exactly the same thing ourselves with an explicit stack data structure.

Think of it like carrying a notepad in the maze instead of relying on your memory. At every junction, you write down the paths you still need to explore. When you hit a dead end, you look at your notepad and pick the most recently added note (LIFO — Last In, First Out). This is exactly how a stack works.

The key detail: when we push neighbors onto the stack, we push them in reverse adjacency list order. This is because a stack is LIFO — the last item pushed is the first one popped. By pushing in reverse, the first neighbor in the adjacency list ends up on top and gets processed first. This ensures the iterative DFS visits nodes in the same order as the recursive version.

We also mark nodes as visited when we push them (not when we pop them). This prevents the same node from being pushed multiple times by different neighbors, keeping the stack size bounded at O(V).

Step-by-Step Explanation

Let's trace through Example 1 with adj = [[2, 3, 1], [0], [0, 4], [0], [2]]:

Step 1: Initialization

  • Push 0 onto stack, mark visited: stack = [0], visited = {0}, result = []

Step 2: Pop and process node 0

  • Pop 0: stack = []. Add to result: result = [0]
  • Push neighbors in reverse adjacency order so first neighbor lands on top:
    • Push 1 (mark visited): stack = [1]
    • Push 3 (mark visited): stack = [1, 3]
    • Push 2 (mark visited): stack = [1, 3, 2]
  • Node 2 is on top → it will be processed next, going deep into the 0→2 branch.

Step 3: Pop and process node 2

  • Pop 2: stack = [1, 3]. Add to result: result = [0, 2]
  • Neighbors of 2: [0, 4]. Reversed: [4, 0].
    • Node 0 is already visited → skip
    • Push 4 (mark visited): stack = [1, 3, 4]
  • Node 4 is on top → DFS continues deeper into 0→2→4.

Step 4: Pop and process node 4

  • Pop 4: stack = [1, 3]. Add to result: result = [0, 2, 4]
  • Neighbor 2 is already visited → nothing to push.
  • Dead end. DFS backtracks by popping the next stack element.

Step 5: Pop and process node 3

  • Pop 3: stack = [1]. Add to result: result = [0, 2, 4, 3]
  • Neighbor 0 is already visited → nothing to push.
  • Another dead end.

Step 6: Pop and process node 1

  • Pop 1: stack = []. Add to result: result = [0, 2, 4, 3, 1]
  • Neighbor 0 is already visited → nothing to push.

Step 7: Termination

  • Stack is empty. DFS complete.
  • Final result: [0, 2, 4, 3, 1]
  • The stack naturally handled backtracking: after the deep path 0→2→4, nodes 3 and 1 (pushed earlier) were waiting on the stack to be explored.

Iterative DFS — Depth-First Exploration with Explicit Stack — Watch how DFS uses a stack to explore as deep as possible before backtracking, pushing neighbors in reverse order so the first neighbor in the adjacency list is processed first.

Algorithm

  1. Create a stack and push the source vertex (0)
  2. Create a boolean visited array of size V; mark vertex 0 as visited
  3. Initialize an empty result list
  4. While the stack is not empty:
    a. Pop the top vertex from the stack
    b. Append the popped vertex to the result
    c. For each neighbor of the popped vertex (in reverse adjacency list order):
    • If the neighbor has not been visited:
      • Mark it as visited
      • Push it onto the stack
        (Reversing ensures the first neighbor in the adjacency list ends up on top of the stack and is processed first)
  5. Return the result list

Code

#include <vector>
#include <stack>
using namespace std;

class Solution {
public:
    vector<int> dfsOfGraph(vector<vector<int>>& adj) {
        int V = adj.size();
        vector<bool> visited(V, false);
        vector<int> result;
        stack<int> stk;

        stk.push(0);
        visited[0] = true;

        while (!stk.empty()) {
            int node = stk.top();
            stk.pop();
            result.push_back(node);

            // Push in reverse order so first neighbor is on top
            for (int i = adj[node].size() - 1; i >= 0; i--) {
                int neighbor = adj[node][i];
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    stk.push(neighbor);
                }
            }
        }

        return result;
    }
};
class Solution:
    def dfsOfGraph(self, adj):
        V = len(adj)
        visited = [False] * V
        result = []
        stack = [0]
        visited[0] = True

        while stack:
            node = stack.pop()
            result.append(node)

            # Push in reverse order so first neighbor is on top
            for neighbor in reversed(adj[node]):
                if not visited[neighbor]:
                    visited[neighbor] = True
                    stack.append(neighbor)

        return result
import java.util.*;

class Solution {
    public ArrayList<Integer> dfsOfGraph(ArrayList<ArrayList<Integer>> adj) {
        int V = adj.size();
        boolean[] visited = new boolean[V];
        ArrayList<Integer> result = new ArrayList<>();
        Deque<Integer> stack = new ArrayDeque<>();

        stack.push(0);
        visited[0] = true;

        while (!stack.isEmpty()) {
            int node = stack.pop();
            result.add(node);

            // Push in reverse order so first neighbor is on top
            List<Integer> neighbors = adj.get(node);
            for (int i = neighbors.size() - 1; i >= 0; i--) {
                int neighbor = neighbors.get(i);
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    stack.push(neighbor);
                }
            }
        }

        return result;
    }
}

Complexity Analysis

Time Complexity: O(V + E)

Each vertex is pushed onto and popped from the stack exactly once, contributing O(V) work. For each popped vertex, we iterate through its adjacency list to find unvisited neighbors. Since each edge appears twice in an undirected graph's adjacency list, the total neighbor-checking work is O(2E) = O(E). Combined: O(V + E).

For V ≤ 10^4, this is at most ~2 × 10^4 operations — extremely fast.

Space Complexity: O(V)

The visited array uses O(V) space. The stack holds at most V elements at any point (in the worst case, all vertices are pushed before any are fully processed). The result array stores exactly V elements. Total: O(V).

Unlike the recursive approach, the explicit stack lives on the heap, which can handle millions of elements. There is no risk of stack overflow regardless of graph shape or size.