Скачать: CL | DM;

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

← →
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.

---

Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.45 MB
Время: 0.026 c