Topological Sort

Directed acyclic graphs were introduced in the concept-of-a-graph lesson as the natural model of dependency relationships: an edge means “this task must be done before that one.”

This lesson’s question is directly practical: given a set of dependencies, how is a valid execution order found?

Definition and Existence Condition

A topological sort is an arrangement of all the vertices in a graph such that every edge goes left to right in the list: if an edge a → b exists, a comes before b in the list.

Only one condition is needed for such an ordering to exist: the graph must be acyclic. If a cycle exists, every vertex in the cycle would have to come before itself, which is impossible.

The condition means the sorting algorithm is also a cycle tester: if all vertices cannot be sorted, the graph contains a cycle.

The In-Degree-Based Algorithm

The most intuitive method is to start from the tasks that have no dependencies left.

1. Compute the in-degree of every vertex — how many edges arrive at it.
2. Place the vertices with in-degree zero in a queue; these are waiting on nothing.
3. Take a vertex from the queue, add it to the ordering. Remove every edge leaving it: decrement the in-degree of its target; if it drops to zero, add it to the queue.
4. Continue until the queue is empty.

If, at the end, the number of vertices in the ordering is less than the total number of vertices, the remaining vertices are part of a cycle.

from collections import deque

def topological_sort(adjacency: dict[str, list[str]]) -> list[str] | None:
    """Returns a valid ordering; None if a cycle exists."""
    in_degree = {vertex: 0 for vertex in adjacency}
    for vertex in adjacency:
        for target in adjacency[vertex]:
            in_degree[target] += 1

    queue = deque(sorted(v for v in in_degree if in_degree[v] == 0))   # sorted for determinism
    result: list[str] = []

    while queue:
        vertex = queue.popleft()
        result.append(vertex)
        for target in adjacency[vertex]:
            in_degree[target] -= 1                # dependency satisfied
            if in_degree[target] == 0:
                queue.append(target)

    return result if len(result) == len(adjacency) else None


# This curriculum's own prerequisite relationship is a dependency graph.
courses = {
    "bilgisayarlar-nasil-calisir": ["programlama-temelleri"],
    "programlama-temelleri":       ["veri-yapilari"],
    "veri-yapilari":               ["algoritmalar"],
    "modelleme-ve-gosterim":       ["algoritmalar"],
    "algoritmalar":                [],
}

print(topological_sort(courses))
# ['bilgisayarlar-nasil-calisir', 'modelleme-ve-gosterim',
#  'programlama-temelleri', 'veri-yapilari', 'algoritmalar']

The result is a reading order in which every course comes after its prerequisites. modelleme-ve-gosterim comes out early because it has no prerequisites; algoritmalar comes out last because it waits on two separate courses.

The Ordering Is Not Unique

For the same graph, there are generally several valid orderings. In the example above, modelleme-ve-gosterim can be anywhere in the list as long as it comes before algoritmalar.

This means the algorithm is making a choice: when more than one vertex is in the queue, which one is taken is free. The implementation above uses alphabetical order so the output is repeatable; another criterion could be chosen instead — taking the shortest task first, for example.

The ordering is unique only when the graph forms a chain: at every step, exactly one vertex is in the queue.

The Cycle Case

cyclic = {
    "a": ["b"],
    "b": ["c"],
    "c": ["a"],       # cycle: a → b → c → a
}

print(topological_sort(cyclic))     # None

Because no vertex has in-degree zero, the queue is empty from the start and the result stays empty. The length check catches this.

This is an alternative to the depth-first-search-based cycle detection from the previous lesson. The two answer the same question; the in-degree-based method also directly gives which vertices are involved in the cycle when one is found — those that never enter the ordering.

A second, depth-first-search-based method also exists: vertices are sorted by finish time and the list is reversed. The result is equally valid; which method to choose depends on the graph’s representation and on whether cycle information is needed.

Layers and Parallel Execution

The flat list the algorithm produces is meant for sequential execution. If independent tasks can run in parallel, a more useful output is layers: the set of tasks that can be started at the same time.

Layers are the contents of the queue on each round — the same layer separation as in breadth-first search:

def layers(adjacency: dict[str, list[str]]) -> list[list[str]] | None:
    in_degree = {v: 0 for v in adjacency}
    for v in adjacency:
        for target in adjacency[v]:
            in_degree[target] += 1

    ready = sorted(v for v in in_degree if in_degree[v] == 0)
    result: list[list[str]] = []
    processed = 0
    while ready:
        result.append(ready)
        processed += len(ready)
        next_ready: list[str] = []
        for vertex in ready:
            for target in adjacency[vertex]:
                in_degree[target] -= 1
                if in_degree[target] == 0:
                    next_ready.append(target)
        ready = sorted(next_ready)
    return result if processed == len(adjacency) else None


print(layers(courses))
# [['bilgisayarlar-nasil-calisir', 'modelleme-ve-gosterim'],
#  ['programlama-temelleri'], ['veri-yapilari'], ['algoritmalar']]

The two courses in the first layer can be read at the same time; the second layer can only start once the first is complete. The number of layers is the shortest time in which all the work could finish given infinite parallelism — this value is called the graph’s critical path length.

Cost

Each vertex enters the queue at most once, and each edge is examined exactly once:

$$O(\lvert V \rvert + \lvert E \rvert)$$

Computing the in-degrees also scans every edge once; the total cost does not change.

Uses

Build systems. Dependencies between source files form a graph; which file compiles first is decided by topological sort. The linking stage from the How Computers Work course rests on this ordering.

Package managers. The install order of dependencies; a circular dependency is a reason installation is refused.

Task scheduling. The execution order of interdependent jobs; in data pipelines, the order in which steps run is determined this way.

Spreadsheet recalculation. When one cell changes, the order in which the cells that depend on it are updated.

Learning paths. This curriculum’s own prerequisite structure; the example above is a real application.

Bringing the Course Together

This lesson is an example of the structures this course has built working together: the graph is shown with a mapping, in-degrees are kept in a counter, ready vertices wait in a queue, and the result accumulates in an array.

The principle repeated throughout the course also becomes visible here: every structure makes one operation cheaper by making some other operation more expensive. An array makes access cheap and insertion expensive; a linked list does the reverse. A hash table reduces lookup to a constant and loses order. A tree preserves order and loses constant time. A heap gives the extreme element but cannot search.

Choosing the right structure is therefore not “finding the best structure”: it is knowing which operation is frequent and which is rare. Algorithms, the subject of the next course, asks the same question at the level of operations.

Summary

• Topological sort is an arrangement of vertices in which every edge goes left to right in the list.
• For the ordering to exist, the graph must be acyclic; the algorithm is also a cycle tester.
• The in-degree-based method starts from vertices with no dependencies left, and new ready vertices appear as edges are removed.
• For the same graph there are generally several valid orderings; the algorithm applies a criterion when choosing from the queue.
• Cost is $O(V + E)$.
• Build systems, package managers, task scheduling, and prerequisite structures use this ordering.

Next Step

This course built how data is organized and how that organization determines the cost of operations. The next course — Algorithms — takes up the solutions that work on these structures: how different solutions to a problem are compared, how cost is expressed formally, and which methods solve sorting, searching, and graph problems.