Published by Dimitris Kougioumtzis · Updated
Remove zero-indegree vertices from a directed acyclic graph.
Remove zero-indegree vertices and update their neighbors; each emitted vertex precedes its dependents.
When to use Topological sort (Kahn)
Ordering tasks with acyclic prerequisites.
Choosing an alternative
SCC analysis identifies cyclic dependency groups.
Worked example: input and state changes
Example input
0,1,4; 0,2,2; 2,1,1; 1,3,5; 2,3,8; 3,4,2
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Initial graph.
State at this checkpoint
{ "values": [ "∞", "∞", "∞", "∞", "∞" ], "active": [], "kind": "graph", "visited": [], "chosen": [] }Step 3: Decrement indegree of 1.
State at this checkpoint
{ "values": [ 0, 1, 1, 2, 1 ], "active": [ 1 ], "kind": "graph", "visited": [ 0 ], "chosen": [] }Step 7: Decrement indegree of 3.
State at this checkpoint
{ "values": [ 0, 0, 0, 1, 1 ], "active": [ 3 ], "kind": "graph", "visited": [ 0, 2 ], "chosen": [] }Step 10: Remove zero-indegree node 3.
State at this checkpoint
{ "values": [ 0, 0, 0, 0, 1 ], "active": [ 3 ], "kind": "graph", "visited": [ 0, 2, 1, 3 ], "chosen": [] }Step 13: Topological order: 0 → 2 → 1 → 3 → 4.
State at this checkpoint
{ "values": [ 0, 0, 0, 0, 0 ], "active": [], "kind": "graph", "visited": [ 0, 2, 1, 3, 4 ], "chosen": [] }
Expected final state
Topological order: 0 → 2 → 1 → 3 → 4.
Complexity and input bounds
Family: Graphs. Time complexity: O(V + E).
Implementation detail: The standard adjacency-list bound is O(V + E). The downloadable edge-array scan version uses O(V + VE) time.
Space complexity: O(V) indegrees and queue.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
Directed edges as source,target,weight; separated by semicolons. Nodes 0–7, positive weights 1–99. Start node is 0.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
If fewer than V vertices are emitted, the partial sequence is not a full topological order.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | // Directed edge arrays from, to, weight; nodes 0..vertices-1; source 0. Up to 8 vertices, 16 edges. Allocate output with at least 256 integers. Writes topological order; returns count, or -1 for a cycle. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(from, to, weight, edges, vertices, output) { let degree = Array(256).fill(0); let queue = Array(256).fill(0); for (let i = 0; i < edges; i++) { degree[to[i]]++; } let head = 0; let tail = 0; let count = 0; for (let v = 0; v < vertices; v++) { if (degree[v] == 0) { queue[tail++] = v; } } while (head < tail) { let u = queue[head++]; output[count++] = u; for (let i = 0; i < edges; i++) { if (from[i] == u) { degree[to[i]]--; if (degree[to[i]] == 0) { queue[tail++] = to[i]; } } } } if (count != vertices) { return -1; } return count; } |
Source
Primary research source for the algorithm or its underlying method. The playground is a bounded teaching implementation, not the publication's original program.
- Topological sorting of large networks
A. B. Kahn (1962). Research paper.