Как узнать
задачи с зависимостями, например курсы, которые надо пройти раньше других, порядок сборки или «a должно идти раньше b», а также поиск цикла в ориентированном графе.
Как решать такие задачи
- Проведи стрелку от каждой задачи к задачам, которые от неё зависят. Посчитай входящую степень каждой вершины: сколько стрелок в неё входит.
- Положи в очередь все вершины со степенью 0: их ничто не держит.
- Бери из начала очереди и добавляй в порядок. Уменьшай степень каждой вершины, на которую она указывает, и клади в очередь те, у кого стало 0.
- Если порядок вышел короче, чем число вершин, в графе есть цикл и правильного порядка нет.
Где встречается
- Сборка программ. make и Bazel собирают файлы в таком порядке, чтобы всё, от чего файл зависит, было готово раньше. Если зависимости замкнулись, make предупреждает о цикле.
- Excel. Excel пересчитывает ячейки в порядке зависимостей: сначала те, на которые ссылаются, потом те, что ссылаются на них. Если формулы ссылаются друг на друга по кругу, он сообщает о циклической ссылке.
- Python. В стандартной библиотеке есть graphlib.TopologicalSorter: он выдаёт задачи, у которых готовы все зависимости, и сообщает об ошибке, если есть цикл.