Topological Sort

The topological sort algorithm takes a directed graph and returns an array of the nodes where each node appears before all the nodes it points to.

Since node 1 points to nodes 2 and 3, node 1 appears before them in the ordering. And, since nodes 2 and 3 both point to node 4, they appear before it in the ordering.

So [1, 2, 3, 4, 5] would be a topological ordering of the graph.

A graph can have more than one topological ordering

The Algorithm

How can we produce a topological ordering for this directed graph?

Well, let's focus on the first node in the topological ordering. That node can't have any incoming directed edges; it must have an indegree ↴ of zero.

So, we'll find a node with an indegree of zero and add it to the topological ordering.

That covers the first node in our topological ordering. What about the next one?

Once a node is added to the topological ordering, we can take the node, and its outgoing edges, out of the graph.

Then, we can repeat our earlier approach: look for any node with an indegree of zero and add it to the ordering.

Here's what this looks like on our graph. We'll grab a node with an indegree of 0, add it to our topological ordering and remove it from the graph:

and repeat

and repeat

until we're

out of nodes