visual-cs / Topological Sort

← All visualizations

Preset Graphs

Speed 5

Vertices

Processing

—

Queue Size

Result Size

Phase

Ready

DAG

Queue (zero in-degree)

Empty

Topological Order (result)

—

Kahn's Algorithm

function kahnSort(graph):

compute inDegree[] for all v

queue = [v | inDegree[v] == 0]

result = []

while queue not empty:

u = queue.dequeue()

result.push(u)

for each neighbor w of u:

inDegree[w] -= 1

if inDegree[w] == 0:

queue.enqueue(w)

if len(result) < V:

return "cycle detected!"

return result

In-Degree Table

Legend

Unvisited

In queue (zero in-degree)

Currently processing

Done / added to result

Cycle detected

Step Log

How It Works

Kahn's Algorithm uses BFS to produce a topological ordering of a DAG.

1. Compute inDegree[v] for all vertices.
2. Enqueue all vertices with inDegree = 0.
3. Dequeue u, append to result, decrement neighbors' in-degrees. If any reach 0, enqueue them.
4. If |result| < V, a cycle exists.

Complexity: O(V + E) time, O(V) space.