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

Топологическая сортировка упорядочивает вершины ориентированного ациклического графа (DAG) так, что для каждого ребра u→v вершина u идёт раньше v. Применяется при планировании задач с зависимостями и сборке проектов.

Сложность: время O(V + E); память: O(V). Алгоритм Кана использует очередь вершин с нулевой входящей степенью; если в конце обработаны не все вершины — в графе есть цикл.

from collections import deque

def topo_sort(graph):
    indeg = {v: 0 for v in graph}
    for v in graph:
        for nb in graph[v]:
            indeg[nb] += 1
    q = deque([v for v in graph if indeg[v] == 0])
    order = []
    while q:
        v = q.popleft()
        order.append(v)
        for nb in graph[v]:
            indeg[nb] -= 1
            if indeg[nb] == 0:
                q.append(nb)
    return order