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

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

Пример

Для графа $G=\Bigl ( \bigl \{2, 3, 5, 7, 8, 9, 10, 11 \bigr \}, \bigl \{(3, 8), (3, 10), (5, 11), (7, 11), (7, 8), (8, 9), (11, 2), (11, 9), (11, 10)\bigr \}\Bigr )$

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

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

• $7, 5, 11, 3, 8, 2, 9, 10$
• $3, 7, 5, 8, 11, 10, 9, 2$

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

Алгоритм

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

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

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

Пусть задан граф $G = \Bigl ( \bigl \{a, b, c, d, e \bigr \}, \bigl \{(a, b), (a, c), (a, d), (a, e), (b, d), (c, d), (c, e), (d,e) \bigr \} \Bigr )$. В таком случае алгоритм выполнится следующим образом:

шаг	$v$	$A(a)$	$A(b)$	$A(c)$	$A(d)$	$A(e)$	$P$
0	$-$	$\varnothing$	$a$	$a$	$a, b, c$	$a, c, d$	$\varnothing$
1	$a$	$\varnothing$	$\varnothing$	$\varnothing$	$b, c$	$c, d$	$a$
2	$c$	$\varnothing$	$\varnothing$	$\varnothing$	$b$	$d$	$a, c$
3	$b$	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$	$d$	$a, c, b$
4	$d$	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$	$a, c, b, d$
5	$e$	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$	$a, c, b, d, e$

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

Применение

При помощи топологической сортировки строится корректная последовательность выполнения действий, всякое из которых может зависеть от другого: последовательность прохождения учебных курсов студентами, установки программ при помощи пакетного менеджера, сборки исходных текстов программ при помощи 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.