Directed Acyclic Graph
A directed graph with no cycles, which is exactly when a topological order exists.
Topological Sort: Kahn's algorithm
Topological order: 0, 1, 2, 3, 5, 4. Every edge now points from an earlier position to a later one. Each vertex was placed once and each edge lowered one count: O(V + E).
Cost
- Topological sort
- O(V + E)
- Space
- O(V + E)
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Topological Sort covers these too, in the same run.