A linear ordering of a DAG's nodes such that every directed edge u→v has u before v; only exists if there's no cycle. Two implementations: Kahn's algorithm (BFS with in-degree counting) or DFS with post-order reversal.
Sub-patterns
- A — Kahn's Algorithm. BFS driven by in-degree counting.
- B — DFS-Based Topological Sort. Post-order reversal.
- C — Cycle Detection via a Failed Topo Sort. If a full ordering can't be produced, the graph has a cycle.
Practice set (5)
- Medium — Course Schedule, Course Schedule II, Minimum Height Trees, Course Schedule IV
- Hard — Alien Dictionary (Premium)
Pending
Kahn's Algorithm
BFS driven by in-degree counting — repeatedly peel off nodes with no remaining incoming edges.
Pending
DFS-Based Topological Sort
Run DFS and reverse the post-order finish times to get a valid ordering.
Pending
Cycle Detection via a Failed Topo Sort
If a full ordering can't be produced, the graph has a cycle — the failure itself is the answer.
Notes from readers
Comments — via GitHub