Detour: Constructing a Topological Ordering

Topological ordering algorithm

The first applications of topological ordering resulted from large management projects in an attempt to schedule a sequence of tasks based on their dependencies (such as the Dressing Challenge). In these projects, tasks are represented by nodes, and an edge connects node a to node b if task a must be completed before task b can be started.

STOP and Think: Prove that every DAG has a node with no incoming edges and a node with no outgoing edges.

The following algorithm for constructing a topological ordering is based on the observation that every DAG has at least one node with no incoming edges. We’ll label one of these nodes as $v_{1}$ and then remove this node from the graph along with all its outgoing edges. The resulting graph is also a DAG, which in turn must have a node with no incoming edges; we label this node $v_{2}$, and again remove it from the graph along with its outgoing edges. The resulting algorithm proceeds until all nodes have been removed, producing a topological order $v_{1}, ... , v_{n}$. This algorithm runs in time proportional to the number of edges in the input DAG.