Skip to main content

DSAPath9 mincore

Depth-First Search

Depth-first search follows one path as far as possible before backtracking. DFS exposes reachability, connected components, cycle structure, topological order, and recursive graph structure.

Why This Matters

DFS is the graph version of following a thread. It is the default tool for reachability, maze search, connected components, cycle detection, topological sorting, and backtracking.

Core Idea

DFS can be recursive or stack-based. Visit a vertex, recursively visit each unvisited neighbor, then return.

Worked example: in a dependency graph, DFS can detect a cycle by tracking nodes currently on the recursion stack. Seeing the same active node again means a circular dependency exists.

Common Mistakes

  • Forgetting a visited set. Cycles can cause infinite recursion.
  • Using DFS when shortest unweighted distance is required. BFS gives that guarantee.
  • Blowing the call stack on very deep graphs. Use an explicit stack when depth is large.

Exercises

  • Trace DFS on a triangle graph and show where the visited set prevents looping.
  • Explain how DFS differs from BFS on the same graph.
  • Use DFS timestamps to sketch a topological sort.

Next Topics

References

  • Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Ch. 20.
  • Sedgewick and Wayne. Algorithms (4th ed., 2011). Ch. 4.