Pascal-procedura sprawdzania grafów spójnych. POMOCY!

0

Witam. Mam problem z napisaniem procedury sprawdzania ile jest grafów spójnych w próbce rep wygenerowanych grafów na n wierzchołkach w zależności od wartości k.(należy przyjąć własne wartości pod n,k,rep) Nie wiem jak sie do tego zabrać. Procedurę generowania grafu G=G(n,k) już mam, kod podaje niżej. Proszę o pomoc. Jest to dla mnie bardzo ważne!

const nmax=100;
kmax=nmax*(nmax-1) div 2;
type ind1=1..kmax;
r=record a,b:integer end;
t1=array[ind1] of r; { E }
procedure init(n:integer; var E:t1; var total:integer);
var i,j,h:integer;
begin
h:=0;
for i:=1 to n - 1 do
for j:=i + 1 to n do
begin
h:=h + 1;
with E[h] do begin a:=i; b:=j end;
end;
total:=h;
end; { init }

procedure Gnk(n,k,total:integer; var E:t1);
var i,h,z:integer; x:r;
begin
h:=total;
for i:=1 to k do
begin
z:=random(h) + 1;
x:=E[z];
E[z]:=E[h];
E[h]:=x;
h:=h-1;
end;
end; { Gnk }

0

A) kolorowanie składni
B) idziesz w pętli po wierzchołkach, gdy wierzchołek jest wolny (wartość 0) to ustawiasz mu 1 i robisz na nim BFS, że ustawia wszystkim wierzchołkom z BFS-a wartość 1. Potem idziesz dalej aż trafisz na kolejny wierzchołek wtedy zwiększasz licznik o jeden (czyli na dwa) i na nim robisz BFS tylko teraz wierzchołki dostają wartość 2, i znowu idziesz w pętli itd. I to jaką wartość ma licznik na końcu to liczba spójnych części i dodatkowo już wiesz czy wierzchołki są w tej samej spójnej części czy nie

0

Mam coś takiego ale nie chce dzialac:/ Potrzebna NATYCHMIASTOWA RADA!

program p5(input,output); { KTB Oct 28, 1996 }
uses dos;
const nmax=100; kmax=nmax*(nmax-1) div 2;
type ind=1..nmax; ind1=1..kmax;
elem=1..nmax;
zbior=set of elem;
r=record a,b:integer; code:Boolean; end;
rs=record w:zbior; l:integer; end;
t=array[ind] of integer;
t1=array[ind1] of r; { E }
t2=array[ind,ind] of Boolean; { A }
ts=array[ind] of rs; { S }
t3=array[ind] of Boolean; { x }
alfa=string[15];

var E:t1; A:t2; S:ts; n,rep,i,k,total,c:integer; p:real;
key:integer; wariant:integer; czas1, czas2:extended;
out:text; dev:alfa;

procedure czyt1(var n,k,rep:integer);
begin
write('n, k, rep ='); read(n, k, rep);
end; { czyt1 }

procedure czyt2(var n,k,rep:integer);
begin
write('n, k, rep ='); read(n, k, rep);
end; { czyt2 }

procedure init(n:integer; var E:t1; var total:integer);
var i,j,h:integer;
begin
h:=0;
for i:=1 to n - 1 do
for j:=i + 1 to n do
begin
h:=h + 1;
with E[h] do begin a:=i; b:=j end;
end;
total:=h;
end; { init }

procedure Gnk(n,k,total:integer; var E:t1);
var i,l,z:integer; x:r;
begin
l:=total;
for i:=1 to k do
begin
z:=random(l) + 1;
x:=E[z];
E[z]:=E[l];
E[l]:=x;
l:=l-1;
end;
end; { Gnk }

procedure druk1a(n,k,rep:integer);
begin
writeln(out);
writeln(out, 'Gnk, n =', n:3, ', k =', k:4, ', rep =', rep:5);
end; { druk1a }

procedure drukE(n,total:integer; var E:t1);
var i,h,l:integer;
begin
write(out, 'Edges from E:');
h:=0;
for l:=total downto total - k + 1 do
with E[l] do
begin
h:=h + 1; write(out, a:4, b:3);
if h mod 10 = 0 then writeln(out)
end;
writeln(out);
end; { drukE }

procedure DFS(n,v:integer; var A:t2; var x:t3);
var j:integer;
begin
for j:=1 to n do
if A[v,j] and not x[j] then
begin
x[j]:=true;
DFS(n, j, A, x)
end;
end; { DFS }

function spojny2(n:integer; var A:t2):Boolean;
var i:integer; var x:t3; b:Boolean;
begin
for i:=1 to n do x[i]:=false;
x[1]:=true;
DFS(n, 1, A, x);
b:=true;
i:=1; while (i <= n) and b do begin b:=x[i]; i:=i + 1 end;
spojny2:=b;
end; { spojny2 }

function pomiar:extended;
var h,m,s,s100:word;
begin
gettime(h, m, s, s100);
pomiar := h * 3600 + m * 60 + s + (s100 / 100);
end; { pomiar }

begin
write('output file:'); readln(dev);
assign(out, dev); rewrite(out);
randomize;
repeat
writeln('wariant: (1/2/3/4/5)'); readln(wariant);
case wariant of
1: begin { Gnp w E, transES }

   end; { 1 }

2: begin  { Gnp w A, transAS }

   end; { 2 }

3: begin { Gnk }
     czyt1(n, k, rep);
     druk1a(n, k, rep);
     init(n, E, total);
     for i:=1 to rep do
       begin
         Gnk(n, k, total, E);
         drukE(n, total, E);
       end;
     czyt2(n,k,rep);
     czas1:=pomiar;
     c:=0;
     for i:=1 to rep do
       begin
         Gnk(n,k,total,E);
         if spojny2(n, ) then c:=c +1;
       end;
     writeln(out);
     writeln(out, 'liczba grafow spojnych w probce, c =', c:3);
     czas2 := pomiar;
     writeln('czas:',(czas2-czas1):6:2,' [s]');
   end; { 3 }


4: begin { czas Gnp + spojnosc }
     
  end; { 4 }

5: begin { czas Gnp }

  end; { 5 }

 end; { case }
writeln('end? 0/1'); readln(key);

until key=1;
close(out)
end.

0

Matko święta, na górze okienka przy dodawaniu postów jest opcja kolorowania składni. Chcesz pomocy, ale jakoś nie pomagasz w tym aby Ci pomóc. Przeanalizuj kod, idea tam jest dobra, choć niezły bałagan jest. Pewnie Ci się nawet nie kompiluje, to mógłbyś chociaż zobaczyć czemu. Sama idea zliczenia spójnych składowych jest prosta to może wpiera napisz tutaj jaka jest aby chociaż było widać, że rozumiesz ją

0

Program się kompiluje, ale nie wiem czemu mi nie chce sprawdzic ile jest grafów spójnych :/ Kurde potrzebuje to na zalicznie na za 1,5h a jestem w tym zielony:(

0

acha, i pewnie zadali Ci dzisiaj ten program? Ręce opadają z klawiatury. Podałem Ci sposób działania, masz jakiś kod, który wygląda, że jest na temat to zrób coś z tym

0

nie dam rady :/
nic nie moge zrobic. Od 2 tygodni dopiero programuje w pascalu, a oni mi zadaja takie zadanie jak ja nic nie czaje prawie :(

1 użytkowników online, w tym zalogowanych: 0, gości: 1