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

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

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

Пример[править | править код]

Для графа

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

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

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

Алгоритм Кана (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'ов.

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

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

Ссылки[править | править код]

Литература[править | править код]