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

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

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

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

Для графа

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

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

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

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

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

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

пока 
  выбрать любую вершину  такую, что  и 
  
  удалить  из всех 

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

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

Tred-G.svg

Пусть задан граф . В таком случае алгоритм выполнится следующим образом:

шаг
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'ов.

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

См. также[править | править вики-текст]

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

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