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

Question

Accepted Answer

**Topological sort** линейно упорядочивает вершины **DAG** (ориентированный ациклический граф) так, чтобы для каждого ребра u->v вершина u находилась **раньше** v. Она отвечает на вопрос "в каком порядке я могу выполнить эти задачи, учитывая их зависимости?"

## Идея

Два распространённых подхода: **алгоритм Кана** (повторно удаляйте узлы с входящей степенью 0) или **DFS** (reverse post-order). Корректный порядок существует **только если нет цикла**.

## Пример (алгоритм Кана)

```python
from collections import deque

def topo_sort(graph):
    indeg = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            indeg[v] += 1                 # count incoming edges
    queue = deque([u for u in indeg if indeg[u] == 0])
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1                 # "remove" the edge
            if indeg[v] == 0:
                queue.append(v)
    return order if len(order) == len(graph) else None  # None -> cycle

topo_sort({'shirt': ['tie'], 'tie': ['jacket'], 'jacket': []})
# -> ['shirt', 'tie', 'jacket']
```

## Сложность

- **Время:** O(V + E). **Память:** O(V).

## Когда использовать / ловушки

Используйте для **систем сборки**, планирования задач, предусловий курсов и разрешения зависимостей. Если результат короче V, граф содержит **цикл** (нет корректного порядка). Упорядочивание в целом **не уникально**.

## Почему это важно

Упорядочивание зависимостей встречается везде — компиляторы, менеджеры пакетов, пересчёт электронных таблиц, CI конвейеры.

Топологическая сортировка также используется для обнаружения циклов в ориентированных графах.

Распознание проблемы как "упорядочивание с ограничениями" и применение топологической сортировки — это признак опытного разработчика.