AlgoScope

Kahn's Algorithm

Repeatedly place a vertex with in-degree zero and lower the counts of everything it points to.

Connectivity and topological order, algorithm, intermediate
Vertex 0 is placed at position 1. 2 vertices become ready.011020324151u
Vertex 0 is placed at position 1. 2 vertices become ready.011020324151u

Topological Sort: Kahn's algorithm

Decision, step 2 of 8

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)

Leads to

Topics that need this one first.

Taught by the same lesson

Topological Sort covers these too, in the same run.