Topological Sort and Cycle Detection

| Topological sorting is a linear ordering of vertices for Directed Acyclic Graphs (DAGs).

Producing a valid order is called topological sorting, and it is one of the most directly useful algorithms in this section, because the algorithm is the key to products like build plans, scheduling systems, and other things that need order.

When does an order exist?

Before finding an order it is worth asking when one exists, because the answer is clean and it drives the algorithm.

Suppose the graph has a cycle: A before B, B before C, C before A. Any ordering has to put one of the three first, and whichever you pick has something in the cycle that must come before it. So no matter how hard you try you wont find a valid order.

Proving that every DAG has a topological ordering is not as trivial but the key idea is that since there are no cycles, there will always be a source node, and after you add that as the first node in an ordering, you can essentially do the same for all its branches' top node. So the question "can these tasks be scheduled" and the question "is this graph a DAG" are the same question, which is what makes DAGs so useful. In fact, the next page in this section discusses a method of turning a cyclic graph into a DAG, which proves to be useful for using other algorithms.

Deriving the algorithm

Think about what you would do by hand with a real to-do list; you'd look for something with nothing blocking it, do that, cross it off, and notice that crossing it off may have unblocked other things. Then repeat.

That's pretty much the core idea of the algorithm, and it needs only one number per node, how many things are still blocking it, a count called the node's in-degree: the number of edges pointing at it.

A node with in-degree 0 has nothing waiting on it, so it is safe to emit. Emitting it removes its outgoing edges, which lowers the in-degree of everything it pointed at, which may drop some of them to 0 and make them available in turn. Keep a collection of the currently-available nodes so you do not have to rescan for them.

This is Kahn's algorithm, and the pleasant part is the cycle check. You never have to look for a cycle explicitly. If you finish and have emitted fewer nodes than the graph contains, whatever is left is stuck behind something, and stuck means a cycle. The count is the detector.

Example

Same dependencies as the previous page: shirt before tie, shirt before belt, trousers before belt, trousers before shoes, socks before shoes, tie before jacket.

Notice that there were three nodes available at the very start, and the algorithm had to pick one. A different pick gives a different valid order. Topological orders are usually not unique, and a problem that expects one specific answer has to say which tie-break to use. If you need the lexicographically smallest order, make the ready collection a min-heap instead of a plain list, and the rest is unchanged.

The other way to do it

There is a second method worth knowing, because it costs nothing once you have depth-first search and it shows up in a lot of published code.

Run a DFS. When a node finishes, meaning you have fully explored everything reachable from it, push it onto a list. At the end, reverse the list.

The reason that works is worth a moment. A node cannot finish until everything downstream of it has finished, so it always lands earlier in the finish list than its dependents. Reversing puts it after them, which is exactly the ordering you want. Detecting cycles takes one extra piece of state: if the DFS ever meets an edge back to a node that is currently open, meaning you are still inside its call, that is a cycle.

Kahn's version is usually easier to reason about and gives you the cycle check for free. The DFS version is more compact if you already have a DFS in front of you and do not want the in-degree bookkeeping. Both cost O(V + E).

The implementation

function topologicalSort(nodeCount, edges) {
  const adj = Array.from({ length: nodeCount }, () => []);
  const inDegree = new Array(nodeCount).fill(0);

  for (const [before, after] of edges) {
    adj[before].push(after);
    inDegree[after]++;                 // one more thing blocking it
  }

  const ready = [];
  for (let v = 0; v < nodeCount; v++) if (inDegree[v] === 0) ready.push(v);

  const order = [];
  while (ready.length > 0) {
    const v = ready.pop();
    order.push(v);
    for (const next of adj[v]) {
      if (--inDegree[next] === 0) ready.push(next);
    }
  }

  // Anything left un-emitted is stuck behind a cycle.
  return order.length === nodeCount ? order : null;
}

Returning null rather than a partial order is intended behavior. A half-finished topological order is not a useful object, and callers that silently use one will produce a build that fails much later for reasons that look unrelated.

Where it goes wrong

Assuming the order is unique. It usually is not, tests that compare against one specific expected order will fail on a perfectly correct implementation unless the problem pinned down a tie-break.

Skipping the count check. Without it, a graph with a cycle returns a short list that looks like a valid order until something downstream breaks.

Forgetting isolated nodes. A task with no dependencies in either direction has in-degree 0 and belongs in the output. If you seed the ready collection from the edge list rather than from every node, those nodes vanish silently.

Check yourself