Как определить связен ли граф?

← →
Derww (2006-12-30 12:09) [0]

Оцените, пожалуйста, мой вариант, основанный на поиске в глубину:

/////////////////////////////////////////////////////////////////////////////////
type int=longint;

Procedure solve(v: int);
var j: int;
begin
use[v]:=true;
for j:=1 to n do
if not use[j] and (a[v,j]<>0) then
begin
a[v,j]:=0;
solve(j);
end;
end;

begin
count:=0;
FillChar(use,sizeof(use),false);
for i:=1 to n do if not use[i] then
begin
inc(count);
solve(i);
end;
if count=1 then writeln("Связный") else writeln("Не связный");
end.
/////////////////////////////////////////////////////////////////////////////////

Пожалуйста, подскажите правильный ли алгоритм я использую!
Заранее благодарен!

← →
TUser © (2006-12-30 14:23) [1]

> FillChar(use,sizeof(use),false);

var use: packed array ...

FillChar(@use[0],length(use)*sizeof(use[0]),false);

В остальном, все вроде праильно. Только я обычно пишу совсем не так, но это дело вкуса. В частности, считать число связных компонент совсем не обязательно - можно останавливать алгоритм после того, как count стал больше 1. Поэтому вместо count можно ввести булевую переменную. Мой пример

procedure Proceed (I: integer);
vart j: integer;
begin
use[i] := true;
for j := 0 to high (use) do
if i <> j then
if a[i, j] <> 0 then
if not use[j] then
proceed (j);
end;

begin
if length (use) = 0 then
writeln ("Empty graph");
exit;

proceed (0);
for i := 1 to high(use) do
if not use [i] then
writeln ("Несвязный")
exit;
writeln ("свзный");
end.

Как определить связен ли граф? Найти похожие ветки