Топологическая сортировка - линейное упорядочивание всех его вершин. Предположим, что граф не содержит циклов, так как если он содержит циклы, то такая сортировка не возможна.
Граф, который не содержит циклов, называется ациклическим.
Ориентированные ациклические графы используются для указания последовательности действия, где каждое действие зависит от других. Например: установка программ с помощью системы управления пакетами или сборка с помощью Makefil'ов. (wikipedie (c))
Топологическая сортировка проводится с помощью поиска в глубину, которая описана в моем блоге: Поиск в глубину
Суть топологической сортировки можно связать с временем закрытия. Чем больше время закрытия, тем первее будет вершина графа в сортировке.
Пример отсортированного графа:
На рисунке представлена последовательность одевания утром. Первым делом идут носки (socks), потом трусы (undershorts) и самым последним идет пиджак у него время закрытия 4.
Для реализации топологической сортировки нам всего лишь нужно добавить в реализацию поиска в глубину глобальный стэк для вершин - stack<unsigned int> answer;
И! где мы красим вершину в черный после цикла, добавим добавление вершины в стек:
Приложение: поиск кратчайшего пути в ациклическом графе.
Алгоритм выглядит так:
Граф, который не содержит циклов, называется ациклическим.
Ориентированные ациклические графы используются для указания последовательности действия, где каждое действие зависит от других. Например: установка программ с помощью системы управления пакетами или сборка с помощью Makefil'ов. (wikipedie (c))
Топологическая сортировка проводится с помощью поиска в глубину, которая описана в моем блоге: Поиск в глубину
Суть топологической сортировки можно связать с временем закрытия. Чем больше время закрытия, тем первее будет вершина графа в сортировке.
Пример отсортированного графа:
Для реализации топологической сортировки нам всего лишь нужно добавить в реализацию поиска в глубину глобальный стэк для вершин - stack<unsigned int> answer;
И! где мы красим вершину в черный после цикла, добавим добавление вершины в стек:
answer.push(u);
Приложение: поиск кратчайшего пути в ациклическом графе.
Алгоритм выглядит так:
- Сначала делаем топологическую сортировку графа
- Для каждой вершины u в порядке топологической сортировки
- Для каждой смежной вершине v к вершине u
- Делаем релаксацию, т.е. запускаем старую добрую RELAX(u,v,w)
0 коммент.:
Отправить комментарий