GraphsLesson 4

DFS — Recursive

Explore a graph by going as deep as possible before backtracking. The recursive implementation — clean, elegant, and easy to understand.

What Is It?

Depth-First Search (DFS) explores a graph by going as deep as possible down one path before backing up and trying another path.

Start at a node. Visit one of its neighbors. Then visit one of that neighbor's neighbors. Keep going deeper until you hit a dead end (a node with no unvisited neighbors). Then back up and try the next path.

The recursive version is the most natural way to write DFS. The function calls itself for each unvisited neighbor, and the computer automatically keeps track of where to go back.

Analogy

You are exploring a maze. At every fork, you always take the first unexplored path and keep walking. When you hit a dead end, you backtrack to the last fork that had untried paths, and take the next one. You keep going until you have explored every corridor.

You go deep first — that is what makes it "depth-first." Compare this to BFS, which would take one step in every direction before taking two steps anywhere.

How It Works

Same graph as the BFS lesson — so you can compare the two traversal orders directly:

pseudocode
1
2
3
    0 --- 1 --- 2
    |           |
    3 --- 4 --- 5

Adjacency List:

pseudocode
1
2
3
4
5
6
  0: [1, 3]
  1: [0, 2]
  2: [1, 5]
  3: [0, 4]
  4: [3, 5]
  5: [2, 4]

DFS Pseudocode

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function DFS(graph, numNodes):
    visited = empty set
​
    for v from 0 to numNodes - 1:
        if v not in visited:
            DFS_visit(graph, v, visited)
​
function DFS_visit(graph, node, visited):
    visited.add(node)
    process(node)              // e.g., print it
​
    for each neighbor in graph[node]:
        if neighbor not in visited:
            DFS_visit(graph, neighbor, visited)

The outer function handles disconnected graphs. DFS_visit does the actual recursive work.

Step-by-Step Trace (starting from node 0)

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
Call DFS_visit(0)
  Visit 0. Neighbors: 1, 3
  1 not visited -> recurse
​
  Call DFS_visit(1)                     depth 1
    Visit 1. Neighbors: 0, 2
    0 already visited.
    2 not visited -> recurse
​
    Call DFS_visit(2)                   depth 2
      Visit 2. Neighbors: 1, 5
      1 already visited.
      5 not visited -> recurse
​
      Call DFS_visit(5)                 depth 3
        Visit 5. Neighbors: 2, 4
        2 already visited.
        4 not visited -> recurse
​
        Call DFS_visit(4)               depth 4
          Visit 4. Neighbors: 3, 5
          3 not visited -> recurse
​
          Call DFS_visit(3)             depth 5
            Visit 3. Neighbors: 0, 4
            0 already visited.
            4 already visited.
            Return.
​
          Back in DFS_visit(4).
          5 already visited.
          Return.
​
        Back in DFS_visit(5). Return.
      Back in DFS_visit(2). Return.
    Back in DFS_visit(1). Return.
  Back in DFS_visit(0).
  3 already visited.
  Return.
​
Processing order: 0, 1, 2, 5, 4, 3

BFS order was: 0, 1, 3, 2, 4, 5. Completely different!

DFS dove deep immediately: 0 → 1 → 2 → 5 → 4 → 3. BFS spread out level by level.

The Recursion Call Tree

pseudocode
1
2
3
4
5
6
7
8
9
10
11
        DFS(0)
          |
        DFS(1)
          |
        DFS(2)
          |
        DFS(5)
          |
        DFS(4)
          |
        DFS(3)

DFS goes all the way down one branch before coming back up. Each call waits for the call below it to finish.

Time: O(V + E) — every node is visited once, every edge is looked at once.

Space: O(V) — the visited set, plus the recursion stack which can go as deep as V in the worst case.

Detecting Cycles with DFS

In an undirected graph: A cycle exists if you visit a neighbor that is already visited and that neighbor is NOT the node that just called you.

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function hasCycle(graph, numNodes):
    visited = empty set
​
    for v from 0 to numNodes - 1:
        if v not in visited:
            if DFS_cycle(graph, v, -1, visited):
                return true
    return false
​
function DFS_cycle(graph, node, parent, visited):
    visited.add(node)
​
    for each neighbor in graph[node]:
        if neighbor not in visited:
            if DFS_cycle(graph, neighbor, node, visited):
                return true
        else if neighbor != parent:
            return true      // found a back edge — that's a cycle!
​
    return false

Examples

Counting Connected Components

pseudocode
1
2
3
4
5
6
7
8
9
10
function countComponents(graph, numNodes):
    visited = empty set
    count = 0
​
    for v from 0 to numNodes - 1:
        if v not in visited:
            DFS_visit(graph, v, visited)
            count = count + 1
​
    return count

Every time the outer loop finds an unvisited node, a new DFS starts — meaning we found a new connected component.

Common Mistakes

  1. Forgetting to check if a neighbor is visited before recursing. Without this check, the function keeps calling itself on already-visited nodes and loops forever.
  1. Not sharing the visited set across recursive calls. Every call must use the same visited set. If you accidentally create a new one, nodes get re-visited.
  1. Using DFS to find shortest paths. DFS does NOT find shortest paths. The first path it finds may be very long. Use BFS for shortest paths.
  1. Stack overflow on very deep graphs. If your graph is a long chain of 100,000 nodes, recursive DFS will crash. Use iterative DFS (next lesson) for such cases.

Best Practices

  • Use DFS when you need to fully explore a path — cycle detection, connectivity checks, finding all paths.
  • Draw the recursion tree when debugging. It makes the backtracking obvious.
  • Always handle disconnected graphs with the outer loop pattern.
  • Switch to iterative DFS when the graph could be very deep — recursive DFS can crash with a stack overflow.
BFS — Breadth-First SearchDFS — Iterative