Раздел «Алгоритмы».StrongConnectivity:

Выделение сильно связных компонент графа

Постановка задачи

Две вершины A, B ориентированного графа называются сильно, связанными если есть пути из A в B и из B в A. Отношение сильной связанности транцитивно, то есть если A сильно связана с B, а B сильно связана с C, то A сильно связана с C.

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

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

Идея решения

Для выделения сильно связных компонент используют два поиска в глубину.

1-ый раз на исходном графе, 2-ой на транспонированном (исходный граф, в котором обращены все разрешенные направления).


Strongly-Connected-Components(G)
  1. С помощью DFS(G), для каждой вершины u, найти время окончания обработки - f[u]
  2. Построить GT - транспонированный граф
  3. Вызвать DFS(GT), при этом в его внешнем цикле перебирать вершины в порядке убывания величины f[u] (вычисленной в 1-ой строке)
  4. Сильно связными компонентами будут деревья поиска, построенные на шаге 3.

Доказательство правильности алгоритма можно найти, например, в книге "Алгоритмы. Построение и анализ" Т. Кормен, Ч. Лейзерсон, Р. Ривест ("Introduction to Algorithms" Thomas Cormen, Charles Leiserson, Roland Rivest) на странице 456.

Примеры кода

-- VladimirSitnikov - 02 Apr 2004

AlgorithmClasifyForm
Type: Теория
Scope: Графы
Strategy: Перебор с возвратом
Complexity: Medium