Topological Sorting

The following is an implementation of topological sorting on a graph (Wikipedia). This sort runs in O(delim{|}{V}{|} + delim{|}{E}{|}), where delim{|}{V}{|} = number of vertices and delim{|}{E}{|} = number of edges.

Topological sort: arrange directed graph — one node per column — so that all edges point right.

If each node is a job to be scheduled, and each incoming edge indicates a prerequisite, a topological ordering is a valid job scheduling; sweeping left to right, all prerequisites have been satisfied.

My implementation is in git and below:

Leave a Reply