Топологическая сортировка
Каждый раз, когда вы устанавливаете программу, собираете проект или планируете работу, что-то должно решить, что делать сначала. Если задаче B нужна задача A, то A должна идти раньше. Топологическая сортировка превращает сеть таких правил в одну прямую линию.
Идея
Нарисуйте каждую задачу как вершину, а каждое правило "A перед B" — как стрелку из A в B. Топологический порядок — это ряд из всех вершин, в котором каждая стрелка направлена вправо. Это называют сортировкой, потому что вещи расставляются по порядку, но, в отличие от сортировки чисел, нужно соблюдать только стрелки: вершины, которые не связывает ни одна цепочка стрелок, могут идти в любом порядке.
Когда это невозможно
Если стрелки образуют цикл, например A перед B, B перед C и C перед A, то A должна идти раньше самой себя. Поэтому топологический порядок существует ровно тогда, когда в графе нет ориентированного цикла. Такой граф называется ориентированным ациклическим графом, или DAG. Оба метода ниже находят цикл, если он есть, поэтому они служат и удобной проверкой на циклы.
Пример
Возьмем стрелки A → C, B → C, B → D, C → E и D → E. Алгоритм Кана считает входящие стрелки: у A и B их нет, поэтому первой идет A, затем B. Удаление стрелок из B освобождает C и D, которые идут следом, а затем E: порядок A, B, C, D, E. Метод DFS посещает A, затем C, затем E; первой обрабатывается E, затем C, затем A, и каждая встает в начало. Потом он посещает B и D, которые обрабатываются и встают перед ними: порядок B, D, A, C, E. Оба порядка верны.
Кан или DFS?
Алгоритм Кана, опубликованный Артуром Каном в 1962 году, работает вперед: он всегда знает, какие задачи можно начать прямо сейчас, что удобно для планирования, и может выбирать среди свободных задач по любому правилу, например по алфавиту. Метод DFS, который популяризировал Роберт Тарьян в 1976 году, работает назад от концов и требует только поиска в глубину. В обоих время растет как число вершин плюс число ребер.
Применения
Системы сборки, такие как make, компилируют файлы после файлов, от которых они зависят. Менеджеры пакетов устанавливают библиотеки в порядке зависимостей. Электронные таблицы пересчитывают ячейку после ячеек, которые использует ее формула. Университеты проверяют, можно ли выполнить требования к предварительным курсам, компиляторы упорядочивают инструкции, а конвейеры данных запускают каждый шаг, когда готовы его входные данные. Команда Unix tsort сама выполняет топологическую сортировку.
Попробуйте сами
Откройте приложение и нажмите Шаг. Стрелки говорят, какая вершина должна идти перед какой. В алгоритме Кана число на каждой вершине — это оставшиеся входящие стрелки, а свободные вершины синие. В методе DFS синие вершины посещаются, а зеленые уже размещены. Порядок растет в ряду под графом. Отметьте Добавить цикл и смотрите, как оба метода обнаруживают, что порядка не существует.
Часто задаваемые вопросы
Что здесь значит «топологическая»?
Название происходит от топологии — науки о том, как вещи связаны, а не об их точной форме. Порядок зависит только от того, какие вершины соединены стрелками, а не от того, где они нарисованы.
Как найти цикл, если порядка нет?
Метод DFS показывает его напрямую: ребро к вершине, которая еще посещается, вместе с путем посещаемых вершин и есть цикл. Алгоритм Кана сообщает только, какие вершины застряли; поиск среди них находит цикл.
Можно ли выбрать определенный порядок среди допустимых?
Да. Когда в алгоритме Кана свободны несколько вершин, выберите ту, которую предпочитаете, например с наименьшей буквой или самую срочную задачу. Очередь с приоритетом дает порядок, который идет первым по алфавиту.
Как топологическая сортировка помогает искать кратчайшие пути?
В ориентированном ациклическом графе обновление расстояний по ребрам каждой вершины в топологическом порядке находит все кратчайшие пути от старта за один проход, даже с отрицательными ребрами, и быстрее, чем алгоритм Дейкстры или Беллмана — Форда.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Попробовать топологическую сортировку