Topological Sort

I’ve been tinkering with build systems lately, and the associated dependency graph between source artefacts. For anyone working on a system like this, you will eventually arrive at the algorithm for Topological Sorting. The Wikipedia page had a very good description of the algorithm, but I found another description that appeared clearer to me:

Repeat the following steps until the graph is empty:

  1. Select a vertex that has no incoming edges.
  2. Add the vertex to the sort.
  3. Delete the vertex and all the edges emanating from it from the graph.

I thought it was a pretty elegant algorithm, and now that I know what I’m looking for, it turns up in a fairly large number of places.

2 thoughts on “Topological Sort

Comments are closed.