Нахождение компонент связности графа

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

Очевидно, что =1 тогда и только тогда, когда (i, j) –ый элемент матрицы

не равен 0, где - матрица смежности графа , |V|=p.

Если граф у нас неориентированный то матрица достижимости будет у нас одновременно и матрицей связности.

Пример

1 2 5 6

3 4 7

Матрица достижимости

В компоненту связности вершины будут входить все вершины, для которых =1.

. Первая компонента связности {1, 2, 3, 4}.

. Вторая компонента связности {5, 6, 7}.

Если граф у нас ориентированный, то мы должны построить матрицу котрдостижимости.

Рассмотрим матрицу S=C Q, где операция обозначает поэлементное произведение матриц C и Q, . Элемент матрицы S тогда и только тогда, когда и вершина взаимнодостижимы. Используя матрицу S, мы можем найти бикомпоненты орграфа.

В бикомпоненту связности вершины будут входить все вершины, для которых =1.

Пример

1 2 3

5 4

Возьмем вершину 2 и по матрице S получаем . Следовательно, бикомпонента, которую входит вершина 2 состоит из вершин {1, 2, 3}. Другие две бикомтоненты состоят из вершин {4} и {5}.

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

Найти компоненты связности графа можно, естественно, и алгоритмическим путем.

Рассмотрим рекурсивный алгоритм выделения компонент связности неориентированного графа, а также их числа.

В основу алгоритма положена техника поиска в глубину. Задача состоит в построении массива меток вершин графа, назовем его у. Вершине графа v присваивается номер ой компоненты, которой она принадлежит, count – счетчик числа компонент.

Вход: граф G, заданный списками смежностей: Г(v).

Выход: массив меток у, счетчик числа компонент count.

For v V do

y(v): =0

count: =0

for v V do

if y(v)=0 then

begin

count: =count+1

component (v, count)

end

procedure component (v, count)

y(v): =count

for w Г(v) do

if y(w)=0 then

component (w, count)

Пример

1 2 5 6

3 4 7

Результат работы алгоритма: