Depth-First Search

MediumProblemExternal linkUpdated Oct 1, 2026

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.

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

Create a visited array of size V, initialized to false
Create an empty result list
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)
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 keeping the same O(V + E) time and exactly the same visiting order.

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.

One more detail matters just as much: we mark a node as visited when we pop it, not when we push it. Marking on push looks tempting, because each node would then enter the stack only once, but it breaks the DFS order. Take adj = [[3, 1], [0, 3], [3], [0, 1, 2]]. Recursive DFS goes 0 → 3 → 1, then backtracks to 3 and visits 2: [0, 3, 1, 2]. If we marked on push, processing 0 would mark both 3 and 1 at once; 3 would then skip 1 as "already visited" and go to 2 instead, giving [0, 3, 2, 1]. Marking on pop means a node counts as visited only when DFS actually reaches it. The price is that a node can sit on the stack more than once (pushed by different neighbors before DFS reaches it), so when we pop a node that is already visited, we simply skip it.

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 the stack (nothing is marked yet): stack = [0], visited = {}, result = []

Step 2: Pop and process node 0

Pop 0: stack = []. Not visited yet → mark it and add to result: visited = {0}, result = [0]
Push its unvisited neighbors in reverse adjacency order so the first neighbor lands on top:
- Push 1: stack = [1]
- Push 3: stack = [1, 3]
- Push 2: 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]. Mark it and add to result: result = [0, 2]
Neighbors of 2: [0, 4]. Reversed: [4, 0].
- Push 4: stack = [1, 3, 4]
- Node 0 is already visited → skip
Node 4 is on top → DFS continues deeper into 0→2→4.

Step 4: Pop and process node 4

Pop 4: stack = [1, 3]. Mark it and 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]. Mark it and 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 = []. Mark it and 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.
This graph is a tree, so no node was ever pushed twice. In a graph with cycles, a node can be pushed by two different neighbors; whichever copy is popped first visits it, and the other copy is skipped when it is popped.

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

Create a stack and push the source vertex (0)
Create a boolean visited array of size V, all false
Initialize an empty result list
While the stack is not empty:
a. Pop the top vertex from the stack
b. If it is already visited, skip it (an extra copy pushed by another neighbor)
c. Otherwise, mark it as visited and append it to the result
d. For each neighbor of the popped vertex (in reverse adjacency list order):
- If the neighbor has not been 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)
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);

        while (!stk.empty()) {
            int node = stk.top();
            stk.pop();
            if (visited[node]) continue;  // an extra copy of a node we already visited
            visited[node] = true;
            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]) {
                    stk.push(neighbor);
                }
            }
        }

        return result;
    }
};

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

        while stack:
            node = stack.pop()
            if visited[node]:
                continue  # an extra copy of a node we already visited
            visited[node] = True
            result.append(node)

            # Push in reverse order so first neighbor is on top
            for neighbor in reversed(adj[node]):
                if not visited[neighbor]:
                    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);

        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (visited[node]) continue;  // an extra copy of a node we already visited
            visited[node] = true;
            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]) {
                    stack.push(neighbor);
                }
            }
        }

        return result;
    }
}

Complexity Analysis

Time Complexity: O(V + E)

Each vertex is visited (marked and added to the result) exactly once, contributing O(V) work. When a vertex is visited, we iterate through its adjacency list once 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). Every push comes from one of those checks, and an edge causes a push only from whichever endpoint is visited first, so there are at most E + 1 pushes (counting the initial push of 0) and just as many pops; skipping an extra copy costs O(1). Combined: O(V + E).

The work is linear in the size of the input: for a sparse graph with V = 10^4 and E ≈ V, that is only about 3 × 10^4 steps — extremely fast.

Space Complexity: O(V + E)

The visited array uses O(V) space and the result array stores exactly V elements. Because a node is marked only when it is popped, it can be pushed several times (once by each neighbor visited before it) before DFS reaches it. Each edge causes at most one push, so the stack holds at most E + 1 entries, and a dense graph really gets close: in a complete graph, each visited vertex pushes every vertex not yet visited. That is O(E), no more than the adjacency list itself already occupies. Total: O(V + E).

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.