Алгоритм Кана: топологическая сортировка простыми словами

Короткий ответ. Алгоритм Кана это топологическая сортировка через подсчёт входящих рёбер. Берём вершины, в которые ничего не ведёт, снимаем их, уменьшаем счётчики соседей. Повторяем, пока есть что снимать. Если сняли не все вершины, в графе цикл. Ниже код на Python, где он нужен и на чём он ломается.

Что делает топологическая сортировка?

Она выстраивает вершины ориентированного графа в ряд. Каждое ребро в нём идёт слева направо.

Пример из жизни. Курсы в университете и их зависимости. Топологический порядок это порядок, в котором их можно пройти.

Работает только на графе без циклов. Если A требует B, а B требует A, порядка нет.

Как работает алгоритм Кана?

Четыре шага, и все они простые.

• Для каждой вершины считаем, сколько рёбер в неё входит. Это in-degree.
• Все вершины с in-degree 0 кладём в очередь.
• Снимаем вершину из очереди, добавляем в ответ. У всех её соседей уменьшаем in-degree на 1.
• Сосед дошёл до нуля, кладём его в очередь.

Проследим на графе с рёбрами A→C, B→C, C→D.

Шаг	Очередь	Снимаем	Ответ
0	A, B
1	B	A	A
2	C	B	A, B
3	D	C	A, B, C
4		D	A, B, C, D

C попал в очередь только на шаге 2. До этого в него вели два ребра, и оба надо было снять.

Как написать алгоритм Кана на Python?

Граф задан списком рёбер. Вершины пронумерованы от 0 до n-1.

from collections import deque

def kahn(n, edges):
    graph = [[] for _ in range(n)]
    indegree = [0] * n
    for a, b in edges:
        graph[a].append(b)
        indegree[b] += 1

    queue = deque(v for v in range(n) if indegree[v] == 0)
    order = []

    while queue:
        v = queue.popleft()
        order.append(v)
        for w in graph[v]:
            indegree[w] -= 1
            if indegree[w] == 0:
                queue.append(w)

    if len(order) != n:
        return None  # в графе есть цикл
    return order

Проверка на цикл встроена. Вершина из цикла никогда не дойдёт до нуля. В ответ она не попадёт.

Сложность O(V + E). Каждую вершину снимаем один раз, каждое ребро уменьшаем один раз.

Когда алгоритм Кана нужен в задаче?

Слова в условии, по которым его узнают.

• «Курсы и пререквизиты», «можно ли пройти все курсы».
• «Порядок сборки», «зависимости пакетов», «порядок задач».
• «Найди любой порядок, в котором…».
• «Есть ли цикл в ориентированном графе».
• «Восстанови алфавит по отсортированным словам».

Общий признак: направленные зависимости. Нужен порядок, или проверка, что он существует.

Сигналы, соседи паттерна и шаблоны на шести языках на странице топологической сортировки.

Чем алгоритм Кана отличается от DFS-варианта?

Топологическую сортировку делают двумя способами. Оба дают верный порядок.

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

На собеседовании чаще ждут Кана. Его проще объяснить вслух, а это половина оценки.

Как решить Course Schedule алгоритмом Кана?

Условие. Есть n курсов. Пары вида «сначала b, потом a». Можно ли пройти все?

Читаем как граф. Каждая пара это ребро b→a. Вопрос: есть ли в графе цикл.

Запускаем kahn. Вернул порядок, ответ «да». Вернул None, ответ «нет».

Course Schedule II просит сам порядок. Тот же код, возвращаем список вместо да или нет.

Проговорим маленький случай. n = 3, пары (1, 0) и (2, 1). Входящие: 0, 1, 1. В очереди сначала 0. Сняли 0, освободилась 1. Сняли 1, освободилась 2. Порядок: 0, 1, 2.

Добавим пару (0, 2). У всех вершин по одному входящему ребру. Очередь пуста с самого начала, ответ «нет».

Как объяснить алгоритм Кана на собеседовании?

Три фразы до кода, в таком порядке.

• «Зависимости это ориентированный граф. Нужен топологический порядок.»
• «Считаю входящие рёбра и начинаю с вершин без них. Снятая вершина освобождает соседей.»
• «Каждая вершина и каждое ребро трогаются один раз, O(V + E). Порядок короче n, значит цикл.»

Потом код. Потом трассировка на трёх вершинах. Сложность в конце ещё раз.

На чём ломается алгоритм Кана?

Три ошибки, которые встречаются чаще других.

• Ребро прочитано в обратную сторону. Порядок выходит зеркальный, тесты красные.
• Забыта проверка len(order) != n. Граф с циклом даёт неполный ответ без ошибки.
• Вместо очереди взят список с pop(0). Это O(n) на каждый шаг.

Как закрепить алгоритм Кана?

Напиши kahn по памяти. Потом реши Course Schedule и Course Schedule II. Это одна и та же задача, вторая просит порядок.

Через день напиши снова без подглядывания. Как это работает, объяснено в статье про интервальные повторения.

Вопросы и ответы

Какая сложность у алгоритма Кана?

O(V + E) по времени и O(V + E) по памяти на список смежности.

Что вернёт алгоритм Кана на графе с циклом?

Неполный порядок. Поэтому в конце сравнивают длину ответа с числом вершин.

Порядок единственный?

Нет. Если в очереди две вершины, любую можно взять первой. Оба порядка верные.

Почему очередь, а не стек?

Со стеком алгоритм тоже верен. Очередь даёт порядок по слоям, который чаще просят.