Topological Sort (Kahn's algorithm)

Order the nodes of a directed graph so every edge points forwards — build order, course prerequisites, task scheduling. Repeatedly take a node nothing depends on, and remove it. If anything is left over, the graph had a cycle.

time O(V + E)

space O(V)

Input

Press Tab out of the box or click Resetto regenerate frames from the current input.

Visualization

No frames yet — edit input and click Run.

—

Pseudocode

indegree[v] = number of edges into v
queue = all v with indegree 0
while queue:
  u = queue.pop(); output.append(u)
  for v in neighbours(u):
    indegree[v] -= 1
    if indegree[v] == 0: queue.append(v)
if output.length < V: there is a cycle