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

Если ты умеешь писать алгоритм Кана, знаешь его критерий цикла (выписано меньше V вершин) и понимаешь, как из него получаются уровни параллельности, листай до «Теперь сам».

Как думаешь, с чего начать, если обхода нет

Забудь на минуту про обход в глубину. Дан граф задач с зависимостями, и надо выдать порядок выполнения. Прежде чем читать дальше, ответь: какую задачу можно взять ПЕРВОЙ - по какому признаку её видно? И что изменится в графе, когда она сделана?

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

Разбор завала на складе. Взять можно только ту коробку, на которой ничего не стоит. Снял её - и коробки, которые она придавливала, могли освободиться; если освободились, их тоже можно брать. Так, слой за слоем, разбирается весь завал. А если в какой-то момент свободных коробок нет, а завал остался - значит там коробки стоят друг на друге по кругу, чего в реальности не бывает, а в графе зависимостей случается сплошь и рядом.

Механизм: считаем входящие степени

from collections import deque

indeg = [0] * V
for u in range(V):
    for v in adj[u]:
        indeg[v] += 1                 # считаем, сколько рёбер ВЕДЁТ в каждую вершину

q = deque(v for v in range(V) if indeg[v] == 0)   # готовые: ни от чего не зависят
order = []
while q:
    v = q.popleft()
    order.append(v)
    for u in adj[v]:
        indeg[u] -= 1                 # сняли ребро v → u
        if indeg[u] == 0:             # у соседа больше нет зависимостей
            q.append(u)

if len(order) < V:
    print("в графе цикл; в порядок попали только", len(order), "вершин")

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

Две полезные модификации:

уровни параллельности : обрабатывать не по одной вершине, а ВЕСЬ текущий слой очереди
                        целиком; число слоёв = длина самой длинной цепочки зависимостей
лексикографически
наименьший порядок    : из всех допустимых - тот, что раньше прочих уходит в
                        меньший номер (как слова в словаре). Заменить очередь на
                        очередь с ПРИОРИТЕТАМИ (кучу); цена станет O(V·log V + E)

Правило

Алгоритм Кана: посчитать входящие степени, положить в очередь все вершины с нулевой степенью; доставая вершину, выписывать её в ответ и уменьшать степень каждого соседа, добавляя в очередь тех, у кого степень стала нулём. Цена O(V + E). Если выписано меньше V вершин, в графе есть цикл, и невыписанное множество содержит циклы и всё, что от них зависит. Обработка очереди слоями даёт уровни параллельного выполнения; замена очереди кучей даёт лексикографически наименьший порядок (как слова в словаре) за O(V·log V + E).

Разбор: разбираем граф по шагам и по уровням

Граф: a→c, b→c, c→d, b→e, e→d.

Входящие степени: a: 0, b: 0, c: 2 (из a и b), d: 2 (из c и e), e: 1 (из b).

очередь: [a, b]                  order = []
взяли a  → снимаем a→c: indeg[c] = 1            order = [a]
взяли b  → снимаем b→c: indeg[c] = 0 → в очередь
           снимаем b→e: indeg[e] = 0 → в очередь  order = [a, b],  очередь: [c, e]
взяли c  → снимаем c→d: indeg[d] = 1            order = [a, b, c]
взяли e  → снимаем e→d: indeg[d] = 0 → в очередь order = [a, b, c, e]
взяли d                                          order = [a, b, c, e, d]

Выписаны все пять вершин - циклов нет, порядок годится: проверь, что каждое из пяти рёбер смотрит вперёд.

Теперь то же самое СЛОЯМИ. Первый слой - всё, что было в очереди сначала: {a, b}. Снимаем их рёбра целиком, смотрим, кто освободился: {c, e} - это второй слой. Снимаем их рёбра: освободилась d - третий слой. Итого три уровня: {a, b}, {c, e}, {d}. Читается это так: если задачи внутри слоя выполнять параллельно, всё дело займёт три такта вместо пяти, а число тактов равно длине самой длинной цепочки зависимостей (a→c→d или b→e→d) - её называют критическим путём. Именно так планировщики сборки решают, что можно компилировать одновременно.

Разбор: почему застрявшие вершины - это в точности цикл

Пусть алгоритм остановился, а вершины остались. Докажем, что среди них есть цикл.

У каждой оставшейся вершины входящая степень больше нуля - иначе она лежала бы в очереди. Значит в каждую ведёт ребро из другой ОСТАВШЕЙСЯ вершины (рёбра из выписанных уже сняты). Теперь пойдём от любой оставшейся вершины ПРОТИВ стрелок: из неё всегда есть куда шагнуть назад, потому что входящая степень не ноль. Шагаем сколько угодно раз, а вершин конечное число - значит рано или поздно мы попадём в вершину, где уже были. Кусок пути между двумя посещениями и есть цикл.

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

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

Первое: уменьшать входящую степень и класть вершину в очередь без проверки на ноль - вершина попадёт в ответ несколько раз, и порядок сломается. Второе: считать входящие степени по неориентированному графу - там у каждого ребра два конца, и «нулевая входящая степень» ничего не значит; алгоритм работает только на ориентированных. Третье: остановиться, когда очередь опустела, и не сравнить len(order) с V - цикл останется незамеченным, а на выходе будет частичный порядок, который выглядит правдоподобно. Четвёртое: ждать от очереди лексикографического порядка - обычная очередь даёт какой-то допустимый порядок, для наименьшего нужна куча. Пятое: пересчитывать входящие степени заново после каждого снятия - это превращает O(V + E) в O(V·E); степени изменяются по месту.

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

Кан против обхода в глубину - выбор по обстоятельствам, и оба нужны. Алгоритм Кана ИТЕРАТИВЕН по своей природе, то есть не упирается в глубину рекурсии; он даёт понятное сообщение о циклической зависимости (вот застрявшие вершины) и естественно раскладывает задачи по уровням параллельности - именно поэтому его выбирают в системах сборки и планировщиках, где надо загрузить все ядра. Топологическая сортировка обходом в глубину короче и бесплатна, если обход всё равно делается (например, вместе с поиском компонент сильной связности - следующий урок). Практическое правило: нужен просто порядок и обход уже есть - бери обход; нужны уровни, отчёт о циклах или граф большой и глубокий - бери Кана. А уровни из Кана - это ещё и оценка «за сколько тактов это вообще можно сделать», то есть нижняя граница времени при любом числе исполнителей.

Теперь сам

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