You have 6 build tasks with dependencies and must produce the lexicographically smallest valid order, or report a cycle. Give the algorithm, its complexity, and explain why the standard depth first search topological sort cannot produce the lexicographically smallest order.

You have 6 build tasks with dependencies and must produce the lexicographically smallest valid order, or report a cycle. Give the algorithm, its complexity, and explain why the standard depth first search topological sort cannot produce the lexicographically smallest order.

Approach: Kahn's algorithm is free to pick any vertex of in-degree zero. Make that choice greedy and prove the greedy pick is safe by an exchange argument.

Run Kahn's algorithm with a min-heap as the priority queue over the ready set, which is O((V + E) log V), and report a cycle when fewer than V vertices are emitted. Compute the in-degree of every vertex, push all vertices of in-degree zero, then repeatedly pop the smallest label, append it to the order and decrement the in-degree of each successor, pushing any successor that reaches zero. The greedy pick is safe by an exchange argument: if the smallest ready vertex v is not placed first, take any valid order and move v to the front. Nothing ahead of v can be an ancestor of v, since v has in-degree zero among the remaining vertices, so the move keeps the order valid and makes it lexicographically no larger. If the loop halts with vertices left, each of them has positive in-degree, which forces a cycle. Depth first search emits vertices in reverse finish order, so a vertex position depends on when its whole descendant subtree finishes rather than on its own label, giving a valid but generally larger sequence.

Follow-up: How do you find the lexicographically smallest order when each task also has a duration and you must minimise makespan on two machines?

Key concepts: kahn's algorithm, in-degree, priority queue, exchange argument.