Unit 3.4 · about 4 h
107 / 324Topological ordering and strongly connected components
Dependency order is the scheduling primitive: builds, courses, task graphs. The same DFS skeleton that orders a DAG also carves directed graphs into strongly connected components.
- derive
- implement
You can now
- Implement Kahn's algorithm and DFS post-order topological sort, each with its cycle witness, and derive the \(\Theta(V + E)\) bound.
- Prove post-order-then-reverse is a topological order from the finish-time invariant.
- Implement Kosaraju's strongly connected components and explain the reverse-graph second pass.
Covers
- Topological ordering and dependency cycles
- Strongly connected components
Study, in this order
3 steps
- Topological sort: Kahn's algorithmDSA Handbook - graphs
What Kahn's actually does; The algorithm (LC 207); Worked example on the 6-course catalog; Reverse-graph Kahn for safe nodes (LC 802)
- Topological sort: DFS post-order reverseDSA Handbook - graphs
Why two colors are not enough; The algorithm; Walking the canonical DAG; Why post-order, then reverse, is correct; Picking between Kahn and DFS
- Topological sort and strong componentsAlgorithms - graph chapters
Section 6.3 Topological Sort with Implicit Topological Sort; Sections 6.5 Strong Connectivity and 6.6 Strong Components in Linear Time, Kosaraju and Sharir's algorithm (printed pp. 232-234 and 237-244; Tarjan's algorithm is optional)
Focus on
- Pin the edge convention in a comment:
[a,b]means \(b\) is the prerequisite, so the edge is \(b \to a\). Inverting it turns DAGs into cycles. - Kahn detects the cycle only at termination: emitted count equal to \(V\) means DAG, fewer means the leftovers sit on cycles. No early return inside the loop.
- DFS emits each vertex after all successors finish, so finish times decrease along every edge; reversing puts producers first. A
GRAYsuccessor aborts with a cycle. - Kosaraju finishes SCCs in topological order on the first pass, then walks the reversed graph from the latest-finishing component, which cannot escape its own SCC.
Reproduce closed-book
[[1,0],[2,0],[3,1],[3,2],[4,2],[5,3],[5,4]] and emit a valid order such as [0,1,2,3,4,5] (check every \(b\) precedes its \(a\)); on [[1,0],[0,1]] emit 0 of 2 and report a cycle. Then run Kosaraju on [(0,1),(1,2),(2,0),(2,3),(3,4)] and report components [0,0,0,1,2].Traps
- Counting indegrees from one edge collection and decrementing from another, such as a deduplicated set against the raw list with duplicate prerequisites: counts go negative or never reach zero. Count and decrement from the same list, and enqueue exactly when a count reaches 0.
- Returning the post-order list unreversed: it holds consumers before producers, the exact opposite of the graded order.
- Running DFS from vertex 0 only: cycles in other weakly connected components are missed. The outer white-check loop is mandatory, as is the
GRAY-to-BLACKflip on exit.
Practice
LeetCode 210: Course Schedule II
Examples 1 to 3 (2 courses [[1,0]]; 4 courses [[1,0],[2,0],[3,1],[3,2]]; single course with no prerequisites)
Attempt cold per the AlgoMaster pool note, in either Kahn or DFS framing, then implement the other framing and compare orders. After-attempt reference is DSA Handbook 8.4 (Kahn) and 8.5 (post-order).
LeetCode 802: Find Eventual Safe States
The two listed examples (7-node graph with two safe terminals; 5-node graph)
Reverse-graph Kahn from terminal vertices, or three-color DFS; state which witness you report. After-attempt reference is the reverse-graph section of DSA Handbook 8.4.
Self-test
-
Prove post-order-then-reverse is a topological order.
When DFS exits \(u\), its loop has returned from every successor, so each successor finished earlier: \(\operatorname{finish}[v] < \operatorname{finish}[u]\) for every edge \((u, v)\). Reversing finish-time order therefore places \(u\) before \(v\) on every edge, which is the topological property. -
Prove leftover vertices after Kahn imply a cycle.
Every leftover vertex still has indegree at least one inside the leftover subgraph. Follow any predecessor chain; with finitely many vertices some vertex repeats, and the repeated segment is a directed cycle. -
Why does Kosaraju's second pass stay inside one SCC?
First-pass finish times order SCCs topologically: if SCC \(A\) reaches SCC \(B\), \(A\) finishes later. Processing latest-first on the reversed graph starts each walk in a sink SCC of the reversed graph, whose reachable set is exactly its own SCC. -
Kahn and DFS report different valid orders on the same DAG. Is one wrong?
No. Topological orders are plural: the handbook's 6-node DAG admits several. Kahn breaks ties by queue order, DFS by recursion shape; both respect every edge.
Completion criterion
Stop when
Your blank-file script prints a valid 6-course order, the 0-of-2 cycle verdict and the [0,0,0,1,2] component labels, and you can defend the Kahn-versus-DFS choice on operational grounds (iteration and lex order versus post-order computation).
Leads to
- 5.9 Dynamic programming as shortest paths, formulations and limits Topological order is the evaluation order for DP on DAGs; carry it into recurrence dependencies.
- 3.6 Dijkstra, Bellman-Ford and negative cycles DAG shortest paths relax vertices in topological order, which is why order comes before weights.
Comes after
- 3.3 DFS, cycle detection and bipartite testingPut post-order finish times and back-edge witnesses to work: orderings and strongly connected components.
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.