Loading algorithms…

Loading visualizer…

Algorithms/Graph/Topological Sort

Topological Sort

Order the vertices of a directed acyclic graph so every edge points forward. Kahn's in-degree peeling and DFS-based post-order, side by side.

DAGOrderingQueue/Stack
Mode
Step 1 of 18: Compute every vertex's in-degree (incoming edge count): A=0, B=1, C=1, D=1, E=2, F=2, G=1.
1 / 18
Speed

Compute every vertex's in-degree (incoming edge count): A=0, B=1, C=1, D=1, E=2, F=2, G=1.

Queue (front first)

— empty —

In-degrees

A:0B:1C:1D:1E:2F:2G:1

Topological order (0)

— empty —
topo-kahn.js
1function topoSortKahn(nodes, edges) {
2 const indeg = countIncomingEdges(edges);
3 const queue = nodes.filter(n => indeg[n] === 0);
4 
5 const order = [];
6 while (queue.length) {
7 const u = queue.shift();
8 order.push(u);
9 
10 for (const v of adj[u]) {
11 if (--indeg[v] === 0) queue.push(v);
12 }
13 }
14 
15 return order.length === nodes.length
16 ? order : 'cycle detected';
17}

Click a node to set the DFS start vertex · Drag to rearrange · Step with Space / ← → / Home End / R

About the Topological Sort algorithm

Order the vertices of a directed acyclic graph so every edge points forward. Kahn's in-degree peeling and DFS-based post-order, side by side.

Category
Graph
Difficulty
Medium
Time complexity
O(V+E)
Space complexity
O(V)
←Previous Algorithm
Prim's MST
GraphO(E log V)
Next Algorithm→
Cycle Detection (Directed)
O(V+E)Graph