Топологическая сортировка: порядок, в котором можно делать

Коротко

Топологическая сортировка - такой порядок вершин ориентированного графа, при котором каждое ребро ведёт СЛЕВА НАПРАВО: если есть u → v, то u стоит раньше v. Это ровно ответ на вопрос «в каком порядке выполнять задачи с зависимостями». Существует такой порядок тогда и только тогда, когда в графе нет циклов, - то есть для ДАГа (направленного ациклического графа); при цикле порядка нет в принципе, и это не недостаток алгоритма, а свойство задачи. Получается он из уже знакомого обхода в глубину почти бесплатно: выписать вершины в порядке ВЫХОДА и перевернуть. Порядок не единственный: у графа обычно много допустимых расстановок.

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

Как думаешь, почему хватает одного обхода

Обход в глубину из прошлой главы уже умеет находить циклы. Прежде чем читать дальше, подумай: какая информация из обхода говорит, что вершину можно ставить в порядок? Подсказка: вершина готова тогда, когда готово всё, что из неё достижимо, - а этот момент обход как раз фиксирует.

На что это похоже

Сборка мебели по инструкции. Нельзя прикрутить дверцу, пока не собран каркас; нельзя собрать каркас, пока не подготовлены стенки. Инструкция и есть топологический порядок: она не единственная (стенки можно готовить в любом порядке), но каждое «сначала это» соблюдено. А если в инструкции написано «шаг 3 после шага 5» и одновременно «шаг 5 после шага 3» - собрать нельзя вообще, и никакая перестановка не спасёт.

Механизм: обратный порядок выхода

order = []
color = [0] * V              # 0 белая, 1 серая, 2 чёрная

def dfs(v):
    color[v] = 1
    for u in adj[v]:
        if color[u] == 1:
            raise Exception("цикл: топологического порядка нет")
        if color[u] == 0:
            dfs(u)
    color[v] = 2
    order.append(v)          # вершина ВЫХОДИТ - значит всё после неё уже записано

for v in range(V):
    if color[v] == 0:
        dfs(v)

order.reverse()              # переворачиваем - и получаем топологический порядок

Весь алгоритм - три строки поверх обхода: список order, дописывание вершины при выходе и разворот в конце. Цена та же O(V + E). Серый цвет ловит цикл (а при цикле ответа не существует); за то, чтобы вершина не попала в список раньше времени, отвечает не он, а МОМЕНТ записи - после перебора всех соседей, то есть при выходе.

Топологический порядок разворачивает граф в линию так, что каждое ребро смотрит вперёд. Таких линий обычно несколько.

Правило

Топологический порядок - расстановка вершин, при которой каждое ребро u → v идёт вперёд (u раньше v). Существует тогда и только тогда, когда граф ацикличен. Получается из обхода в глубину: вершины записываются в момент ВЫХОДА, итоговый список переворачивается; цена O(V + E). Порядок, как правило, не единственный. Цикл обнаруживается тем же обходом - по ребру в серую вершину.

Разбор: почему обратный порядок выхода верен

Надо доказать: если есть ребро u → v, то в итоговом списке u стоит раньше v. После разворота это равносильно tout[u] > tout[v] - то есть вершина u выходит ПОЗЖЕ. Разберём три случая по цвету v в момент, когда обход стоит в u и смотрит ребро u → v (четвёртого не бывает).

v белая. Мы спустимся в неё прямо сейчас, изнутри dfs(u). Вложенный вызов завершится раньше объемлющего, значит tout[v] < tout[u]. Верно.
v чёрная. Она уже вышла, а u ещё нет, значит tout[v] < tout[u]. Верно.
v серая. Это обратное ребро, то есть цикл, - а в этом случае топологического порядка не существует, и алгоритм останавливается с ошибкой. Значит случай к делу не относится.

Получается, для ациклического графа tout[u] > tout[v] выполняется ДЛЯ КАЖДОГО ребра. Сортировка по убыванию tout и есть топологический порядок - а обход даёт её бесплатно, если записывать вершины при выходе и перевернуть список.

Обратная сторона «тогда и только тогда» доказывается в одну строку: пусть в графе есть цикл v₁ → v₂ → ... → v_k → v₁. Каждое его ребро требует, чтобы начало стояло раньше конца, значит v₁ раньше v₂, v₂ раньше v₃, ..., и наконец v_k раньше v₁. Склеив цепочку, получаем, что v₁ стоит раньше самого себя - невозможно. Значит при цикле порядка не существует вовсе, и дело не в алгоритме.

Заметь, как мало пришлось доказывать: вся работа сделана теоремой о скобках из прошлой главы. Именно поэтому времена входа-выхода стоило вводить отдельным уроком - они окупаются здесь и дальше.

Разбор: считаем порядок руками

Граф зависимостей: a→b, a→c, b→d, c→d. Обход стартует из a, соседи в порядке записи.

вход a
  вход b
    вход d      (у d исходящих рёбер нет)
    выход d  →  order = [d]
  выход b      →  order = [d, b]
  ребро a→c: c белая
  вход c
    ребро c→d: d ЧЁРНАЯ - не идём
  выход c      →  order = [d, b, c]
выход a        →  order = [d, b, c, a]

Переворачиваем: a, c, b, d. Проверим все рёбра: a→b - a перед b ✓; a→c - ✓; b→d - b перед d ✓; c→d - ✓. Порядок годится.

Обрати внимание: он не совпал с «очевидным» a, b, c, d, но тот тоже верен - просто наш обход закончил c позже b. Оба ответа правильные, и это нормально: у ДАГа обычно много топологических порядков (у нашего - ровно два). Если задача требует КОНКРЕТНЫЙ из них - например, лексикографически наименьший, - обход в глубину не подойдёт, нужен другой алгоритм, и он в следующем уроке.

Что ломается без этого

Первое: записывать вершину при ВХОДЕ, а не при выходе. В разобранном примере список получился бы [a, b, d, c], а после обязательного разворота - c, d, b, a: ребро a→b смотрит назад, и порядок никуда не годится. Второе: забыть развернуть список - получится ОБРАТНЫЙ топологический порядок, и все зависимости выполнятся наоборот; ошибка особенно коварна, потому что на симметричных тестах может не проявиться. Третье: применять топологическую сортировку к графу с циклом и не проверять цикл - алгоритм молча выдаст какой-то порядок, в котором часть рёбер смотрит назад. Четвёртое: забыть внешний цикл по всем вершинам - вершины, недостижимые из первой, не попадут в порядок вовсе. Пятое: ждать единственного ответа и сравнивать вывод с эталоном строкой - проверять надо СВОЙСТВО («каждое ребро вперёд»), а не совпадение с конкретной расстановкой.

Зачем это в работе

Это, пожалуй, самый часто применяемый графовый алгоритм в инженерной практике. Системы сборки (make, ninja, сборщики фронтенда) строят граф зависимостей целей и выполняют их в топологическом порядке; они же сообщают о циклической зависимости - это та самая проверка серым цветом. Пакетные менеджеры решают порядок установки. Планировщики задач и конвейеры CI выполняют шаги с учётом «после чего». Миграции базы данных применяются в порядке зависимостей. В электронных таблицах пересчёт формул идёт топологически - и циклическая ссылка ловится тем же способом. В компиляторах порядок вычисления выражений и инициализации модулей, в операционных системах порядок запуска служб (systemd хранит зависимости и разворачивает их топологически). Там же, где линейный порядок не нужен, а нужна параллельность, топологическая сортировка даёт УРОВНИ: всё, что не зависит друг от друга, можно делать одновременно - об этом следующий урок.

Теперь сам

Граф: 1→3, 2→3, 3→4, 2→5, 5→4. Проведи обход в глубину, стартуя с вершины 1, потом с остальных по возрастанию, и выпиши топологический порядок. Проверь, что каждое ребро смотрит вперёд.

Ответ. Списки: adj[1]=[3], adj[2]=[3,5], adj[3]=[4], adj[4]=[], adj[5]=[4]. Обход: вход 1 → ребро 1→3, тройка белая → вход 3 → ребро 3→4, четвёрка белая → вход 4, исходящих рёбер нет → выход 4, order=[4] → выход 3, order=[4,3] → выход 1, order=[4,3,1]. Внешний цикл: вершина 2 белая → вход 2 → ребро 2→3: тройка ЧЁРНАЯ, не идём → ребро 2→5: пятёрка белая → вход 5 → ребро 5→4: четвёрка чёрная, не идём → выход 5, order=[4,3,1,5] → выход 2, order=[4,3,1,5,2]. Вершины 3, 4, 5 уже чёрные - внешний цикл их пропускает. Переворачиваем: 2, 5, 1, 3, 4. Проверка рёбер: 1→3 - единица на третьем месте, тройка на четвёртом ✓; 2→3 - двойка первая ✓; 3→4 ✓; 2→5 - двойка перед пятёркой ✓; 5→4 - пятёрка вторая, четвёрка последняя ✓. Все пять рёбер смотрят вперёд. Заметь, что вершина 2 оказалась ПЕРВОЙ, хотя обход начинался с единицы: она вышла последней, а разворот поставил её в начало. Это хорошая проверка понимания - в топологическом порядке первой стоит не та вершина, с которой начали обход, а та, из которой вышли позже всех.

Главное

Топологический порядок - расстановка вершин ориентированного графа, при которой каждое ребро u → v ведёт вперёд. Существует ровно для ациклических графов: при цикле порядка нет в принципе, и алгоритм обязан сообщить об этом, а не выдать неверную расстановку. Получается из обхода в глубину тремя строками: записывать вершину в момент ВЫХОДА и в конце перевернуть список; цена O(V + E). Корректность следует из теоремы о скобках: для любого ребра u → v в ациклическом графе tout[u] > tout[v], потому что v либо раскрывается изнутри u, либо уже закончена; третий случай (серая v) - это и есть цикл. Порядок обычно НЕ единственный, поэтому проверять результат надо свойством «каждое ребро смотрит вперёд», а не сравнением с эталонной строкой. Типичные ошибки: записать вершину при входе, забыть разворот, не проверить цикл, забыть внешний цикл по вершинам. На этом алгоритме держатся системы сборки, пакетные менеджеры, планировщики, пересчёт формул и порядок запуска служб.