Kahn's Algorithm
Repeatedly place a vertex with in-degree zero and lower the counts of everything it points to.
Topological Sort: Kahn's algorithm
Place 0, position 1. Its edges to 1, 2 are satisfied, so their counts drop. 1, 2 reached 0 and are ready.
Cost
- Best
- O(V + E)
- Average
- O(V + E)
- Worst
- O(V + E)
- Space
- O(V)
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.