Урок

Топологическая сортировка

Интуиция: что делать сначала

Ты одеваешься утром. Носки надеваются раньше ботинок, футболка раньше куртки. А вот носки и футболку можно надеть в любом порядке. Чтобы не запутаться, ты действуешь так: берёшь любую вещь, которую уже можно надеть, потому что всё нужное для неё уже на тебе. Надел её, и, возможно, «открылись» новые вещи.

Это и есть топологическая сортировка: расставить задачи в таком порядке, чтобы каждая шла после всех, от которых зависит.

Зависимости как граф

Каждая задача — вершина. Если A нужно сделать до B, проводим направленное ребро A → B.

Возьмём пример — сборку модулей проекта:

Модуль	Номер	Зависит от
utils	0	—
db	1	utils
auth	2	utils
api	3	db, auth
app	4	api

Рёбра: 0→1, 0→2, 1→3, 2→3, 3→4.

Один из правильных порядков: utils, db, auth, api, app. Порядок utils, auth, db, api, app тоже правильный. Ответ часто не единственный, и на собесе это нормально.

Цикл = невозможность. Если A ждёт B, а B ждёт A, ни одну из них нельзя начать первой. Топологический порядок существует только для графа без циклов (DAG). Поэтому та же сортировка — ещё и детектор циклов.

Алгоритм Кана: входящие степени и очередь

Входящая степень (indegree) вершины — это сколько стрелок в неё входит, то есть сколько у неё невыполненных зависимостей. Вершина с indegree = 0 готова к выполнению прямо сейчас.

Алгоритм:

Посчитай indegree для каждой вершины.
Положи в очередь все вершины с indegree = 0.
Пока очередь не пуста:
- достань вершину v и добавь её в ответ;
- для каждого соседа u (ребро v → u) уменьши indegree[u] на 1, потому что одна зависимость выполнена;
- если indegree[u] стал 0, положи u в очередь.
Если в ответе меньше n вершин, в графе есть цикл.

Прогоним на нашем примере

Стартовые входящие степени. Свободен только utils:

indegree: utils=0, db=1, auth=1, api=2, app=1

utils→null

очередь на старте

Достаём utils. Его соседи db и auth теряют по зависимости, и у обоих степень становится 0:

после utils: db и auth освободились

db→auth→null

очередь: db, auth

Достаём db, и у api степень падает до 1. Пока рано. Достаём auth, и у api степень становится 0:

после db и auth: api готов

Дальше api освобождает app. Итог:

utils→db→auth→api→app→null

топологический порядок — все 5 вершин, цикла нет

Шаблон кода

Вершины пронумерованы 0..n-1, рёбра заданы парами [from, to]. Функция возвращает порядок или пустой список, если есть цикл.

from collections import deque

def topo_sort(n, edges):
    graph = [[] for _ in range(n)]
    indeg = [0] * n
    for a, b in edges:          # a должно быть раньше b
        graph[a].append(b)
        indeg[b] += 1
    q = deque(v for v in range(n) if indeg[v] == 0)
    order = []
    while q:
        v = q.popleft()
        order.append(v)
        for u in graph[v]:
            indeg[u] -= 1       # одна зависимость выполнена
            if indeg[u] == 0:
                q.append(u)
    return order if len(order) == n else []  # иначе цикл

Сложность

Время: O(V + E). Каждую вершину кладём в очередь один раз, каждое ребро просматриваем один раз.
Память: O(V + E) на список смежности, массив степеней и очередь.

Где встречается

Сборка модулей и пакетов: в каком порядке компилировать (make, Gradle, npm/pip резолверы).
Расписание курсов: «чтобы взять курс B, сначала пройди A». Можно ли пройти все курсы, и в каком порядке.
Порядок вычисления ячеек в таблицах, миграции БД, пайплайны задач (CI, Airflow).

Сигнал к применению: в условии есть слова «зависит от», «сначала / потом», «prerequisite», «порядок».

Как это звучит на собесе

«Строю направленный граф: ребро из A в B, если A нужно сделать раньше. Считаю входящие степени и запускаю алгоритм Кана: в очередь кладу вершины без зависимостей, по одной достаю и уменьшаю степени соседей. Если в итоге обработал не все вершины, значит есть цикл и ответа нет. Время и память O(V + E)».

Частые ошибки

Перепутано направление ребра. «B зависит от A» — это A → B, а indegree увеличивается у B. Если перепутать, получишь порядок задом наперёд.
Забыта проверка на цикл. Вершины из цикла никогда не попадут в очередь, и ответ молча окажется короче. Всегда сравнивай len(order) с n.
Учтены не все вершины. Изолированная вершина без рёбер тоже должна попасть в ответ. Стартовую очередь заполняй перебором всех 0..n-1, а не только тех, что встречаются в рёбрах.
shift() в JS или срез в цикле на больших входах. Используй указатель head.

Запомни одну фразу: «беру то, что уже свободно, и освобождаю следующих». Из неё весь алгоритм Кана восстанавливается за минуту.