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

Топологическая сортировка, задача о разбиении графа на сильно связанные компоненты

Пусть имеется ориентированный граф без циклов (directed acyclic graph; это
английское название иногда сокращают до «dag»). Задача о топологической сор-
тировке (topological sort) этого графа состоит в следующем: надо указать такой
линейный порядок на его вершинах, что любое ребро ведёт от меньшей вершины
к большей (в смысле этого порядка). Очевидно, что если в графе есть циклы,
такого порядка не существует. Можно сформулировать задачу о топологической
сортировке и так: расположить вершины графа на горизонтальной прямой так,
чтобы все рёбра шли слева направо. (Слово «сортировка» не должно вводить в заблуждение: эта задача весьма отличается от обычной задачи сортировки.)

Вот пример ситуации, в которой возникает такая задача. Рассеянный про-
фессор одевается по утрам, причём какие-то вещи обязательно надо надевать
до каких-то других (например, носки – до башмаков); в других случаях это
всё равно (носки и штаны, например). На рис. 5.4(а) требуемые соотношения
показаны в виде ориентированного графа: ребро (u, v) означает, что предмет и
должен быть надет до v. Топологическая сортировка этого графа, тем самым,
описывает возможный порядок одевания. Один из таких порядков показан на
рис. 5.4(б) (надо одеваться слева направо).

Рисунок 5.4 – Пример топологической сортировки

На рис. 5.4 показан пример топологической сортировки. (а) Профессор топологически сортирует свою одежду по утрам. Ребро (u, v) означает, что u должно быть надето до v. Рядом с вершинами показаны времена
начала и конца обработки при поиске в глубину. (б) Граф топологически отсортирован
(вершины расположены в порядке убывания времени окончания обработки). Все рёбра идут
слева направо.

Следующий простой алгоритм топологически сортирует ориентированный
ациклический граф.

Листинг 5.6 – Топологическая сортировка

На рисунке 5.4(б) показан результат применения такого алгоритма: значения f [ v ] убывают слева направо.

Топологическая сортировка выполняется за время O (V + Е), потому что
столько времени занимает поиск в глубину, а добавить каждую из | V | вершин
к списку можно за время O (1).

Правильность этого алгоритма доказывается с помощью такой леммы:

Лемма 5.6. Ориентированный граф не имеет циклов тогда и только тогда, когда поиск в глубину не находит в нём обратных рёбер.

Доказательство. Обратное ребро соединяет потомка с предком и потому
замыкает цикл, образованный рёбрами дерева.

Пусть в графе имеется цикл с. Докажем, что в этом случае поиск
в глубину обязательно найдёт обратное ребро. Среди вершин цикла выберем
вершину v, которая будет обнаружена первой, и пусть (и, v)ведущее в неё
ребро цикла. Тогда в момент времени d [ v ] из v в и ведёт путь из белых вершин.
По теореме о белом пути и станет потомком v в лесе поиска в глубину,
поэтому (u, v) будет обратным ребром.

Теорема 5.7. Процедура TOPOLOGICAL-SORT(G} правильно выполняет топо
логическую сортировку ориентированного графа G без циклов.

Доказательство. Нужно доказать, что для любого ребра (u, v) выполнено не-
равенство f [ v ]< f [ u ]. В момент обработки этого ребра вершина и не может
быть серой (это означало бы, что она является предком и и (и, v)является
обратным ребром, что противоречит лемме 5.6). Поэтому v в этот момент
должна быть белой или чёрной. Если v белая, то она становится ребёнком и,
так что f [ v l < f [ и ]. Если она уже чёрная, то тем более f [ v ] < f [ и ].