Directed Acyclic Graph
A directed graph with no cycles, which is exactly when a topological order exists.
Decision · step 2 of 8Topological 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.
What you will see
Vertices arranged left to right so all arrows point forward.
Cost
| topological sort | O(V + E) |
|---|---|
| Space | O(V + E) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.
Screen readers: Each element is an accessibility element with position, value and state; structural changes are announced per step.
Reduced motion: Elements appear at their destination with a crossfade; no travel longer than the element's own size.
Before this
Taught by the same lesson
Topological Sort covers these too, in the same run.