Лекция №12.5: Алгоритмы на графах и деревьях

страницы: 1 2 3 4 5 6

Содержание

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

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

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

Считаем, что граф задан матрицей смежности 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, как и прежде, будет хранить номера компонент связностей, к которым принадлежат помеченные вершины графа.

Алгоритм КомпСвяз–Итер

Прочитать начало и конец очередного ребра. Далее возможны 4 различные ситуации:

  1. Оба конца ребра ещё не относятся ни к одной из ранее встретившихся компонент связности (mark[u] = 0 и mark[v] = 0). В этом случае количество компонент связности kol увеличивается на единицу, а новая компонента связности получает очередной номер ks + 1.
  2. Один конец ребра уже относится к какой–то компоненте связности, а второй — ещё нет (mark[u] = 0, а mark[v] ≠ 0). В этом случае общее количество компонент связности kol остаётся прежним, а непомеченный конец ребра получает ту же пометку, что и второй его конец.
  3. Оба конца нового ребра относятся к одной и той же компоненте связности (mark[u] = mark[v] ≠ 0). В этом случае не нужно производить никаких действий.
  4. Концы нового ребра относятся к разным компонентам связности (0 ≠ mark[u] ≠ mark[v] ≠ 0). В этом случае нужно объединить две ранее созданные компоненты связности в одну. Общее количество компонент связности kol уменьшается на 1, а все вершины, принадлежавшие к более новой компоненте связности (больший номер), получают новую пометку. Заметим, что переменная ks, обозначающая очередной свободный номер для следующей компоненты связности, в данном случае изменяться не должна, поскольку нет никакой гарантии, что изменён будет номер именно самой последней компоненты связности.

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

Реализация
kol := 0;
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);

страницы: 1 2 3 4 5 6

Примечания

Код для вставки: :: :: :: ::
Поделиться: // //