Topological sort: ordering directed graphs · 2 of 3
Topological sort
Build a topological order with Kahn's algorithm, tell from its length whether one exists, choose among several valid orders, and compute values such as route counts in that order.
- Topological Sort Code for Kahn's algorithm and the DFS method in three languages, a section on printing a cycle, and dynamic programming over a DAG on CSES Longest Flight Route, a close relative of Game Routes. usaco.guide (opens in a new tab)
- 拓扑排序 (Topological sorting) Kahn's algorithm and the DFS method with a correctness proof, the lexicographically smallest order with a heap, and critical paths in activity networks. oi-wiki.org (opens in a new tab)
- Algorithms, Chapter 6: Depth-first search Section 6.3 defines a topological order as a line on which every edge points right, sorts by reversing the order in which a depth-first search finishes, and computes values in topological order without storing the order. Parts of this page adapt this chapter’s text, licensed CC BY 4.0 (creativecommons.org/licenses/by/4.0), with changed wording, examples and code. jeffe.cs.illinois.edu (opens in a new tab)