Если неориентированный граф является связанным, то требуется только одно обращение к процедуре поиска в глубину, которая просмотрит рекурсивно все его вершины. Если компонент связанности несколько, то процедура поиска запускается несколько раз для очередной компоненты.
Пусть заполняется массив из n элементов вида comp[1..n], элементы которого указывают номера компонент связности.
num - текущая компонента
for i:=1 to n do begin
mark[i]:=true; comp[i]:=0;
end;
num:=0;
for i:=1 to n do
if mark[i] then
begin
num:=num+1; DFS1(i); write(num);
end;
{сама процедура нахождения компонент связности}
Procedure DFS1(i:integer);
var j:integer;
begin
mark[i]:=false; comp[i]:=num; write(i);
for j L(i) do
if mark[j] then DFS1(j);
end;
|
Главная
Каталог файлов
