к- связность графа Опции

[xel]

вообщем.. есть алгоритм с куском реализации.. я 42 часа искал этот алгоритм(двое суток без сна..) ..

ПЛИЗ... ПОМАГИТЕ ИЗ АЛГОРИТМА СЛЕПИТЬ ПРОГУ... на вас последняя надежда..плиззз...

вот все данные:

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

[Fanat]

Program Graffi;
Uses Crt;
Const Max=80;                        {Obyavlenie peremennix}
Type
 massiv=array[1..Max] of integer;
 matrica=array[1..Max,1..Max] of integer;
Var
 s,i,j,v,nu,p,k,g:integer;
 a,b:massiv;
 m:matrica;
 F:text;
 num:string[2];
Procedure gr (v:integer);     {Rekyrsivnaya procedura}
 Var
   j: integer;
 Begin
   b[v]:= k;
   for j:=1 to g do
      if ((b[j]=0) and (m[v,j]<>0))
	 then gr(j);
 End;

BEGIN             {Nachalo glavnoi programmi}
Clrscr;           {Ochistka ekrana}
writeln('Vvedite nomer testa');
readln(num);
clrscr;
Textcolor(26);    {Menyaem cvet texta}
Writeln('===========Poisk ciklomaticheskogo chisla grafa v FO-predstavlenii===========');
Textcolor(7);
Assign(F,'graf'+num+'.txt');    {Inicializaciya faila}
Reset(F);                           {Otkriie faila dla schitivania}
i:=0;
g:=0;
While Not(Eoln(F)) Do               {Poka ne konec faila}
  Begin
   i:=i+1;
   Read(F,A[i]);             {Chitaem elementi faila v massiv}
   g:=g+1;                   {Podschitivaem kol-vo elementov v massive}
  End;
v:=A[1];                     {Zapisivaem v v 1ii element massiva}
Writeln;
Writeln('Chislo vershin v grafe (p) : ',v);
Writeln;

For i:=1 to v do             {Obnylaem matricy}
 For j:=1 to v do
  M[i,j]:=0;

Writeln('FO-predstavlenie:');
For i:=1 to g do                {Vivodim na ekran massiv}
  Write(' ',A[i]);
Writeln;
Writeln;

s:=round((g-1-v)/2);        {Podschet kol-va reber grafa}
Writeln('Chislo reber v grafe (q) : ',s);
Writeln;

Writeln('Matrica smegnosti vershin grafa: ');
Writeln;
p:=1;
For i:=2 to g Do             {Cikl ot 2 do konca massiva}
 Begin
  If A[i]<>0 Then            {Esli element massiva ne raven 0,    }
		Begin
		 j:=A[i];    {j prisvaevaem znachenie etogo elementa,  }
		 M[p,j]:=1;  {a matrice s indeksami p i j zapisivaem 1}
		End
	     Else p:=p+1;    {inache perexodim na sledyushyu stroky}
 End;

For i:=1 to v Do
 Begin                        {Vivod matrici smegnosti}
  For j:=1 to v Do
   Write('  ', M[i,j]);
   Writeln;
 End;

For i:= 1 to g Do             {Obnylaem vspomogatelnii massiv}
 b[i]:=0;

k:= 0;
For i:= 1 to v Do              {Cikl ot 1 do v (kol-vo vershin)}
  If b[i]=0 Then               {Esli element iz massiva = 0, to}
	      Begin
	       k:=k+1;         {Yvelichivaem k na 1 }
	       gr(i);          {i obrashaemsa k procedure}
	      End;

Writeln;                       {Vivod rezyltatov na ekran}
Writeln('Chislo komponent svyaznosti ® : ',k);
nu:=s-v+k;
Writeln;
Textcolor(2);
Writeln('Iskomoe ciklomaticheskoe chislo = q - p + r = ',nu);
Readln;
END.

Вот что есть...программа считает цикломатическое число...процедура gr пробегая по всем вершинам считает число компонент сязности...

Сообщение отредактировано: Fanat - 4.06.2007 22:19

[volvo]

Это другой язык? Интересно, от какого он отличается?