Topological Sort

Topological Sort

A topological sort is a traversal of a digraph with ordering constraints. Let each node have some value/weight. It is a linear ordering of the nodes such that for every edge \(u-v\), \(u\) comes before \(v\) in the ordering.

A common example of this is the tree one often sees in textbooks which indicate the dependencies of the chapters. If you want to know what chapter requires which other chapters as prerequisites, you do a topological sort on them.

A digraph can be topologically sorted if and only if it is a directed acyclic graph (DAG).

To topologically sort a DAG, apply the depth first search algorithm. Whenever you reach a node where you can’t proceed any further, place that node on a stack. Once you’ve traversed all the nodes (not just in a connected component), start popping the stack. The order the nodes leave the stack is the desired ordering.

The complexity is linear.

Note that the ordering is not unique.

Implementations