CSCI2100 · Theorem · Chapter 13 · Graph traversal
Topological order from finish times
4 steps of prerequisites below it
In an acyclic directed graph, listing vertices in decreasing order of DFS finish time gives a topological order.
Taught in
- 13.2 Graph representations and depth-first search · introduced
Uses
- Cycles and back arcs · used in its proof, proof step 13.2
- Topological order · used in its definition, passage 13.2
Used by
No later knowledge point in these notes uses it.
Counterexamples
Everything this builds on, earliest first · 5 steps
Each step comes after its own prerequisites, so reading in this order never needs something you have not met. It is a reading order for these notes, not a diagnosis of what you know.
- Adjacency matrix and adjacency lists · 13.2
- Depth-first search · 13.2
- Edge classification · 13.2
- Cycles and back arcs · 13.2
- Topological order · 13.2
Possible roots and a review route need your own answers on these points. None are recorded yet, so none are suggested.
Longest chain down to a starting point
Each step is used by the one above it, across courses where the notes link them. It ends at a point the notes define without another point.