Topological sort

O(V + E)

A topological sort orders the vertices of a directed acyclic graph (DAG) so that every edge goes from an earlier vertex to a later one — an order in which you could carry out tasks without ever needing one that hasn't been done yet. Kahn's algorithm builds it from in-degrees: start with every vertex that has no incoming edges, output one, then remove its outgoing edges, which may expose new in-degree-zero vertices. The numbers above the nodes track each vertex's remaining in-degree. It runs in O(V + E). If some vertices never reach in-degree zero, the graph contains a cycle and no ordering exists. It powers build systems, task schedulers, and spreadsheet recalculation.

Directed graph
Edit the input and press Play

How it works

  1. Count each vertex's in-degree (incoming edges); the overlay shows it.
  2. Queue every vertex with in-degree 0 — these depend on nothing.
  3. Output one, then decrement the in-degree of each successor.
  4. A successor that hits 0 joins the queue. If any vertex is left over, there's a cycle.

Pseudocode

1topoSort(graph):                    # Kahn — O(V + E)2  indeg[v] ← number of incoming edges3  queue ← all vertices with indeg 04  order ← []5  while queue not empty:6    u ← queue.remove()7    order.append(u)8    for v in successors(u):9      indeg[v] ← indeg[v] − 110      if indeg[v] = 0: queue.add(v)11  if order has every vertex: return order12  else: graph has a cycle