Итеративный алгоритм

Реализация

Алгоритм КомпСвяз-Рек

Рекурсивный алгоритм

Подсчет количества компонент связности

Задача. Определить количество компонент связности в заданном графе.

Считаем, что граф задан матрицей смежности sm.

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

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

Рекурсивная процедура обхода в глубину (прямого или обратного обхода) переберет все вершины, достижимые из начальной. Начальной вершиной для очередной компоненты связности может стать любая вершина, еще не отнесенная ни к какой другой компоненте связности (то есть еще не помеченная в массиве mark).

По окончании работы программы переменная kol будет содержать количество найденных компонент связности.

procedure step (v: integer);var j: integer;begin mark[v]:= k; for j:=1 to N do if (mark[j]=0)and(sm[v,j]<>0) then step(j);end; begin... for i:= 1 to N do mark[i]:=0; k:= 0; {номер текущей компоненты связности} for i:= 1 to N do if mark[i]=0 then begin inc(k); step(i); end;...end.

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

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

Дата добавления: 2014-01-03