Правила форума
Лекция №12.5: Алгоритмы на графах и деревьяхСодержание
Подсчёт количества компонент связности
Задача. Определить количество компонент связности в заданном графе.
Рекурсивный алгоритм
Считаем, что граф задан матрицей смежности sm.
Каждый элемент специального линейного массива mark будет хранить номер компоненты связности, к которой принадлежит соответствующая вершина графа.
Алгоритм КомпСвяз–Рек
- Совершить обход в глубину всех компонент связности графа, помечая вершины каждой из них отдельным номером.
Рекурсивная процедура обхода в глубину (прямого или обратного обхода) переберёт все вершины, достижимые из начальной. Начальной вершиной для очередной компоненты связности может стать любая вершина, ещё не отнесённая ни к какой другой компоненте связности (то есть, ещё не помеченная в массиве mark).
По окончании работы программы переменная kol будет содержать количество найденных компонент связности.
Реализация
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, как и прежде, будет хранить номера компонент связностей, к которым принадлежат помеченные вершины графа.
Алгоритм КомпСвяз–Итер
Прочитать начало и конец очередного ребра. Далее возможны 4 различные ситуации:
- Оба конца ребра ещё не относятся ни к одной из ранее встретившихся компонент связности (mark[u] = 0 и mark[v] = 0). В этом случае количество компонент связности kol увеличивается на единицу, а новая компонента связности получает очередной номер ks + 1.
- Один конец ребра уже относится к какой–то компоненте связности, а второй — ещё нет (mark[u] = 0, а mark[v] ≠ 0). В этом случае общее количество компонент связности kol остаётся прежним, а непомеченный конец ребра получает ту же пометку, что и второй его конец.
- Оба конца нового ребра относятся к одной и той же компоненте связности (mark[u] = mark[v] ≠ 0). В этом случае не нужно производить никаких действий.
- Концы нового ребра относятся к разным компонентам связности (0 ≠ mark[u] ≠ mark[v] ≠ 0). В этом случае нужно объединить две ранее созданные компоненты связности в одну. Общее количество компонент связности kol уменьшается на 1, а все вершины, принадлежавшие к более новой компоненте связности (больший номер), получают новую пометку. Заметим, что переменная ks, обозначающая очередной свободный номер для следующей компоненты связности, в данном случае изменяться не должна, поскольку нет никакой гарантии, что изменён будет номер именно самой последней компоненты связности.
По окончании работы этого алгоритма в массиве mark будет записано S различных целых чисел, каждое из которых будет означать отдельную компоненту связности. Кроме того, в массиве могут остаться нулевые компоненты: каждая из них будет соответствовать изолированной вершине, которая тоже является отдельной компонентой связности. Следовательно, количество нулей должно быть прибавлено к количеству компонент, найденному в процессе работы основного алгоритма.
Реализация
ks := 0;
while not Eof(f) do
begin
ReadLn(f, u, v);
if mark[u] = 0 then
if mark[v] = 0 then
begin {случай 1}
Inc(kol);
Inc(ks);
mark[u] := ks;
mark[v] := ks;
end
else
mark[u] := mark[v] {случай 2}
else if mark[v] = 0 then
mark[v] := mark[u] {случай 2 — симметричный}
else if mark[u] <> mark[v] then {случай 4}
begin
max := v;
min := u;
if u > v then
begin
max := u;
min := v
end;
for i := 1 to n do
if mark[i] = max then
mark[i] := min;
Dec(kol);
end
end;
for i := 1 to N do
if mark[i] = 0 then
Inc(kol);
::
::
::
