Algoritmul lui Kruskal

     Algoritmul liu Kruskal a fost pentru prima data publicat in anul 1956 si poate fi implementat in mai multe moduri. In continuare voi prezenta o metoda care utilizeaza structura de date multime si submultime, pe care sunt definiti operatorii Uniune si Cauta.
     Inainte de a scrie implementarea algoritmului am decis ca ar fi mai bine sa fac o scurta prezentarea a acestuia.
     Fie graful conex G=(N,A) cu N={1,2,3,...,n} si cu functia de cost C definita pe multimea arcelor A. O alta metoda de constructie a unui arbore de acoperire minim, numita algoritmul lui Kruskal, porneste de la un graf T=(N,U) care consta doar din cele n noduri ale grafului G, dar nu are nici un arc.

     In aceasta situatie fiecare nod este de fapt o componenta conexa a grafului care consta consta chiar din nodul respectiv. In continuare pornind de la multimea curenta a componentelor conexe, algoritmul selecteaza pe rand cate un arc de cost minim pe care il adauga componentelor conexe care cresc in dimensiune dar al caror numar se reduce. In final rezulta o singura componenta conexa care este chiar arborele de acoperire minim.

     Pentru a construi componente din ce in ce mai mari se examineaza arcele din multimea A in ordine crescatoare a costului lor. Daca arcul selectat conecteaza doua noduri apartinand unor componente conexe distincte, arcul respectiv este adaugat grafului T. Daca arcul selectat conecteaza doua noduri apartinand unei aceleasi componente conexe, arcul este neglijat intrucat introducerea sa ar conduce la aparitia unui ciclu in respectiva componenta si in final la un ciclu in arborele de acoperire, lucru nepermis de definitie. Aplicand in maniera repetitiva acest procedeu, la momentul la care toate nodurile grafului apartin unei singure componente conexe, algoritmul se termina si T reprezinta arborele de acoperire minim al grafului G.

     Cu alte cuvinte algortimul lui Kruskal porneste de la o padure de n arbori. In fiecare din cei n-1 pasi, algoritmul combina doi arbori intr-unul singur, utilizand ca legatura arcul cu costul cel mai redus curent. Procedeul continua pana in momentul in care ramane un singur arbore. Acesta este arborele de acoperire minim. Spre exemplu consideram graful ponderat din figura de mai jos. In succesiunea (1)-(5) din cadrul aceleiasi figuri se prezinta maniera de determinare a unui arbore de acoperire minim al grafului in baza acestui algoritm.

     Ordinea in care se adauga arcele rezulta din figura. Initial se adauga arcele cu costurile 1,2,3 si 4, toate acceptate, intrucat nici unul dintre ele nu genereaza un ciclu. Arcele (1,4) si (3,4) de cost 5 nu pot fi acceptate deoarece conecteaza noduri apartinand aceleiasi componente si conduc la cicluri. In consecinta se accepta arcul (2,3) de cost 5 care nu produce nici un ciclu incheind astfel constructia arborelui de acoperire minim.

     Implementare:

Procedure Kruskal (N: set of Noduri; A: set of Arce; 

                   Var t: set of arce); 

Var ncomp:integer; {numarul curent de componente}

    CPArce: CoadaBazataPePrioritate; {pastreaza arcele in vederea                                          selectiei arcului mimim}

    componente: MS; {multime de submultimi pe care sunt definit                          operatorii Uniune si Cauta}

    x,y: Noduri;

    a: Arce;

    compUrm: integer; {numarul noii componenre}

    xComp,YComp:integer; {nume de componente}

Begin

  MultimeVida(T); {face multimea T vida}

  Initealizeaza(CPArce); {initializeaza coada bazata pe prioritate                             pe coada vida}

  compUrm:=0;

  nComp:=(numarul de membrii a lui N);

  For x In n Do    {initealizeaza multimea de submultimi astfel                         incat fiecare componenta a sa contina un singur                     nod din N}

   Begin

    compUrm:compUrm +1;

    Initealizeaza (compUrm,x,componente);

   End;

  For a In A Do {initealizeaza coada de prioritati a arcelor}

    Insereaza(a,CPArce);

  While (nComp>1) And (Not Vid (CPArce)) Do

    Begin                 {cerceteaza arcul urmator}

      a:=Extrage(CPArce); {se presupune ca a=(x,y)}

      xComp:=Cauta(x,componente);

      yComp:=Cauta(y,componente);

      If xComp<>yComp Then

        Begin {a conecteaza doua componente diferite}

          Uniune(xComp,yComp,componente);

          nComp:=nComp-1;

          Insereaza(a,T);

        End; {If}

     End; {While}

End; {Kruskal}

     Referitor la aceasta implementare fac urmatoarele precizari:

a)Uniune(A:componenta, B:componenta, C:multime_de_submultimi); -reuneste componentele A si B ale multimii de submultimi C.

b)Cauta(x:nod,C:multime_de_submultimi):componenta; - returneaza mumele acelei componente a lui C al carei membru este nodul x. Operatia va fi utilizata pentru a stabili daca cele doua noduri care determina un arc apartin aceleiasi componente conexe sau nu.

c)Initializeaza(A:componenta,x:nod,C:multime_de_submultimi) -craza componenta cu numele A a multimii de submultimi C. Componenta A va contine numai nodul x.

d)Insereaza(a:TipArc, T:set of Arce); -construieste multimea T.