Skip to main content

Topological Sort and DAG Algorithms

What This Concept Is​

A topological order is a permutation of all vertices with every edge going from an earlier to a later vertex. It exists exactly for a DAG. Kahn's algorithm maintains residual indegrees, enqueues zero-indegree vertices and removes their outgoing edges. If fewer than V vertices are emitted, a cycle remains. A FIFO implementation runs in O(V+E); a heap for lexicographic choice changes the bound.

Why It Matters Here​

Topological processing turns cyclic-looking recurrence code into one pass only when dependencies actually form a DAG. Order is a certificate: check a complete vertex permutation and every edge inequality. Many valid orders can exist.

Concrete Examples​

For 0→2,1→2,2→3 with isolated 4, orders such as [0,1,4,2,3] and [4,1,0,2,3] both work. Two parallel 0→2 edges contribute two to indegree and must each be removed, or both consistently deduplicated before counting.

For DAG shortest paths, initialize source to zero and others unreachable, then relax outgoing edges in topological order. Every possible predecessor has been processed when a vertex is used, so even negative weights are safe. Longest paths switch min to max and use an unreachable sentinel, not zero everywhere.

Common Confusion / Misconceptions​

Unemitted Kahn vertices are not all necessarily on cycles: downstream vertices can be blocked by one. Use SCCs to isolate the actual cycle regions. Precedence order alone is not a minimum-duration schedule. Critical-path length equals the minimum makespan only under assumptions such as unlimited processors, fixed task durations and no additional resource constraints. Path counts may require large integers; O(V+E) arithmetic operations are not necessarily O(V+E) bit work.

How To Use It​

Document edge direction and cycle behavior. Return None on cycles in the lab; the empty graph has the valid empty order. To return a concrete cycle, add a DFS or SCC-based witness extraction rather than inventing one from the incomplete output list. Keep presentation tie-breaking separate from correctness.

Check Yourself​

  1. Why must every DAG have a zero-indegree vertex?
  2. Why may blocked vertices be outside all cycles?
  3. Why do negative weights not break DAG relaxation?
  4. Which scheduling assumption makes critical-path length attainable?

Mini Drill or Application​

Validate alternative orders, duplicate edges and a self-loop. Add a negative weighted edge to a DAG and derive shortest distances in order. Then add a back edge and reject the graph before applying the DAG recurrence. See P8.

Read This Only If Stuck​

Find topological order, DAG paths, and critical-path assumptions in Skiena, CLRS, or Sedgewick and Wayne. These are book indexes, not exact section links. The reading guide names bounded assignments and local source files. Attempt the worked examples before adding more reading.