Algorithms and data structures · Intermediate

Topological sorting: order tasks by dependencies

Use zero-indegree vertices to produce a dependency-respecting order and recognize when a directed cycle prevents one.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Define the edge direction first
  2. Remove zero-indegree vertices
  3. Recognize a remaining cycle
  4. Separate cost, choice and uniqueness
  5. Ask Logeia about this articleCheck your understanding

Define the edge direction first

A topological ordering places u before v for every directed edge u→v. For task dependencies, draw an edge from a prerequisite to the task that requires it. Reversing that convention reverses the meaning of the result. Such an ordering exists exactly for a directed acyclic graph, or DAG. This is not a shortest-path calculation or a request to sort tasks by edge weight. Include isolated vertices in the vertex set as well: a task without dependencies must not disappear simply because it has no incident edges.

Remove zero-indegree vertices

With edges A→C, B→C and C→D, the initial zero-indegree vertices are A and B. Remove A and decrement C’s indegree from two to one. Removing B reduces it to zero, so C becomes ready. Removing C then makes D ready, producing [A,B,C,D]. Choosing B before A instead yields another valid order, [B,A,C,D]. Kahn’s algorithm can be understood as repeatedly deleting a ready vertex and its outgoing edges. The indegrees describe the remaining graph, not the original graph after some unrelated visitation labels have been set.

Recognize a remaining cycle

If the ready queue becomes empty before all V vertices are output, the unprocessed subgraph contains a directed cycle. Adding D→C to the example leaves C and D dependent on one another after A and B are processed. Not every unprocessed vertex must itself lie on a cycle; downstream vertices may merely be blocked by one. Reporting an actual cycle requires additional traversal information. Self-loops and parallel edges also require consistent indegree accounting. Count every stored edge when initializing and decrement it once when its source is removed.

Separate cost, choice and uniqueness

With adjacency lists and an ordinary queue, each vertex and edge is processed once, giving O(V+E) time and O(V) additional bookkeeping space. The graph representation itself occupies O(V+E). A priority queue can select the lexicographically smallest ready task, but changes the running-time analysis. Several simultaneous choices indicate that the valid order need not be unique. Dependency ordering also does not by itself schedule limited workers, memory or other execution resources. Validate the ordering by checking every edge’s endpoint positions, and distinguish that test from checking whether the produced order is the only possible one.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 11

Choose a learning path