Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Ада и другие языки _ к- связность графа

Автор: xel 5.06.2007 1:54

вообщем.. есть алгоритм с куском реализации.. я 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 5.06.2007 2:16


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 пробегая по всем вершинам считает число компонент сязности...

Автор: volvo 5.06.2007 2:20

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