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

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

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

Алгоритм

Пусть дан бесконтурный ориентированный простой граф 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) = {пустое множество} и v не принадлежит P
• P <- P, v
• удалить v из всех A(u), u != v

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

Пример

Для графа

G=({2, 3, 5, 7, 8, 9, 10, 11},{(3, 8), (3, 10), (5, 11), (7, 11), (7, 8), (8, 9), (11, 2), (11, 9), (11, 10)})

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

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

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

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

Блок-схема работы алгоритма

Вывод по топологической сортировке

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