# Chapter 21. Topological Ordering

# Chapter 21. Topological Ordering

A topological ordering is a linear arrangement of the vertices of a directed graph that respects every arc direction. It turns a partial order given by a directed acyclic graph into a single list.

Topological ordering is defined only for directed graphs. It is especially important for directed acyclic graphs, because a directed graph has a topological ordering exactly when it has no directed cycle. This equivalence is one of the basic structural facts about DAGs.

## 21.1 Definition

Let

$$
D = (V,A)
$$

be a directed graph. A topological ordering of \(D\) is an ordering of its vertices

$$
v_1, v_2, \ldots, v_n
$$

such that for every arc

$$
(v_i,v_j) \in A,
$$

the vertex \(v_i\) appears before the vertex \(v_j\) in the list.

Equivalently, every arc points from left to right when the vertices are written in topological order.

If an arc is written as

$$
u \to v,
$$

then \(u\) must appear earlier than \(v\).

The ordering does not require every pair of vertices to be related by an arc or path. It only requires the listed order to respect the constraints that are present.

## 21.2 First Example

Consider the directed graph with arcs

$$
a \to b,
\qquad
a \to c,
\qquad
b \to d,
\qquad
c \to d.
$$

The ordering

$$
a,b,c,d
$$

is topological. Each arc points forward:

$$
a \to b,
\qquad
a \to c,
\qquad
b \to d,
\qquad
c \to d.
$$

The ordering

$$
a,c,b,d
$$

is also topological.

There is no arc from \(b\) to \(c\), and no arc from \(c\) to \(b\). Therefore either \(b\) or \(c\) may come first, provided both remain after \(a\) and before \(d\).

The ordering

$$
b,a,c,d
$$

is not topological, because the arc

$$
a \to b
$$

requires \(a\) to appear before \(b\).

## 21.3 Topological Ordering and DAGs

A directed graph has a topological ordering if and only if it is a DAG.

We prove both directions.

First, suppose a directed graph has a topological ordering. If it contained a directed cycle

$$
v_0 \to v_1 \to \cdots \to v_{k-1} \to v_0,
$$

then the ordering would require

$$
v_0 < v_1 < \cdots < v_{k-1} < v_0.
$$

This is impossible. Hence a graph with a topological ordering has no directed cycle.

Conversely, suppose the graph is a finite DAG. Every finite nonempty DAG has at least one source, a vertex with in-degree zero. Place such a source first. Remove it and all outgoing arcs. The remaining graph is still a DAG. Repeat the argument. This process eventually lists every vertex and produces a topological ordering.

Thus acyclicity is exactly the condition needed for topological ordering.

## 21.4 Sources and Construction

A source is a vertex with no incoming arcs.

In a topological ordering, a source is a natural candidate for the first position. Since no arc enters it, no other vertex is required to appear before it.

More generally, after some vertices have already been placed in the ordering, we look at the remaining graph. Any source in the remaining graph may be placed next.

This gives the basic constructive principle:

$$
\text{Repeatedly remove a source.}
$$

The removed vertices, in the order of removal, form a topological ordering.

This is the idea behind Kahn's algorithm, a standard linear-time topological sorting algorithm.

## 21.5 Kahn's Algorithm

Kahn's algorithm builds a topological ordering by repeatedly selecting vertices of in-degree zero.

Given a finite directed graph \(D=(V,A)\):

1. Compute the in-degree of every vertex.
2. Put all vertices of in-degree zero into a set or queue \(S\).
3. Remove a vertex \(u\) from \(S\).
4. Append \(u\) to the output list.
5. For each arc \(u \to v\), remove that arc and decrease the in-degree of \(v\).
6. If \(v\) now has in-degree zero, insert \(v\) into \(S\).
7. Continue until \(S\) is empty.

If every vertex has been output, the list is a topological ordering.

If some vertices remain, then the remaining graph has no source. In a finite directed graph, this means a directed cycle remains. Therefore the original graph was not a DAG.

## 21.6 Example of Kahn's Algorithm

Let

$$
V = \{a,b,c,d,e\}
$$

and

$$
A = \{(a,b),(a,c),(b,d),(c,d),(d,e)\}.
$$

The in-degrees are:

| Vertex | In-degree |
|---|---:|
| \(a\) | 0 |
| \(b\) | 1 |
| \(c\) | 1 |
| \(d\) | 2 |
| \(e\) | 1 |

The only source is \(a\). Place \(a\) first.

After removing \(a\), the vertices \(b\) and \(c\) both have in-degree zero. We may choose either.

Choose \(b\). Then choose \(c\). After both are removed, \(d\) has in-degree zero. Then after removing \(d\), \(e\) has in-degree zero.

One possible topological ordering is

$$
a,b,c,d,e.
$$

Another is

$$
a,c,b,d,e.
$$

The algorithm may produce different valid orderings depending on how it chooses among available sources.

## 21.7 Depth-First Search Method

Topological ordering can also be computed by depth-first search.

Run DFS on the directed graph. When a vertex has finished exploring all of its outgoing neighbors, place it at the front of a list. Equivalently, record vertices in reverse finishing order.

If the graph is a DAG, this reverse finishing order is a topological ordering. This method is another standard linear-time construction.

The reason is as follows. If there is an arc

$$
u \to v,
$$

then DFS finishes \(v\) before \(u\), unless \(v\) was already fully processed. In either case, reversing finishing order places \(u\) before \(v\).

DFS also detects directed cycles. If DFS reaches a vertex that is currently active on the recursion stack, then the graph contains a directed cycle and no topological ordering exists.

## 21.8 Non-Uniqueness

Topological orderings are usually not unique.

Whenever two vertices are unrelated by reachability, either may appear before the other, provided all other constraints are respected.

For example, in the graph

$$
a \to b,
\qquad
a \to c,
$$

both

$$
a,b,c
$$

and

$$
a,c,b
$$

are topological orderings.

A DAG has a unique topological ordering only under stronger conditions. One useful characterization is that the ordering is unique exactly when each consecutive pair in the ordering is forced by an arc, or equivalently when the DAG contains a directed Hamiltonian path consistent with the ordering.

## 21.9 Topological Ordering as Linear Extension

A DAG defines a partial order by reachability.

Define

$$
u \preceq v
$$

if \(u=v\) or there is a directed path from \(u\) to \(v\).

A topological ordering is a linear extension of this partial order. It places all vertices in one sequence while preserving the required precedence constraints.

This interpretation is important. The DAG may not compare every pair of vertices, but a topological ordering must still choose some order for incomparable pairs.

Thus topological sorting converts partial order into total order without violating the partial order.

## 21.10 Applications to Scheduling

Topological ordering is the basic model for dependency scheduling.

Suppose vertices represent tasks, and an arc

$$
u \to v
$$

means that task \(u\) must be completed before task \(v\) begins.

Then a topological ordering gives a valid schedule. Every task appears after all of its prerequisites.

Examples include:

| System | Vertices | Arcs |
|---|---|---|
| Course planning | Courses | prerequisite before course |
| Build systems | Targets | dependency before dependent |
| Project planning | Tasks | required task before later task |
| Compilers | Computations | value before use |
| Spreadsheets | Cells | referenced cell before formula cell |
| Package managers | Packages | dependency before dependent |

Topological ordering is widely used for dependency-driven execution and scheduling.

## 21.11 Cycle Detection Through Topological Sorting

Topological sorting also detects cycles.

During Kahn's algorithm, if vertices remain but no source exists, then the remaining subgraph contains a directed cycle. Therefore no topological ordering exists.

This gives a practical test:

| Result | Meaning |
|---|---|
| All vertices are output | The graph is a DAG |
| Some vertices remain | The graph contains a directed cycle |

This is useful in systems where cycles represent invalid dependency structure, such as build rules, imports, package dependencies, and task graphs.

## 21.12 Complexity

Topological sorting can be performed in linear time:

$$
O(|V| + |A|).
$$

The algorithm visits each vertex and processes each arc a constant number of times.

Kahn's algorithm achieves this bound by maintaining in-degree counts and adjacency lists. DFS topological sorting also achieves this bound by running one depth-first traversal over the graph.

This linear complexity makes topological sorting practical even for large graphs.

## 21.13 Topological Ordering in Weighted DAGs

Topological order is useful beyond scheduling. It also supports efficient dynamic programming on DAGs.

For example, shortest paths in a weighted DAG can be computed by processing vertices in topological order. When a vertex is processed, all possible incoming contributions from earlier vertices have already been considered. This avoids repeated relaxation cycles and gives a linear-time algorithm in the number of vertices and arcs.

The same principle applies to longest paths in DAGs, counting paths, evaluating expression graphs, and many dynamic programming recurrences.

Acyclicity turns recurrence into ordered computation.

## 21.14 Common Mistakes

A common mistake is to attempt topological sorting on an undirected graph. Topological ordering is a concept for directed graphs.

Another mistake is to think that every directed graph has a topological ordering. Directed cycles make topological ordering impossible.

A third mistake is to expect the ordering to be unique. Many DAGs have several valid topological orderings.

A fourth mistake is to reverse the meaning of dependency arcs. If \(u \to v\) means “\(u\) must come before \(v\),” then \(u\) appears before \(v\). If the convention is reversed, the interpretation of the order is reversed as well.

## 21.15 Summary

A topological ordering of a directed graph is a linear ordering of vertices in which every arc points from an earlier vertex to a later vertex.

A finite directed graph has a topological ordering exactly when it is a DAG. This makes topological sorting both a construction method and a cycle-detection method.

Two standard algorithms compute topological orderings in linear time: Kahn's algorithm, which repeatedly removes sources, and the depth-first search method, which uses reverse finishing order.

Topological ordering is the main bridge between directed acyclic graphs and ordered computation. It is used in scheduling, dependency resolution, compilation, dynamic programming, project planning, and many other systems where one object must precede another.