Log inSign up
easyGeeksforGeeksNot Started

Depth First Search

Given a connected undirected graph represented by an adjacency list adj, return a list containing the DFS traversal of the graph starting from vertex 0.

Graph
Solve on GeeksforGeeks
Lesson

Problem Statement

### Problem Statement

Given a connected undirected graph represented by an adjacency list adj, perform a Depth First Search (DFS) traversal starting from vertex 0 and return a list containing the vertices in the order they are visited.

The graph contains V vertices numbered from 0 to V - 1. When visiting neighbors of any vertex, explore them in the order they appear in the adjacency list.

---

### Examples

Example 1: ``text Input: V = 5, adj = [[2, 3, 1], [0], [0, 4], [0], [2]] 0 / | \ 2 3 1 | 4 Output: [0, 2, 4, 3, 1] Explanation: Starting from 0: - First neighbor is 2. Move to 2. - From 2, neighbor 0 is visited, unvisited neighbor is 4. Move to 4. - From 4, all neighbors visited, backtrack to 2, then to 0. - Next neighbor of 0 is 3. Move to 3. - Next neighbor of 0 is 1. Move to 1. Resulting DFS order: 0 -> 2 -> 4 -> 3 -> 1.

Example 2: ``text Input: V = 4, adj = [[1, 3], [2, 0], [1], [0]] Output: [0, 1, 2, 3]

---

### Constraints - 1 <= V <= 10^4 - 1 <= E <= 10^4 - The graph is 0-indexed and connected.

Constraints:

  • 1 <= V <= 104
  • 1 <= E <= 104
  • 0 <= adj[i][j] < V
  • Graph is connected and 0-indexed

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the recursive depth-first traversal paradigm on graphs.
  • Understand cycle prevention with a boolean visited array.
  • Implement both recursive DFS and explicit LIFO stack iterative DFS.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Explore paths deeply before exploring siblings
  • Cycle detection, topological sort, connected components
  • Backtracking on state graphs or mazes

Algorithmic Decision Tree:

  • If need to search all paths, detect cycles, or evaluate topological order -> Use DFS.
  • If need shortest path in unweighted graph -> Use BFS instead.

Connected Patterns:

Breadth First SearchDetect Cycle in Undirected GraphNumber of Connected Components

1. Iterative DFS Using Explicit Stack

Intuition

Push vertex 0 onto a stack. While the stack is non-empty, pop the top node. If not visited, mark it visited, add to result, and push all its neighbors in reverse order (to maintain left-to-right exploration).

Algorithm

  1. Initialize visited array of size V to false.
  2. Push source vertex 0 onto stack.
  3. While stack is not empty:
  4. Pop vertex u from stack.
  5. If visited[u], continue.
  6. Mark visited[u] = true and append u to result.
  7. Iterate neighbors of u in reverse order and push unvisited neighbors onto stack.
  8. Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <stack>
4
5class Solution {
6public:
7 std::vector<int> dfsOfGraph(int V, std::vector<std::vector<int>>& adj) {
8 std::vector<bool> visited(V, false);
9 std::vector<int> result;
10 std::stack<int> st;
11
12 st.push(0);
13
14 while (!st.empty()) {
15 int u = st.top();
16 st.pop();
17
18 if (visited[u]) continue;
19 visited[u] = true;
20 result.push_back(u);
21
22 for (int i = (int)adj[u].size() - 1; i >= 0; --i) {
23 int v = adj[u][i];
24 if (!visited[v]) {
25 st.push(v);
26 }
27 }
28 }
29 return result;
30 }
31};
32
33int main() {
34 Solution sol;
35 std::vector<std::vector<int>> adj = {{2, 3, 1}, {0}, {0, 4}, {0}, {2}};
36 std::vector<int> res = sol.dfsOfGraph(5, adj);
37 std::cout << "Iterative DFS: ";
38 for (int x : res) std::cout << x << " ";
39 std::cout << "\nExpected: 0 2 4 3 1\n";
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(V + E)
  • Space complexity: O(V)

2. Recursive DFS with Global State Class

Intuition

Encapsulating traversal state as member variables avoids passing visited arrays and result vectors across recursive stack frames.

Algorithm

  1. Declare class members visited[] and result.
  2. Initialize visited to false and clear result.
  3. Define dfs(u):
  4. Mark visited[u] = true.
  5. result.push_back(u).
  6. For neighbor v in adj[u]:
  7. If !visited[v]: dfs(v).
  8. Call dfs(0) and return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5 std::vector<bool> visited;
6 std::vector<int> result;
7
8 void dfs(int u, const std::vector<std::vector<int>>& adj) {
9 visited[u] = true;
10 result.push_back(u);
11
12 for (int v : adj[u]) {
13 if (!visited[v]) {
14 dfs(v, adj);
15 }
16 }
17 }
18public:
19 std::vector<int> dfsOfGraph(int V, std::vector<std::vector<int>>& adj) {
20 visited.assign(V, false);
21 result.clear();
22 dfs(0, adj);
23 return result;
24 }
25};
26
27int main() {
28 Solution sol;
29 std::vector<std::vector<int>> adj = {{2, 3, 1}, {0}, {0, 4}, {0}, {2}};
30 std::vector<int> res = sol.dfsOfGraph(5, adj);
31 std::cout << "Member-State DFS: ";
32 for (int x : res) std::cout << x << " ";
33 std::cout << "\nExpected: 0 2 4 3 1\n";
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(V + E)
  • Space complexity: O(V)

3. Canonical Functional Recursive DFS

Intuition

The canonical graph DFS pattern. A pure recursive function marks the current node, appends to the result, and loops through unvisited neighbors.

Algorithm

  1. Initialize boolean visited array of size V to false.
  2. Create result vector.
  3. Define dfs(node, adj, visited, result):
  4. Mark visited[node] = true.
  5. result.push_back(node).
  6. For each neighbor in adj[node]:
  7. If !visited[neighbor]: dfs(neighbor, adj, visited, result).
  8. Invoke dfs(0, ...).
  9. Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5 void dfs(int u, const std::vector<std::vector<int>>& adj, std::vector<bool>& visited, std::vector<int>& result) {
6 visited[u] = true;
7 result.push_back(u);
8
9 for (int v : adj[u]) {
10 if (!visited[v]) {
11 dfs(v, adj, visited, result);
12 }
13 }
14 }
15public:
16 std::vector<int> dfsOfGraph(int V, std::vector<std::vector<int>>& adj) {
17 std::vector<bool> visited(V, false);
18 std::vector<int> result;
19 dfs(0, adj, visited, result);
20 return result;
21 }
22};
23
24int main() {
25 Solution sol;
26 std::vector<std::vector<int>> adj = {{2, 3, 1}, {0}, {0, 4}, {0}, {2}};
27 std::vector<int> res = sol.dfsOfGraph(5, adj);
28 std::cout << "Canonical DFS: ";
29 for (int x : res) std::cout << x << " ";
30 std::cout << "\nExpected: 0 2 4 3 1\n";
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(V + E)
  • Space complexity: O(V)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Iterative DFS with Explicit StackO(V + E)O(V)Simulates recursion using an explicit LIFO stack.Explicit stack management
2.Recursive DFS with Member StateO(V + E)O(V)Encapsulates visited array and result list as class fields.Recursion call-stack depth
3.Canonical Functional Recursive DFSOptimalO(V + E)O(V)Pure recursive helper with visited and result passed by reference.Recursion depth on path graphs

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Forgetting to mark visited[u] = true upon entering the function, causing infinite recursion on cyclic graphs.

Pitfall 2:

Using an unmemoized search or passing visited array by value in C++ (creating O(V) copies per step).

Pitfall 3:

Assuming DFS always finds the shortest path (that is a property of BFS, not DFS).

Crucial Edge Cases to Validate:

  • Single node graph (V = 1, adj = [[]]) — Visits node 0 and returns [0] immediately.
  • Graph with self-loops or cycles — The visited boolean check prevents re-entering already visited vertices, preventing infinite recursion.
  • Linear chain graph (0 - 1 - 2 - ... - V-1) — Recursion stack reaches depth V. Handled cleanly within stack limit for V <= 104.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Differentiate BFS and DFS clearly: BFS explores layer-by-layer (shortest paths), while DFS explores path-by-path (connectivity, cycles, topological sorting).
  2. Be ready to implement both recursive and iterative stack versions on the whiteboard.
  3. Mention recursion stack depth limits and when an explicit stack is preferred in production systems.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the maximum recursion depth of DFS on a graph with V vertices?

2.Why must neighbors be pushed in reverse order when implementing iterative DFS with an explicit stack?

3.How does DFS handle disconnected graphs containing multiple components?

Back to DSA Sheet