Algorithms

DFS: Depth-First Search

Цели урока

  • Understand the difference between DFS and BFS
  • Implement both recursive and iterative DFS
  • Apply DFS for path finding and cycle detection
  • Understand discovery/finish times

Предварительные знания

  • Stack
  • Graph representation

How do you escape a maze without a map? Walk forward until a dead end, then back to the last fork. This intuitive method is the foundation of DFS, one of two fundamental graph traversal algorithms.

  • Compilers: module dependency analysis
  • Games: maze generation
  • AI: game trees (minimax)
  • Web crawlers: following links depth-first

Trémaux's maze rule and the Hopcroft-Tarjan era

The depth-first idea predates computers. In the 19th century the French engineer Charles Pierre Trémaux worked out a rule for solving mazes by hand: mark every passage on each pass, never take a fully marked passage twice, and back up once the fresh corridors run out. Édouard Lucas published the method in his Récréations Mathématiques around 1882. That is DFS with edge marking, decades before any machine could run it. The algorithm became central to computer science in the early 1970s, when John Hopcroft and Robert Tarjan turned DFS into a precision tool. Their 1973 work showed that a single DFS pass, augmented with discovery and finish times, solves a whole family of graph problems in linear time: biconnected components, bridges and articulation points, and planarity testing. Tarjan's 1972 strongly connected components algorithm and the topological sort by finish time both fall straight out of the same traversal. What had been a maze trick became the backbone of graph theory in practice.

0

1

Sign In

Idea: Go Deep First

**You're exploring a cave.** You walk forward along a corridor until you hit a dead end. Then you backtrack to the last junction and try another path. That's DFS - Depth-First Search.

**The key structure is a stack (Stack).** Recursion is an implicit call stack, so DFS is naturally implemented recursively.

**BFS = queue (Queue), DFS = stack (Stack or recursion).** This is the only difference in the code!

DFS vs BFS: in what order will vertices be visited in a linear graph A→B→C→D?

DFS Implementation

**Recursive version (simpler):**

**Iterative version (with a stack):**

VersionProsCons
RecursiveClean code, naturalStack overflow at depth > 1000
IterativeNo depth limitMore complex code

**Python recursion limit:** ~1000. For large graphs use the iterative version or `sys.setrecursionlimit()`.

What is the difference between BFS code and iterative DFS code?

Applications of DFS

**1. Path existence check:**

**2. Cycle detection:**

**3. Count connected components:**

**4. Flood Fill:**

For finding the SHORTEST path, it's better to use:

Discovery and Finish Times

**Advanced technique:** record the discovery and finish time for each vertex.

**Applications of timestamps:**

  • **Topological sort:** finish DESC
  • **Finding bridges and articulation points**
  • **Edge classification:** tree, back, forward, cross
  • **Strongly Connected Components (SCC)**

**Bracket structure:** intervals [discovery, finish] are either nested or non-overlapping. They never partially overlap.

DFS finds the shortest path between two vertices - just remember the first path it discovers.

DFS only guarantees that a path exists; its length depends on neighbour ordering. For shortest paths in an unweighted graph the right tool is BFS.

On small examples DFS frequently does return a short path, which builds false intuition. The moment branching appears with a long 'wrong' subtree, DFS descends all the way down before backtracking and accumulates a long route.

If discovery[A]=1, finish[A]=10, discovery[B]=3, finish[B]=7, then:

DFS - Depth-First Search

  • Go deep until stuck, then backtrack
  • Uses Stack (or recursion)
  • O(V + E) time, O(V) memory
  • Does NOT guarantee shortest path
  • Foundation for: topological sort, cycle detection, SCC

Вопросы для размышления

  • Which everyday problem follows the same 'go forward, hit a wall, back up to the last fork' template that DFS encodes - and what does that say about why the algorithm feels natural?
  • On a graph with 10000 vertices containing a chain of length 5000, what breaks in a recursive Python DFS, and why does the iterative stack-based form become mandatory there?
  • Memoized DFS collapses into DP. In which problems does this equivalence dissolve the line between graph traversal and dynamic programming?

Related Topics

DFS is the foundation for many algorithms.

  • BFS — Alternative traversal (Queue)
  • Topological Sort — Based on DFS

Связанные уроки

  • alg-12-bfs — BFS is the alternative traversal, difference is essential
  • alg-18-topological — Topological sort is built on DFS
  • alg-17-mst — DFS finds connected components for MST algorithms
  • alg-21-dp — Memoized DFS is DP on a graph
  • calc-01-sequences — DFS recursion unrolls like a sequence of calls
  • ds-16-graphs-intro — Graph structure is the foundation of DFS
  • comp-20-semantic-passes
  • comp-18-type-checking
  • plt-04-type-inference
  • ml-11-decision-trees
DFS: Depth-First Search