Алгоритм нахождения сильных компонент графа можно описать следующей последовательностью шагов

Шаг 1. G = (X, V) – данный граф. Определение сильных компонент графа (СК) начать с произвольной вершины х_iÎХ. Найти R(x_i) и Q(x_i). Положить СК(х_i) = - сильная компонента графа, содержащая вершину х_i.

Шаг 2. Определить множество . Если ¹Æ, то и перейти к шагу 1, иначе останов, так как все сильные компоненты определены.

Граф G*=(X*,V*) определяется так: каждая его вершина представляет множество вершин некоторой сильной компоненты графа G, дуга (x_i*, x_j*) существует в G* тогда и только тогда, когда в G существует дуга (x_i, x_j), такая, что x_i принадлежит ком­поненте, соответствующей вершине x_i*, а x_j –компоненте, соответствующей вершине x_j*. ГрафG* называют конденсациейграфа G.

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

Пример. Для графа G, приведенного на рис. 4.25, найти сильные ком­поненты и построить конденсацию G*.

Найдем СК в G, содержащую вершину x₁.

Из соотношений (4.3) и (4.4) получаем

R(x₁) ={ x₁ , x₂ , x₄ , x₅ , x₆ , x₇ , x₈ , x₉ , x₁₀ }

Q(x₁) ={ x₁ , x₂ , x₃ , x₅ , x₆ }

Следовательно, СК, содержащая вершину x₁, является порожденным подграфом

R(x₁) Q(x₁) = ({ x₁ , x₂ , x₅ , x₆ })

Аналогично, СК, содержащая вершину x₈, есть порожденный подграф ({x₈, x₁₀}), СК содержащая x₇ – подграф ({x₄, x₇, x₉}), СК, содержащая x₁₁, –подграф ({x₁₁, x₁₂, x₁₃ }) и СК, содержащая x₃, – подграф ({x₃}). Следует отметить, что последняя СК со­стоит из единственной вершины графа G. Конденсация G* приведена на рис. 4.26.

Рис. 4.26. G* - конденсация графа G

Процедуру, описанную выше и связанную с нахождением СК графа, можно сделать более удобной, если непосредственно исполь­зовать матрицыR и Q. Пусть записьRÄQ означает поэлементное умножение этих матриц. Тогда сразу видно, что строка x_i, матрицы RÄQ содержит единицы только в тех столбцах x_j, для которых выполняется усло­вие: вершины x_i и x_j взаимно достижимы; в других местах строки x_i стоят нули. Таким образом, две вершины находятся в одной и той же СК тогда и только тогда, когда соответствующие им стро­ки (или столбцы) в матрице RÄQ идентичны. Вершины, кото­рым соответствуют строки, содержащие 1 в столбце x_j, образуют множество вершин СК, содержащей x_j. Отсюда мгновенно сле­дует, что матрицу RÄQ можно преобразовать путем транспони­рования строк и столбцов в блочно-диагональную. Каждая из диа­гональных подматриц этой матрицы соответствует СК графа G и содержит только единичные элементы, все остальные элементы блочно-диагональной матрицы равны нулю. Для приведенного ранее примера матрицаRÄQ, преобразованная соответствую­щим образом, имеет вид