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

Сначала берём то, что ничего не ждёт, и вычёркиваем его из чужих зависимостей: от этого освобождается следующее. Порядок складывается за один проход, а если в какой-то момент свободного нет, значит, зависимости зациклились.

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

Пример задачи: курсы A–F; стрелка X → Y значит, что X нужно пройти раньше Y: A → C, B → C, B → E, C → D, D → F, E → F. В каком порядке пройти все курсы? Ответ: A, B, C, E, D, F.

A0B0C2D1E1F2очередьначало слева—порядок—
ждёт другие курсыв очередитекущий курскуда ведёт стрелкав порядке

Считаем стрелки, входящие в каждый курс

01/39
сначала · назад · пуск · шаг
Скорость
1function courseOrder(graph):
2 indegree = arrows into each course
3 queue = courses with indegree 0
4 order = []
5 while queue is not empty:
6 course = queue.popFront()
7 order.pushBack(course)
8 for next in graph[course]:
9 decrease indegree[next] by 1
10 if indegree[next] is 0:
11 queue.pushBack(next)
12 return order
состояние
indegree
{A: 0, B: 0, C: 2, D: 1, E: 1, F: 2}
queue
–
order
–
course
–
next
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Как узнать

задачи с зависимостями, например курсы, которые надо пройти раньше других, порядок сборки или «a должно идти раньше b», а также поиск цикла в ориентированном графе.

Как решать такие задачи

  1. Проведи стрелку от каждой задачи к задачам, которые от неё зависят. Посчитай входящую степень каждой вершины: сколько стрелок в неё входит.
  2. Положи в очередь все вершины со степенью 0: их ничто не держит.
  3. Бери из начала очереди и добавляй в порядок. Уменьшай степень каждой вершины, на которую она указывает, и клади в очередь те, у кого стало 0.
  4. Если порядок вышел короче, чем число вершин, в графе есть цикл и правильного порядка нет.

Где встречается

  • Сборка программ. make и Bazel собирают файлы в таком порядке, чтобы всё, от чего файл зависит, было готово раньше. Если зависимости замкнулись, make предупреждает о цикле.
  • Excel. Excel пересчитывает ячейки в порядке зависимостей: сначала те, на которые ссылаются, потом те, что ссылаются на них. Если формулы ссылаются друг на друга по кругу, он сообщает о циклической ссылке.
  • Python. В стандартной библиотеке есть graphlib.TopologicalSorter: он выдаёт задачи, у которых готовы все зависимости, и сообщает об ошибке, если есть цикл.