Топологическая сортировка (алгоритм Кана)

Topological sort (Kahn's algorithm)

O(V+E)

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

Elman HuseynovОбновлено 17 окт. 2026 г.

Топологическая сортировка (алгоритм Кана): как это работает?

Посчитайте, сколько рёбер входит в каждую вершину. Это число называют входящей степенью.

Положите в очередь все вершины с нулевой входящей степенью. Они никому не должны и идут первыми.

Достаньте вершину и допишите её в ответ. Теперь она расставлена окончательно.

Пройдите по её исходящим рёбрам и уменьшите счётчик каждой цели. У цели стало на один долг меньше.

Счётчик, дошедший до нуля, попадает в очередь. Все её зависимости уже расставлены.

Если ответ короче числа вершин, в графе есть цикл. Вершины в цикле нуля не достигают.

Источники: Википедия: Топологическая сортировка, Kahn (1962), Topological sorting of large networks (англ.)

степени: A 0, B 1, C 1, D 2Рёбра это A в B, A в C, B в D и C в D.
очередь = [A], ответ = []Никому не должна только A, она и есть точка старта.
берём A, ответ = [A]B и C теряют по одному долгу. Обе дошли до нуля.
очередь = [B, C]У D всё ещё два долга. Она ждёт.
ответ = [A, B, C, D]D входит, когда оба её долга закрыты.

Порядок задач по алгоритму Кана

topoSort(6, [[1, 2], [3], [3, 5], [4, 5], [], []])

число над задачей = сколько задач она ещё ждёт

queue (готовы к запуску)

пусто

order

пусто

Стрелка u → v значит, что u должна выполниться раньше v. Считаем входящие стрелки у каждой задачи.

1 / 16

Топологическая сортировка (алгоритм Кана): шаблон кода

function topoSort(n, adj) {
    const indeg = new Array(n).fill(0);
    for (const u in adj) for (const v of adj[u]) indeg[v]++;
    const queue = [];
    for (let i = 0; i < n; i++) if (indeg[i] === 0) queue.push(i);
    const order = [];
    while (queue.length) {
        const u = queue.shift();
        order.push(u);
        for (const v of adj[u] || []) {
            if (--indeg[v] === 0) queue.push(v);
        }
    }
    return order.length === n ? order : null; // null: a cycle exists
}

function topoSort(n: number, adj: number[][]): number[] | null {
    const indeg = new Array<number>(n).fill(0);
    for (const edges of adj) for (const v of edges) indeg[v]++;
    const queue: number[] = [];
    for (let i = 0; i < n; i++) if (indeg[i] === 0) queue.push(i);
    const order: number[] = [];
    while (queue.length) {
        const u = queue.shift()!;
        order.push(u);
        for (const v of adj[u] ?? []) {
            if (--indeg[v] === 0) queue.push(v);
        }
    }
    return order.length === n ? order : null; // null: a cycle exists
}

from collections import deque

def topo_sort(n, adj):
    indeg = [0] * n
    for u in adj:
        for v in adj[u]:
            indeg[v] += 1
    queue = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj.get(u, []):
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)
    return order if len(order) == n else None  # None: a cycle exists

function topoSort(int $n, array $adj): ?array {
    $indeg = array_fill(0, $n, 0);
    foreach ($adj as $u => $neighbors) {
        foreach ($neighbors as $v) $indeg[$v]++;
    }
    $queue = [];
    for ($i = 0; $i < $n; $i++) if ($indeg[$i] === 0) $queue[] = $i;
    $order = [];
    while ($queue) {
        $u = array_shift($queue);
        $order[] = $u;
        foreach ($adj[$u] ?? [] as $v) {
            if (--$indeg[$v] === 0) $queue[] = $v;
        }
    }
    return count($order) === $n ? $order : null; // null: a cycle exists
}

    public static List<Integer> topoSort(int n, List<List<Integer>> adj) {
        int[] indeg = new int[n];
        for (List<Integer> edges : adj) for (int v : edges) indeg[v]++;
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) if (indeg[i] == 0) queue.add(i);
        List<Integer> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            int u = queue.poll();
            order.add(u);
            for (int v : adj.get(u)) {
                if (--indeg[v] == 0) queue.add(v);
            }
        }
        return order.size() == n ? order : null; // null: a cycle exists
    }

    public static List<int> TopoSort(int n, List<List<int>> adj) {
        var indeg = new int[n];
        foreach (var edges in adj) foreach (int v in edges) indeg[v]++;
        var queue = new Queue<int>();
        for (int i = 0; i < n; i++) if (indeg[i] == 0) queue.Enqueue(i);
        var order = new List<int>();
        while (queue.Count > 0) {
            int u = queue.Dequeue();
            order.Add(u);
            foreach (int v in adj[u]) {
                if (--indeg[v] == 0) queue.Enqueue(v);
            }
        }
        return order.Count == n ? order : null; // null: a cycle exists
    }

Топологическая сортировка (алгоритм Кана): разбор примера

Порядок, в котором можно пройти все курсы

Дано число курсов и список пар с предварительными требованиями. Верните порядок, в котором можно пройти всё.

Если такого порядка нет, верните пустой список.

Постройте список смежности и входящие степени за один проход.

Потом крутите цикл очереди. Ответ короче числа курсов означает цикл.

function findOrder(numCourses, prerequisites) {
    const next = Array.from({ length: numCourses }, () => []);
    const indegree = new Array(numCourses).fill(0);

    for (const [course, needs] of prerequisites) {
        next[needs].push(course);
        indegree[course]++;
    }

    const queue = [];
    for (let i = 0; i < numCourses; i++) {
        if (indegree[i] === 0) queue.push(i);
    }

    const order = [];
    for (let i = 0; i < queue.length; i++) { // index walk, never shift
        const node = queue[i];
        order.push(node);

        for (const target of next[node]) {
            if (--indegree[target] === 0) queue.push(target);
        }
    }

    // a short answer means some nodes never reached zero
    return order.length === numCourses ? order : [];
}

Топологическая сортировка (алгоритм Кана): когда применять?

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

задача должна идти перед другой
порядок, соблюдающий зависимости
обнаружить цикл в предпосылках
порядок сборки / расписание курсов / порядок установки
ориентированный граф, X должен произойти перед Y

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

Топологическая сортировка (алгоритм Кана): с чем путают?

Паттерн «Топологическая сортировка (алгоритм Кана)» чаще всего путают с этими паттернами: Обход графа BFS / DFS, Компоненты связности, Система непересекающихся множеств и Жадный алгоритм (обменный аргумент).

Обход графа BFS / DFS (Graph BFS / DFS): Обычный обход посещает вершины в любом удобном порядке. Здесь порядок и есть ответ.
Компоненты связности (Connected components): Компоненты не смотрят на направление и только группируют вершины. Здесь направление задаёт весь ответ.
Система непересекающихся множеств (Union-find (disjoint set)): Она считает любое ребро ненаправленным. Направление здесь и есть самое главное.
Жадный алгоритм (обменный аргумент) (Greedy (exchange argument)): Правило жадное: берите всё, у чего не осталось долгов. Удаление вершины не может добавить зависимость.

Топологическая сортировка (алгоритм Кана): частые ошибки

Строят рёбра в обратную сторону
Пара читается как курс и требование к нему. Переворот молча решает совсем другую задачу.
Не проверяют длину в конце
Цикл даёт короткий ответ, а не ошибку. Сравните длину с числом вершин.
Ждут единственный правильный порядок
Готовых вершин в один момент бывает несколько. Любой порядок среди них верен.
Берут shift на очереди
В JavaScript это O(n) на каждое удаление. Идите по массиву индексом.

Паттерн «Топологическая сортировка (алгоритм Кана)» решает такие задачи с собеседований: Расписание курсов, Расписание курсов II, Словарь инопланетян, Деревья минимальной высоты, Восстановление последовательности, Параллельные курсы и Сортировка элементов по группам.

Расписание курсов: Нужно только знать, существует ли порядок.
Расписание курсов II: Нужен сам порядок, а не ответ да или нет.
Словарь инопланетян: Рёбра выводятся сравнением соседних слов.
Деревья минимальной высоты: Здесь слои листьев снимают снаружи внутрь.
Восстановление последовательности: Проверьте, что на каждом шаге готова ровно одна вершина.
Параллельные курсы: Считаются раунды, а не выдаётся порядок.
Сортировка элементов по группам: Два порядка: внутри групп и между ними.