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

Как упорядочить задачи так, чтобы каждая шла после всех, от которых зависит. И как заодно поймать «порочный круг» зависимостей.

Топологическая сортировка — упорядочивание вершин ориентированного ациклического графа так, что для каждого ребра u → v вершина u идёт раньше v.

Зачем это нужно

Представь учебный план: чтобы изучить «Производные», надо сначала пройти «Пределы», а для них — «Функции». Это граф зависимостей, и нужно выстроить порядок прохождения. Аналогично: порядок сборки модулей проекта, выполнение задач с предусловиями, расписание курсов. Все они — про топологическую сортировку. Бонусом тот же алгоритм обнаруживает циклы: если зависимости образуют порочный круг (A зависит от B, B от A), корректного порядка не существует, и алгоритм это покажет.

Идея «на пальцах» (алгоритм Кана)

Самый интуитивный метод — алгоритм Кана на входящих степенях. Входящая степень вершины — число рёбер, ведущих в неё (число «предусловий»). Логика:

• Вершина с входящей степенью 0 ни от чего не зависит — её можно делать прямо сейчас.
• «Выполнив» вершину, убираем её рёбра — у соседей входящая степень уменьшается.
• Когда у соседа степень падает до 0, все его предусловия выполнены — он готов к обработке.

Берём вершины с нулевой степенью из очереди, добавляем в ответ, обновляем соседей — пока очередь не опустеет.

Реализация

from collections import deque

n = 6
edges = [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)]
g = [[] for _ in range(n)]
indeg = [0] * n
for u, v in edges:
    g[u].append(v)
    indeg[v] += 1                 # считаем входящие степени

# старт: все вершины без предусловий
q = deque(i for i in range(n) if indeg[i] == 0)
order = []
while q:
    u = q.popleft()
    order.append(u)
    for v in g[u]:
        indeg[v] -= 1             # «убрали» ребро u->v
        if indeg[v] == 0:         # все предусловия v выполнены
            q.append(v)

print("Топологический порядок:", order)
print("Корректен (нет цикла):", len(order) == n)

Разберём результат. Вершины 4 и 5 не имеют входящих рёбер — с них начинаем. Дальше порядок раскручивается по зависимостям. В выводе видно: 5 идёт раньше 2 и 0 (рёбра 5→2, 5→0), 2 раньше 3, и так далее — все рёбра «смотрят вперёд». Сложность — O(n + m): каждое ребро обрабатывается один раз.

Вывод:

Топологический порядок: [4, 5, 2, 0, 3, 1]
Корректен (нет цикла): True

Обнаружение цикла — бесплатный бонус

Ключевое наблюдение: если в графе есть цикл, то вершины цикла никогда не получат входящую степень 0 (они вечно ждут друг друга), и в order попадут не все вершины. Поэтому проверка len(order) == n отвечает на вопрос «есть ли цикл?». Если меньше — корректного порядка не существует.

from collections import deque

def has_cycle(n, edges):
    g = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        g[u].append(v); indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    processed = 0
    while q:
        u = q.popleft(); processed += 1
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return processed != n          # не все обработаны => есть цикл

print("Граф 0->1->2:        цикл?", has_cycle(3, [(0, 1), (1, 2)]))
print("Граф 0->1->2->0:    цикл?", has_cycle(3, [(0, 1), (1, 2), (2, 0)]))

Первый граф — цепочка без цикла, все три вершины обработаны. Второй замкнут в кольцо: ни у одной вершины степень не станет 0, обработано 0 вершин — цикл есть.

Вывод:

Граф 0->1->2:        цикл? False
Граф 0->1->2->0:    цикл? True

Где применяется

• Зависимости: порядок установки пакетов, сборки модулей, прохождения курсов.
• Планирование задач с предусловиями (что за чем делать).
• ДП на DAG: динамику по графу удобно считать в топологическом порядке.
• Проверка ацикличности любого ориентированного графа.

Подводные камни

• Порядок не единственный. При нескольких вершинах со степенью 0 топсортировок много; задача может требовать лексикографически наименьшую — тогда вместо очереди берут min-кучу.
• Только для ориентированных графов. Для неориентированных понятие топологического порядка не определено.
• Цикл = нет порядка. Всегда проверяй len(order) == n, если не гарантировано, что граф ацикличен.
• Есть и DFS-вариант топсортировки (через порядок выхода из вершин), но алгоритм Кана нагляднее и проще ловит циклы.

Итог

• Топологическая сортировка упорядочивает вершины DAG так, что каждое ребро ведёт «вперёд».
• Алгоритм Кана: начинаем с вершин входящей степени 0, снимаем рёбра, добавляем вершины по мере готовности — O(n+m).
• Если обработаны не все вершины (len(order) < n) — в графе есть цикл, порядок невозможен.
• Применяется к зависимостям, планированию и ДП на DAG.