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

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

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

Алгоритм поиска сильно связных компонент графа 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 + Е).

Листинг 5.7 – Алгоритм поиска сильно связных компонент