Overview
Topological sort orders vertices in a DAG so every edge points from earlier to later in the sequence.
Analogy
Course prerequisites: you must take Calculus before Linear Algebra.
Step-by-step
- Kahn's BFS: count in-degrees; push 0-in-degree nodes; process, decrement neighbors.
- DFS post-order: run DFS; push node to result stack after all descendants are finished.
- Reverse the DFS stack to get topological order.
- If cycle exists, Kahn's algorithm won't process all nodes.
Visual
DAG: A→B→C, A→C. In-degrees: A=0,B=1,C=2. Process A→B→C.
Common mistakes
- Running on a graph with cycles (result would miss nodes or be invalid).
- Not detecting cycle (cycle = not all nodes processed in Kahn's).
Practice questions
- Find a build order given a list of dependencies.
- Detect if a course schedule is feasible.
AI Wisdom