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

Пример

Для графа

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

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

Алгоритм

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

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

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

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

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

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

Применение

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

Ссылки

• Пример алгоритма топологической сортировки на Python, C++, Pascal
• Топологическая сортировка при помощи поиска в глубину — реализация на C++
• Топологическая сортировка на Pascal за O(n + m) от Никлауса Вирта

Литература

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