Topological Sort With Kahn's Algorithm
In the queue
Empty.
Order so far
Nothing yet.
- Not reached
- Waiting
- Current
- Finished
1/21
Count the incoming edges of every node: A=0 B=1 C=1 D=2 E=1 F=1 G=2 H=2.
Settings
Graph
Topological Sort
- 1
count incoming edges per node - 2
queue = nodes with zero incoming - 3
while queue: - 4
node = queue.shift() - 5
output.push(node) - 6
for each neighbour: - 7
incoming[neighbour] -= 1 - 8
if incoming[neighbour] == 0: - 9
queue.push(neighbour)
What Each One Answers
| Algorithm | What it answers | Time | Needs |
|---|---|---|---|
| Breadth-First | Fewest hops from the start | O(V + E) | A queue |
| Depth-First | Reachability, one branch at a time | O(V + E) | A stack |
| Cycle Detection | Whether there is a cycle, and where | O(V + E) | Node colours |
| Topological Sort | A valid order to do the work in | O(V + E) | No cycles |
| Dijkstra | Cheapest path by edge weight | O(E log V) | Non-negative weights |
Scroll the table sideways for the rest of the columns.
V is the number of nodes and E the number of edges. On the graph with a cycle, topological sort gets stuck, because a cycle leaves no valid order.