---
title: "Топологическая сортировка (алгоритм Кана)"
url: https://algopath.pro/ru/patterns/topological-sort
language: ru
summary: "Расставьте задачи так, чтобы каждая шла после всех, от которых она зависит. Каждый раз берите вершину, которая никому не должна."
updated: 2026-08-24
---

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

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

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

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

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

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

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

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

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

- `степени: 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 входит, когда оба её долга закрыты.

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

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

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

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

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

V вершин и E рёбер дают O(V + E). Каждое ребро убирается ровно один раз.

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

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

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

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

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

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

```javascript
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 : [];
}
```

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

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

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

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

## JavaScript

```javascript
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
}
```

## Python

```python
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
```

## PHP

```php
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
}
```