: index | programowanie | webmastering | algorytmika | download | projekty | słownik | grafika | flash | linki :

a l g o r y t m y > grafy >

A L G O R Y T M   P R I M A

 

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29 30

 
       

Algorytm Prima wyznacza tzw. minimalne drzewo rozpinające. Mając do dyspozycji graf spójny i nieskierowany, tzn. taki w którym dla każdych dwóch wierzchołków grafu istnieje droga pomiędzy nimi oraz krawędzie grafu nie mają ustalonego kierunku, nasuwa się pytanie o podzbiór E' zbioru krawędzi E, dla którego graf nadal pozostaje spójny, ale suma kosztów wszystkich krawędzi zbioru E' ma najmniejszą możliwą wartość.
Grafy zawierające dużo krawędzi, w których dwa te same wierzchołki połączone są np. 5 ścieżkami długości 2, raczej nie są "lubiane" przez algorytmy i często przekształcenie takiego skomplikowanego grafu w graf mu równoważny pod względem zachowania możliwych połączeń przynosi znaczące korzyści.

Wskazaną do algorytmu reprezentacją grafu są listy sąsiedztwa, ponieważ dla każdego węzła przetwarzana jest lista wszystkich jego następników. Drugim wymogiem jest kolejka priorytetowa, do której dodawane będą krawędzie grafu, i z której usuwana będzie krawędź o najmniejszym koszcie - idealną strukturą do implementacji takiej kolejki jest kopiec (odwrócony).

Algorytm Prima buduje minimalne drzewo rozpinające rozpoczynając od dowolnego wierzchołka grafu i stopniowo dodając do niego krawędzie o możliwe najmniejszych kosztach.

  1. Zaznacz wybrany wierzchołek grafu - niech będzie to wierzchołek 1 - jako dołączony do minimalnego drzewa rozpinającego (zrobiony)

  2. Dla wszystkich wierzchołków j incydentnych z wierzchołkiem 1:

    • jeżeli wierzchołek j nie został jeszcze zrobiony, to krawędź prowadzącą do tego wierzchołka dodaj do kopca

  3. Dopóki kopiec nie jest pusty wykonuj następujące czynności:

    • Jeżeli krawędź o najmniejszym koszcie w kopcu prowadzi do wierzchołka jeszcze nie zrobionego, to wykonaj następujące czynności:

      • Dodaj tą krawędź do minimalnego drzewa rozpinającego

      • Zaznacz wierzchołek i, do którego prowadzi krawędź jako zrobiony

      • Usuń z kopca krawędź prowadzącą do wierzchołka i

      • Dla wszystkich wierzchołków j incydentnych z wierzchołkiem i:

        • Jeżeli wierzchołek j nie został jeszcze dołączony do minimalnego drzewa rozpinającego, to dołącz krawędź [i, j] do kopca

    • W przeciwnym wypadku usuń z kopca krawędź o najmniejszym koszcie

 

DANE:
  n - liczba wierzchołków grafu
  a - graf spójny i nieskierowany - tablica wymiaru "n x n" 
      zawierająca listy sąsiedztwa wszystkich wierzchołków
      elementem tablicy jest rekord zawierający dwa pola:
        wezel - numer wierzchołka incydentnego
        koszt - koszt krawędzi
      wszystkie krawędzie grafu powinny mieć nieujemne koszty
  ca - tablica zawierająca stopnie poszczególnych wierzchołków grafu "a"
       ca[i] - ilość wierzchołków incydentnych z wierzchołkiem "i"
  z  - tablica, w której zapisano informację o zrobionych wierzchołkach 
       grafu z[i]=prawda, gdy wierzchołek "i" został już dołączony do 
       minimalnego drzewa rozpinającego
  K  - kopiec krawędzi grafu "a"
  ck - rozmiar kopca K
WYNIK:
  minimalne drzewo rozpinające "b" grafu "a"
Type
  KrawedzGrafu  = Record
                    wezel : Integer;
                    koszt : Integer;
                  End;
  Graf     = Array[1..30, 1..30] Of KrawedzGrafu;
  Stopnie  = Array[1..30] Of Byte;

  WezelKopca = Record
                 odwezla : Integer;
                 dowezla : Integer;
                 koszt   : Integer;
               End;
  Kopiec   = Array[1..900] Of WezelKopca;

Procedure Zamien(Var a, b : WezelKopca);
Var
  tmp : WezelKopca;
Begin
  tmp:=a;
  a:=b;
  b:=tmp;
End;

{ n - rozmiar kopca }
{ k - numer węzła   }
Procedure Przywroc(Var a : Kopiec; n, k : Integer);
Var
  rodzic, potomek : Integer;
Begin
  { Przywróć strukturę ku górze, do korzenia }
  potomek:=k;
  rodzic:=potomek Div 2;
  While (rodzic>0) And (a[rodzic].koszt>a[potomek].koszt) Do
    Begin
      Zamien(a[rodzic], a[potomek]);
      potomek:=rodzic;
      rodzic:=potomek Div 2;
    End;
  { Przywróć strukturę ku dołowi, od korzenia }
  rodzic:=k;
  potomek:=2*rodzic;
  While potomek<=n Do
    Begin
      If (potomek<n) And (a[potomek].koszt>a[potomek+1].koszt) 
       Then Inc(potomek);
      If a[potomek].koszt<a[rodzic].koszt Then
        Begin
          Zamien(a[rodzic], a[potomek]);
          rodzic:=potomek;
          potomek:=2*rodzic;
        End
      Else Break;
    End;
End;

{ Dodaj do kopca krawędź grafu }
{ n - rozmiar kopca            }
Procedure DoKopca(Var a : Kopiec; Var n : Integer; odwezla,
                  dowezla, koszt : Integer);
Begin
  Inc(n);
  a[n].odwezla:=odwezla;
  a[n].dowezla:=dowezla;
  a[n].koszt:=koszt;
  Przywroc(a, n, n);
End;

{ Usuń z kopca jego korzeń }
Procedure ZKopca(Var a : Kopiec; Var n : Integer);
Begin
  Zamien(a[1], a[n]);
  Dec(n);
  Przywroc(a, n, 1);
End;

Procedure DodajKrawedz(Var a : Graf; Var c : Stopnie; odwezla,
                            dowezla, koszt : Integer);
Begin
  c[odwezla]:=c[odwezla]+1;
  a[odwezla, c[odwezla]].wezel:=dowezla;
  a[odwezla, c[odwezla]].koszt:=koszt;
  c[dowezla]:=c[dowezla]+1;
  a[dowezla, c[dowezla]].wezel:=odwezla;
  a[dowezla, c[dowezla]].koszt:=koszt;
End;

Var
  n, i, j : Integer;
  a, b    : Graf;
  ca, cb  : Stopnie;
  z       : Array[1..30] Of Boolean;
  K       : Kopiec;
  ck      : Integer;
Begin
  n:=6;
  For i:=1 To n Do
    Begin
      ca[i]:=0;
      cb[i]:=0;
    End;
  DodajKrawedz(a, ca, 1, 2, 13);
  DodajKrawedz(a, ca, 1, 3, 2);
  DodajKrawedz(a, ca, 1, 4, 6);
  DodajKrawedz(a, ca, 2, 4, 5);
  DodajKrawedz(a, ca, 2, 5, 1);
  DodajKrawedz(a, ca, 2, 6, 5);
  DodajKrawedz(a, ca, 3, 4, 3);
  DodajKrawedz(a, ca, 3, 5, 15);
  DodajKrawedz(a, ca, 4, 5, 10);
  DodajKrawedz(a, ca, 5, 6, 2);

  ck:=0;
  For i:=1 To n Do z[i]:=False;

  { Algorytm Prima }
  z[1]:=True;
  For i:=1 To ca[1] Do
    If Not z[a[1, i].wezel] Then
      DoKopca(K, ck, 1, a[1, i].wezel, a[1, i].koszt);

  While ck>0 Do
    Begin
      If Not z[K[1].dowezla] Then
        Begin
          i:=k[1].dowezla;
          DodajKrawedz(b, cb, K[1].odwezla, K[1].dowezla,
                       K[1].koszt);
          ZKopca(K, ck);
          z[i]:=True;
          For j:=1 To ca[i] Do
            If Not z[a[i, j].wezel] Then
              DoKopca(k, ck, i, a[i, j].wezel, a[i, j].koszt);
        End
      Else ZKopca(K, ck);
    End;

  WriteLn('Minimalne drzewo rozpinajace :');
  For i:=1 To n Do
    For j:=1 To cb[i] Do
      If i<=b[i, j].wezel Then
        Writeln(i, ' -> ', b[i, j].wezel, ' - ', b[i, j].koszt);
  ReadLn;
End.
Minimalne drzewo rozpinajace :
1 -> 3 - 2
2 -> 4 - 5
2 -> 5 - 1
3 -> 4 - 3
5 -> 6 - 2

Złożoność obliczeniowa: O(n*log(n)).