Topological Sort
Topological sort orders the vertices of a directed acyclic graph (DAG) such that for every directed edge (u, v), u comes before v. It's used in task scheduling, build systems, and dependency resolution.
Topological Sort Visualization
How to use: Click empty space to add a vertex. Click a vertex then another to add a directed edge. Drag to reposition. Right-click to delete.
SlowFast
🔊 Sound
Ready
● Active (DFS enter)● Visiting (on stack)● Finished● Cycle edge● Selected
DFS Call Stack
empty
Topological Order
—
Node States
Complexity
Time Complexity:
O(V + E)Space Complexity:
O(V)Pseudocode
function TopologicalSort(graph):
inDegree = {v: 0 for all v}
for each edge (u, v):
inDegree[v]++
queue = [v where inDegree[v] == 0]
result = []
while queue is not empty:
current = queue.dequeue()
result.append(current)
for each neighbor of current:
inDegree[neighbor]--
if inDegree[neighbor] == 0:
queue.enqueue(neighbor)