Unit 3.3 · about 4 h
106 / 324DFS, cycle detection and bipartite testing
DFS supplies the recursion structure BFS cannot: finish times, edge classification and back-edge witnesses. Cycles and two-coloring are its first two customers.
- derive
- implement
You can now
- Implement recursive and iterative DFS with pre-order, post-order and on-stack hooks, and derive the \(\Theta(V + E)\) bound.
- Detect directed cycles with three-color DFS and undirected cycles with parent-tracking DFS, and exhibit the false positive each wrong pairing produces.
- Test bipartiteness with two-color BFS or DFS and explain the odd-cycle obstruction.
Covers
- DFS state, timestamps and recursive versus iterative traversal
- Cycle detection in directed and undirected graphs
- Bipartite testing and two-color invariants
Study, in this order
4 steps
- Depth-first searchDSA Handbook - graphs
The recursive form; Three flavors: pre-order, post-order, on-stack; Worked example: LC 130 Surrounded Regions; Two pitfalls that bite
- Cycle detection in graphsDSA Handbook - graphs
Why the obvious approach reports cycles that are not there (diamond); The other half: undirected graphs need a parent argument; Worked example: LC 1361
Depth · Skim the Floyd tortoise-and-hare pointer; it belongs to linked lists, not graphs.
- Bipartite checkDSA Handbook - graphs
Why the obvious approach wastes most of its work; The pattern (LC 785); Worked example on a 4-cycle and a triangle
- Depth-first search through cycle detectionAlgorithms - graph chapters
Sections 6.1 Preorder and Postorder (with Classifying Vertices and Edges) and 6.2 Detecting Cycles (printed pp. 227-232)
Focus on
- Mark before recursing, on entry. Recursing first lets the neighbor immediately recurse back, which loops until
RecursionError. GRAYmeans on the current stack;BLACKmeans finished. The diamond edge into aBLACKvertex is a benign forward edge; only aGRAYneighbor is a back edge and a cycle witness.- Undirected DFS needs one boolean plus the
parentargument: the neighbor you arrived from does not count. Three colors are unnecessary there because undirected DFS has no forward or cross edges. - Bipartite colors are 1 and -1 with 0 for unvisited, flipped by negation across each edge, inside an outer loop over components. A same-color edge is the odd-cycle witness.
Reproduce closed-book
[(0,1),(0,2),(1,3),(2,3)] and report no cycle, and on [(0,1),(1,2),(2,0)] report a cycle. Then run two-color BFS on [[1,3],[0,2],[1,3],[0,2]] (True) and on [[1,2],[0,2],[0,1]] (False).Traps
- Two-color directed DFS: the diamond reports a cycle because one visited bit conflates on-stack with finished. The fix is the third color, not a second visited set.
- Parentless undirected DFS: a single edge reports a cycle because each endpoint sees the other as visited. The fix is the
parentargument, not more colors. - Recursive DFS on deep grids or chains: CPython caps the stack at 1000 frames by default (check with
sys.getrecursionlimit), so a snake region or a 2000-chain crashes. Set the limit explicitly or ship the iterative form.
Practice
LeetCode 130: Surrounded Regions
The two listed examples (\(4 \times 4\) board with two interior O cells flipping; single-cell board)
Pre-order DFS from every border O, marking first and recursing second. After-attempt reference is the DSA Handbook 8.2 worked example.
LeetCode 785: Is Graph Bipartite?
Examples 1 (triangle inside, False) and 2 (4-cycle, True)
Two-color BFS with the outer component loop. After-attempt reference is the DSA Handbook 8.7 worked example.
Self-test
-
Prove a directed graph is acyclic iff DFS finds no back edge.
If a back edge \((u, v)\) exists, \(v\) is an ancestor of \(u\), so the tree path from \(v\) to \(u\) plus the edge closes a cycle. Conversely, if a cycle exists, let \(v\) be its first vertex DFS discovers. Every other cycle vertex is still white then, so each becomes a descendant of \(v\), and the cycle edge from \(v\)'s predecessor \(u\) back to \(v\) reaches \(v\) while \(v\) is still GRAY: a back edge. -
Prove a graph is bipartite iff it has no odd cycle.
If 2-colored, any cycle alternates colors and must return to its start color after an even number of steps, so all cycles are even. If no odd cycle exists, BFS two-coloring never assigns the same color to both ends of an edge: a conflict would close an odd cycle through the BFS tree, contradiction. -
Why does the bipartite outer loop cost nothing on connected graphs?
Every later start is already colored, so each trips thecontinueimmediately: \(O(V)\) checks total. Skipping the loop misses odd cycles hiding in unvisited components. -
LC 130 floods from the border instead of testing each region. Why is the inversion sound?
Border-connected regions are exactly the ones to keep; DFS marks all of them, so every unmarked O is surrounded by construction. Testing from inside cannot see the border without the same outward walk.
Completion criterion
Stop when
Your blank-file script prints the four reproduce verdicts (no cycle, cycle, True, False), and LC 130 plus LC 785 pass with the visited discipline stated up front.
Leads to
- 3.4 Topological ordering and strongly connected components Put post-order finish times and back-edge witnesses to work: orderings and strongly connected components.
- 3.5 Union-find with path compression and union by rank Meet the other cycle-detection engine, for edges that arrive one at a time.
Comes after
- 3.2 BFS, unweighted shortest paths and connected componentsSwap the queue for a stack and trade the layer guarantee for recursion structure: entry hooks, exit hooks and back edges.
Resources for this unit
- DSA Handbook - graphs Study all of Part 8 in order. For each algorithm, write the representation, invariant, forbidden input assumptions and independently checkable output before reading the implementation.
- Algorithms - graph chapters Use the basic graph, depth-first search, minimum spanning tree, shortest path and flow chapters, and lecture note 11 Disjoint Sets for union-find, for correctness proofs and counterexamples to tempting wrong algorithms.
Also in this section
- AlgoMaster DSA - graph slice Attempt Number of Islands, Course Schedule II and Network Delay Time cold. They cover traversal, dependency modeling and weighted shortest paths; add one narrative problem only if graph modeling remains weak.
- Hypothesis - generated graph tests Generate small sparse, dense, disconnected, cyclic, parallel-edge and weighted graphs. Compare optimized results with exhaustive or deliberately simple references and retain shrunk failures.
- NeetCode - unseen graph problems Use two unseen story problems without graph tags. Grade the model, assumptions, certificate and tests as well as the final answer.