---
title: "Алгоритм Кана: топологическая сортировка простыми словами"
url: https://algopath.pro/ru/blog/algoritm-kana
language: ru
summary: "Алгоритм Кана строит топологический порядок через подсчёт входящих рёбер. Трассировка по шагам, код на Python с проверкой на цикл, слова в условии, по которым его узнают, и три ошибки."
updated: 2026-09-26
---

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

**Короткий ответ.** Алгоритм Кана это топологическая сортировка через подсчёт входящих рёбер. Берём вершины, в которые ничего не ведёт, снимаем их, уменьшаем счётчики соседей. Повторяем, пока есть что снимать. Если сняли не все вершины, в графе цикл. Ниже код на 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). Каждую вершину снимаем один раз, каждое ребро уменьшаем один раз.

 

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

 

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

 

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

 

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

 

Сигналы, соседи паттерна и шаблоны на шести языках на странице [топологической сортировки](/ru/patterns/topological-sort).

 

## Чем алгоритм Кана отличается от 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. Это одна и та же задача, вторая просит порядок.

 

Через день напиши снова без подглядывания. Как это работает, объяснено в статье про [интервальные повторения](/ru/blog/intervalnye-povtoreniya).

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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