Detour: Constructing a Topological Ordering
Let’s look at an algorithm for topological ordering.
We'll cover the following...
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 ...