---
title: 'Topological Sort'
source: 'https://academia.sh/en/courses/data-structures/topological-sort'
course: 'Data Structures'
language: en
updated: '2026-08-17T18:07:54+00:00'
license: 'CC BY-SA 4.0'
---

# Topological Sort

Producing a valid execution order from a dependency graph, an in-degree-based algorithm, cycle detection, and uses.

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.

```python
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

```python
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:

```python
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.