Lesson 32 / 42

Depth-First Search

Follow one path as deep as possible, then backtrack — natural for recursion.

Go deep, then back up

DFS dives down one branch until it dead-ends, then retreats to the last unexplored fork. Implemented with recursion (the call stack) or an explicit stack. O(V + E).

Recursive DFS

Mark on entry; recurse into unvisited neighbours.

def dfs(g, node, seen=None):
    if seen is None: seen = set()
    seen.add(node)
    for nb in g[node]:
        if nb not in seen:
            dfs(g, nb, seen)
    return seen

What DFS is good at

Detecting cycles, counting connected components, topological sort, path existence, and any exhaustive "try all combinations" search (which is backtracking).

Quick check: You need the shortest path in an unweighted graph. Use...

  • DFS
  • BFS
  • Either works equally
Answer

BFS — BFS explores in order of distance, so the first time it reaches the target is a shortest path. DFS gives no such guarantee.