witam
Otrzymałem prosty program implementujący algorytm Kruskala wyznaczy minimalne drzewo rozpinające dla grafu nieskierowanego ważonego.
Poproszono mnie o jego poprawieni a dokładnie samej procedury implementującej algorytm.
Jednak nie jest to moje pole i szczerze powiedziawszy nie bardzo rozumie ten algorytm.
Problem brzmi następująco:
Zbyt duża złożoność operacji przy łączeniu drzew... (tak mi powiedziano)
Jeżeli, więc ktoś wie o co chodzi i wie jak rozwiązać ten problem to bardzo proszę o pomoc. Gdyby była taka możliwość to prosiłbym o dodanie komentarzy do kodu tak aby można było zrozumieć działanie algorytmu. Z góry dziękuję... poniżej zamieszczam kod procedury i opis zmiennych globalnych.
Część nagłówkowa:
Const
MaxIloscWezlow = 100;
MaxIloscKrawedzi = 1000;
Type
KrawedzGrafu = Record
odwezla, dowezla : Integer;
koszt : Integer;
End;
Graf = Array[1..MaxIloscKrawedzi] Of KrawedzGrafu;
TGraf = Class
Public
G, T : Graf;
gk, tk, n : Integer; //gk - liczba krawedzi; n - liczba wierzcholow; tk -krawędzie w drzewie
procedure WczytajZPliku;
procedure WczytajZKonsoli;
procedure SortujKrawedzie;
procedure SortujKrawedziePrzezKopcowanie;
procedure AlgKruskala;
procedure WyswietlWynik;
End;
Metoda impl. algorytm:
Procedure TGraf.AlgKruskala;
Var
Z : Array[1..MaxIloscWezlow] Of Integer;
i, j, k, u, v, w : Integer;
Begin
For i:=1 To n Do Z[i]:=0;
tk:=0;
k:=1;
j:=1;
While k<n Do
Begin
u:=G[j].odwezla;
v:=G[j].dowezla;
j:=j+1;
If (Z[u]=0) Or (Z[v]=0) Or (Z[u]<>Z[v]) Then
Begin
tk:=tk+1;
T[tk]:=G[j-1];
If (Z[u]=0) And (Z[v]<>0) Then
Begin
w:=u;
u:=v;
v:=w;
End;
If Z[u]=0 Then Z[u]:=u;
If Z[v]=0 Then Z[v]:=Z[u]
Else
Begin
w:=Z[v];
For i:=1 To n Do
If Z[i]=w Then Z[i]:=Z[u];
End;
k:=k+1;
End;
End;
End;