Сильно связные компоненты

Классическое применение поиска в глубину задача о разложении графа
на сильно связные компоненты. Мы покажем, как это можно сделать, дважды
выполнив поиск в глубину.

Многие алгоритмы, работающие на ориентированных графах, начинают с
отыскания сильно связных компонент: после этого задача решается отдельно для
каждой компоненты, а потом решения комбинируются в соответствии со связями
между компонентами. Эти связи можно представлять в виде так называемого
«графа компонент».

Алгоритм поиска сильно связных компонент графа G = (V, Е) будет ис-
пользовать «транспонированный» граф G^T = (V, Е^T), получаемый из
исходного обращением стрелок на рёбрах: Е^T = ((u, v): (v, и) E). Такой граф
можно построить за время O (V + Е) (мы считаем, что исходный и транспони-
рованный графы заданы с помощью списков смежных вершин). Легко понять,
что G и G^T имеют одни и те же сильно связные компоненты (поскольку v до-
стижимо из и в G^T, если и только если и достижимо из v в G^T). На рисунке
5.5(б) показан результат транспонирования графа рис. 5.5(а).

Рисунок 5.5 – Выделение сильно связных компонент

(а) Ориентированный граф G и его сильно связные компоненты (показаны
серым). Показан лес поиска в глубину и метки времени для графа G. (б) Транс-
понированный граф G. Показан лес поиска в глубину, вычисляемый в строке 3 процедуры STRONGLY-CONNECTED-COMPONENTS. Рёбра дерева обведены серым. Вершины b, с, g, h, являю-
щиеся корнями деревьев поиска в глубину (для графа G), выделены чёрным. (в) Ацикличе-
ский граф, который получится, если стянуть каждую сильно связную компоненту графа G
в точку.

Следующий алгоритм находит сильно связные компоненты ориентированно-
го графа G = (V, Е), используя два поиска в глубину – для G и для G^T; время
работы есть O (V + Е).