Топологическая сортировка

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Топологическая сортировка — упорядочивание вершин бесконтурного ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин.

Пример[править | править вики-текст]

Для графа 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 )

Бесконтурный ориентированный граф

существует несколько согласованных последовательностей его вершин, которые могут быть получены при помощи топологической сортировки, например:

  • 7, 5, 11, 3, 8, 2, 9, 10
  • 3, 7, 5, 8, 11, 10, 9, 2

Видно, что в последовательности могут быть переставлены любые две стоящие рядом вершины, которые не входят в отношение частичного порядка E.

Алгоритм Кана (1962)[править | править вики-текст]

Один из первых алгоритмов, и наиболее приспособленный к исполнению вручную.

Пусть дан бесконтурный ориентированный простой граф G=(V, E). Через A(v), v \in V обозначим множество вершин таких, что u \in A(v) \Leftrightarrow (u, v) \in E. То есть, A(v) — множество всех вершин, из которых есть дуга в вершину v. Пусть P — искомая последовательность вершин.

пока |P| < |V|
  выбрать любую вершину v такую, что A(v) = \varnothing и v \notin P
  P \gets P, v
  удалить v из всех A(u), u \neq v

Наличие хотя бы одного контура в графе приведёт к тому, что на определённой итерации цикла не удастся выбрать новую вершину v.

Пример работы алгоритма[править | править вики-текст]

Tred-G.svg

Пусть задан граф 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 ). В таком случае алгоритм выполнится следующим образом:

шаг v A(a) A(b) A(c) A(d) A(e) P
0 - \varnothing a a a, b, c a, c, d \varnothing
1 a \varnothing \varnothing \varnothing b, c c, d a
2 c \varnothing \varnothing \varnothing b d a, c
3 b \varnothing \varnothing \varnothing \varnothing d a, c, b
4 d \varnothing \varnothing \varnothing \varnothing \varnothing a, c, b, d
5 e \varnothing \varnothing \varnothing \varnothing \varnothing a, c, b, d, e

На втором шаге вместо c может быть выбрана вершина b, поскольку порядок между b и c не задан.

Алгоритм Тарьяна (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 d a, b c, d e
6 c a, b c d, e
7 a, b c, d, e
8 d a, b c, d, e
9 e a, b c, d, e
10 a b a c, d, e
11 b a, b c, d, e
12 a a b, c, d, e
13 a, b, c, d, e
14 b a, b, c, d, e

Применение[править | править вики-текст]

При помощи топологической сортировки строится корректная последовательность выполнения действий, всякое из которых может зависеть от другого: последовательность прохождения учебных курсов студентами, установки программ при помощи пакетного менеджера, сборки исходных текстов программ при помощи Makefile'ов.

Можно построить список отображения объектов в изометрической проекции зная парные порядковые отношения между объектами (какой из двух объектов должен быть прорисован раньше).

Ссылки[править | править вики-текст]

Литература[править | править вики-текст]

  • Ананий В. Левитин Глава 5. Метод уменьшения размера задачи: Топологическая сортировка // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. — М.: «Вильямс», 2006. — С. 220-224. — ISBN 5-8459-0987-2
  • Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 22.4. Топологическая сортировка // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — С. 632-635. — ISBN 5-8459-0857-4