Топологическая сортировка
Топологическая сортировка — упорядочивание вершин бесконтурного ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин.
Пример
Для графа
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/08/Directed_acyclic_graph.png/220px-Directed_acyclic_graph.png)
существует несколько согласованных последовательностей его вершин, которые могут быть получены при помощи топологической сортировки, например:
Видно, что в последовательности могут быть переставлены любые две стоящие рядом вершины, которые не входят в отношение частичного порядка .
Алгоритм Кана (1962)
Один из первых алгоритмов, и наиболее приспособленный к исполнению вручную.
Пусть дан бесконтурный ориентированный простой граф . Через обозначим множество таких вершин , что . То есть — множество всех вершин, из которых есть дуга в вершину . Пусть — искомая последовательность вершин.
пока выбрать любую вершину такую, что и удалить из всех
Наличие хотя бы одного контура в графе приведёт к тому, что на определённой итерации цикла не удастся выбрать новую вершину .
Пример работы алгоритма
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/Tred-G.svg/200px-Tred-G.svg.png)
Пусть задан граф . В таком случае алгоритм выполнится следующим образом:
шаг | |||||||
---|---|---|---|---|---|---|---|
0 | |||||||
1 | |||||||
2 | |||||||
3 | |||||||
4 | |||||||
5 |
На втором шаге вместо может быть выбрана вершина , поскольку порядок между и не задан.
Алгоритм Тарьяна (1976)
На компьютере топологическую сортировку можно выполнить за O(n) времени и памяти, если обойти все вершины, используя поиск в глубину, и выводить вершины в момент выхода из неё.
Другими словами алгоритм состоит в следующем:
- Изначально все вершины белые.
- Для каждой вершины делаем шаг алгоритма.
Шаг алгоритма:
- Если вершина чёрная, ничего делать не надо.
- Если вершина серая — найден цикл, топологическая сортировка невозможна.
- Если вершина белая
- Красим её в серый
- Применяем шаг алгоритма для всех вершин, в которые можно попасть из текущей
- Красим вершину в чёрный и помещаем её в начало окончательного списка.
Пример
Пример будет на том же графе, однако порядок, в котором выбираем вершины для обхода — c, d, e, a, b.
Шаг | Текущая | Белые | Стек (серые) | Выход (чёрные) |
---|---|---|---|---|
0 | — | a, b, c, d, e | — | — |
1 | c | a, b, d, e | c | — |
2 | d | a, b, e | c, d | — |
3 | e | a, b | c, d, e | — |
4 | d | a, b | c, d | e |
5 | c | a, b | c | d, e |
6 | — | a, b | — | c, d, e |
7 | d | a, b | — | c, d, e |
8 | e | a, b | — | c, d, e |
9 | a | b | a | c, d, e |
10 | b | — | a, b | c, d, e |
11 | a | — | a | b, c, d, e |
12 | — | — | — | a, b, c, d, e |
13 | b | — | — | a, b, c, d, e |
Применение
При помощи топологической сортировки строится корректная последовательность выполнения действий, всякое из которых может зависеть от другого: последовательность прохождения учебных курсов студентами, установки программ при помощи пакетного менеджера, сборки исходных текстов программ при помощи Makefile'ов.
Можно построить список отображения объектов в изометрической проекции зная парные порядковые отношения между объектами (какой из двух объектов должен быть прорисован раньше).
См. также
Ссылки
- Пример алгоритма топологической сортировки на Python, C++, Pascal
- Топологическая сортировка при помощи поиска в глубину — реализация на C++
- Топологическая сортировка на Pascal за O(n + m) от Никлауса Вирта
Литература
- Левитин А. В. Глава 5. Метод уменьшения размера задачи: Топологическая сортировка // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 220—224. — 576 с. — ISBN 978-5-8459-0987-9
- Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 22.4. Топологическая сортировка // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — С. 632-635. — ISBN 5-8459-0857-4.