Топологическая сортировка | это... Что такое Топологическая сортировка? (original) (raw)

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

Содержание

1 Пример
2 Алгоритм
- 2.1 Пример работы алгоритма
3 Применение
4 Ссылки
5 Литература

Пример

Для графа $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 )$

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

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

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

Алгоритм

Пусть дан бесконтурный ориентированный простой граф G=(V, E) . Через $A(v), v \in V$ обозначим множество вершин таких, что $u \in A(v) \Leftrightarrow (u, v) \in E$ . То есть, A(v) — множество всех вершин, из которых есть дуга в вершину . Пусть — искомая последовательность вершин.

пока |P| < |V| выбрать любую вершину такую, что $A(v) = \{\varnothing\}$ и $v \notin P$ $P \gets P, v$ удалить из всех $A(u), u \neq 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 )$ . В таком случае алгоритм выполнится следующим образом:

шаг
0	$\varnothing$					$\varnothing$
1	$\varnothing$	$\varnothing$	$\varnothing$
2	$\varnothing$	$\varnothing$	$\varnothing$
3	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$
4	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$
5	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$

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

Применение

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

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

Ссылки

Литература

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

Алгоритмы сортировки
Теория	Сложность • О-нотация • Отношение порядка • Типы сортировки: Устойчивая • Внутренняя • Внешняя
Алгоритмы	Обменные: Пузырьком • Перемешиванием • Гномья • Быстрая • Расчёской • Выбором: Выбором • Пирамидальная • Вставками: Вставками • Шелла • Деревом • Слиянием: Слиянием • Без дополнительной памяти • Без сравнений: Подсчётом • Поразрядная • Блочная • Гибридные: Introsort • Timsort • Прочее: Топологическая • Сети • Непрактичные: Bogosort • Stooge sort • Глупая • Блинная

Алгоритмы сортировки

Теория

Сложность • О-нотация • Отношение порядка • Типы сортировки: Устойчивая • Внутренняя • Внешняя

Алгоритмы

Обменные: Пузырьком • Перемешиванием • Гномья • Быстрая • Расчёской • Выбором: Выбором • Пирамидальная • Вставками: Вставками • Шелла • Деревом • Слиянием: Слиянием • Без дополнительной памяти • Без сравнений: Подсчётом • Поразрядная • Блочная • Гибридные: Introsort • Timsort • Прочее: Топологическая • Сети • Непрактичные: Bogosort • Stooge sort • Глупая • Блинная