- Текущая
- Свободные или посещаемые
- Размещенные
- Цикл
Топологическая сортировка
Носки перед ботинками, фундамент перед стенами, курс перед курсом, который на нем строится. Топологическая сортировка выстраивает вершины графа с односторонними ребрами в ряд, где каждое ребро направлено вперед. Выберите алгоритм Кана или метод DFS и идите по шагам, чтобы увидеть, как растет порядок, а затем добавьте цикл, чтобы увидеть, почему тогда никакой порядок невозможен. Нажмите Пуск, чтобы посмотреть, как растет порядок, или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место. Каждое ребро одностороннее, как показывает стрелка: читайте его как "это идет перед тем". Выберите метод: алгоритм Кана сначала размещает вершины без входящих ребер, а число на каждой вершине — сколько входящих ребер у нее еще осталось; метод DFS ставит каждую вершину в начало, когда все, что идет после нее, уже размещено. Ряд под графом — порядок на данный момент. Отметьте Добавить цикл, чтобы увидеть, как каждый метод его находит. Кнопка Новый граф создает другой граф; выберите, сколько в нем вершин и ребер. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят в начало и в конец.
Как это работает
- Выберите алгоритм Кана или метод DFS.
- Нажмите Пуск или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место.
- Следите, как под графом растет порядок. Отметьте Добавить цикл, чтобы увидеть, как каждый метод его находит.
Алгоритм Кана
Посчитайте для каждой вершины, сколько ребер в нее входит. Вершина без входящих ребер ни от чего не зависит, поэтому может идти первой. Разместите такую вершину и удалите ее исходящие ребра: у вершин, в которые они вели, стало на одно входящее ребро меньше, и некоторые могут дойти до нуля и стать свободными. Размещайте свободные вершины, пока они не закончатся. Если какие-то вершины так и не стали свободными, они ждут друг друга в цикле, и топологического порядка не существует.
Метод DFS
Запустите поиск в глубину из каждой непосещенной вершины. Вершина обработана, когда обработано все, что из нее достижимо, а значит, все, что должно идти после нее, уже размещено. Ставьте каждую обработанную вершину в начало порядка — и порядок получится правильным. Если поиск идет по ребру к вершине, внутри которой он еще находится, это ребро замыкает цикл, и порядка снова не существует.
Часто задаваемые вопросы
Что такое топологическая сортировка?
Это упорядочение вершин ориентированного графа, в котором каждое ребро идет от более ранней вершины к более поздней. Если ребра означают "должно быть раньше", это порядок, в котором можно выполнить все задачи.
Когда существует топологический порядок?
Ровно тогда, когда в графе нет ориентированного цикла, то есть это ориентированный ациклический граф, или DAG. При наличии цикла каждая вершина на нем должна была бы идти раньше самой себя.
Единственен ли топологический порядок?
Обычно нет. Если две вершины не связаны цепочкой ребер, любая из них может идти первой, поэтому у графа может быть много допустимых порядков. Алгоритм Кана и метод DFS часто дают разные.
Насколько быстра топологическая сортировка?
Оба метода просматривают каждую вершину и каждое ребро фиксированное число раз, поэтому работа растет как число вершин плюс число ребер.
Отправляется ли мой граф куда-нибудь?
Нет. Граф создается и сортируется в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор