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

Учебный план, сборка проекта, зависимости пакетов: одни задачи должны идти после других. Такие зависимости записываются ориентированным графом: ребро u -> v значит «u раньше v». Топологическая сортировка выстраивает вершины так, чтобы все рёбра шли слева направо.

DAG и условие порядка

• Порядок существует только в ориентированном графе без циклов (DAG).
• Для каждого ребра u -> v вершина u стоит раньше v.
• Порядок обычно не единственный: независимые вершины могут идти в любой последовательности.
• При цикле порядка нет: a -> b -> a требует «a раньше b и b раньше a».

Алгоритм Кана

Входящая степень — число рёбер, входящих в вершину. Вершина со степенью 0 ни от чего не зависит, с неё можно начинать.

deps = {
    "python": ["algorithms", "databases"],
    "math": ["algorithms", "statistics"],
    "algorithms": ["ml"],
    "databases": ["web"],
    "statistics": ["ml"],
    "ml": [],
    "web": [],
}

indegree = {node: 0 for node in deps}
for node in deps:
    for nxt in deps[node]:
        indegree[nxt] += 1
print(indegree)
print("sources:", [n for n in deps if indegree[n] == 0])

{'python': 0, 'math': 0, 'algorithms': 2, 'databases': 1, 'statistics': 1, 'ml': 2, 'web': 1}
sources: ['python', 'math']

1. Поставьте в очередь все вершины со степенью 0.
2. Возьмите вершину из очереди и запишите в результат.
3. Уменьшите степень каждого соседа на 1; тех, у кого стало 0, поставьте в очередь.
4. Повторяйте, пока очередь не пуста.