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

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

ПримерПравить

Для графа  

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

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

  •  
  •  

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

Алгоритм Кана (1962)Править

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

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

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

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

Пример работы алгоритмаПравить

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

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

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

См. такжеПравить

СсылкиПравить

ЛитератураПравить