Русская Википедия:Топологическая сортировка
Топологическая сортировка — упорядочивание вершин ациклического ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин.
Пример
Для графа <math>G=\Bigl ( \bigl \{2, 3, 5, 7, 8, 9, 10, 11 \bigr \}, \bigl \{(3, 8), (3, 10), (5, 11), (7, 11), (7, 8), (8, 9), (11, 2), (11, 9), (11, 10)\bigr \}\Bigr )</math>
существует несколько согласованных последовательностей его вершин, которые могут быть получены при помощи топологической сортировки, например:
- <math>7, 5, 11, 3, 8, 2, 9, 10</math>
- <math>3, 7, 5, 8, 11, 10, 9, 2</math>
Видно, что в последовательности могут быть переставлены любые две стоящие рядом вершины, которые не входят в отношение частичного порядка <math>E</math>.
Алгоритм Кана (1962)
Один из первых алгоритмов, и наиболее приспособленный к исполнению вручную.
Пусть дан ациклический ориентированный простой граф <math>G=(V, E)</math>. Через <math>A(v), v \in V</math> обозначим множество таких вершин <math>u \in V </math>, что <math>\exists~ (u, v) \in E</math>. То есть <math>A(v)</math> — множество всех вершин, из которых есть дуга в вершину <math>v</math>. Пусть <math>P</math> — искомая последовательность вершин.
пока <math>|P| < |V|</math> выбрать любую вершину <math>v</math> такую, что <math>A(v) = \varnothing</math> и <math>v \notin P</math> <math>P \gets P, v</math> удалить <math>v</math> из всех <math>A(u), u \neq v</math>
Наличие хотя бы одного цикла в графе приведёт к тому, что на определённой итерации цикла не удастся выбрать новую вершину <math>v</math>.
Пример работы алгоритма
Пусть задан граф <math>G = \Bigl ( \bigl \{a, b, c, d, e \bigr \}, \bigl \{(a, b), (a, c), (a, d), (a, e), (b, d), (c, d), (c, e), (d,e) \bigr \} \Bigr )</math>. В таком случае алгоритм выполнится следующим образом:
| шаг | <math>v</math> | <math>A(a)</math> | <math>A(b)</math> | <math>A(c)</math> | <math>A(d)</math> | <math>A(e)</math> | <math>P</math> |
|---|---|---|---|---|---|---|---|
| 0 | <math>-</math> | <math>\varnothing</math> | <math>a</math> | <math>a</math> | <math>a, b, c</math> | <math>a, c, d</math> | <math>\varnothing</math> |
| 1 | <math>a</math> | <math>\varnothing</math> | <math>\varnothing</math> | <math>\varnothing</math> | <math>b, c</math> | <math>c, d</math> | <math>a</math> |
| 2 | <math>c</math> | <math>\varnothing</math> | <math>\varnothing</math> | <math>\varnothing</math> | <math>b</math> | <math>d</math> | <math>a, c</math> |
| 3 | <math>b</math> | <math>\varnothing</math> | <math>\varnothing</math> | <math>\varnothing</math> | <math>\varnothing</math> | <math>d</math> | <math>a, c, b</math> |
| 4 | <math>d</math> | <math>\varnothing</math> | <math>\varnothing</math> | <math>\varnothing</math> | <math>\varnothing</math> | <math>\varnothing</math> | <math>a, c, b, d</math> |
| 5 | <math>e</math> | <math>\varnothing</math> | <math>\varnothing</math> | <math>\varnothing</math> | <math>\varnothing</math> | <math>\varnothing</math> | <math>a, c, b, d, e</math> |
На втором шаге вместо <math>c</math> может быть выбрана вершина <math>b</math>, поскольку порядок между <math>b</math> и <math>c</math> не задан.
Алгоритм Тарьяна (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) от Никлауса Вирта
Литература
