Topological sort: ordering directed graphs · 3 of 3
Cycle detection
See why a directed cycle rules out every order, find and print one with a DFS that tracks unseen, active and finished vertices, and get a topological order from the same search.
Books1
Links3
- Topological Sorting The DFS method by exit times with a short C++ implementation and a list of practice problems. cp-algorithms.com (opens in a new tab)
- Lecture 10: Depth-First Search Proves that reversed DFS finishing order is a topological order and uses the same search for cycle detection. ocw.mit.edu (opens in a new tab)
- Algorithms, Chapter 6: Depth-first search Sections 6.1 to 6.3: the new, active and finished states of a depth-first search, why the active vertices always form a path, a linear-time test for cycles, and a topological order from the reversed postorder. 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)