ARBORE PARTIAL DE COST MINIM

Se da un graf G=(X, U). Fiecare muchie a sa are atasat un numar real pozitiv reprezentand costul muchiei. Sa se determine un arbore partial de cost minim.

Def: Suma costurilor unui graf se numeste costul grafului

Daca c : U ® R₊  functia costul grafului    atunci suma costurilor muchiilor care compun arborele determina costul arborelui.

Graful se va citi c o succesiune de muchii (doua varfuri) impreuna cu costul fiecarei muchii. Numarul de muchii este m.

Se va ordona sirul muchiilor in ordine crescatoare dupa costul muchiilor.

Se considera un graf format numai din cele n noduri fara nici o muchie

Se vor adauga muchii la acest graf daca muchia respectiva nu va crea un ciclu pana cand graful devine conex (numarul de componente conexe este 1).

Se vor lua muchiile in ordinea crescatoare a costurilor si se va stabili apartenenta celor doua varfuri la o componenta conexa. Astfel avem 3 cazuri:

1. Daca varfurile nu apartin de nici o componenta conexa atunci se va crea una noua care sa contina cele doua varfuri, costul componentei va fi costul muchiei.
2. Daca unul din varfuri apartine de o componenta conexa atunci se va introduce si celalalt iar costul componentei va creste cu costul muchiei, sau ambele varfuri apartin de o componenta conexa, atunci nu se va face nimic.
3. Daca unul din varfuri apartine la o componenta conexa si celalalt la o alta componenta conexa atunci cele doua componente conexe se vor uni si va contine toate varfurile de la cele doua si numarul de componente conexe va scade cu 1 iar costul noi componente este suma costurilor celor doua la care se aduna costul muchiei.

Se vor introduce muchii pana in prima componenta conexa avem n noduri.

Algoritmul de determinare a unui arbore partial de cost minim.

Muchiile au fost ordonate dupa cost [much[I].x, much[I].y, much[I].cost]

Pentru I = 1 la m si NrElemente(CompCon[1] != n)   executa

k=0;

Pentru j = 1 la nc executa

Daca ((much[I].x apartine CompCon[j]) sau (much[I].y apartine CompCon[j]))          atunci        

                k = k+1;           u[k] = j;

 SfDaca

 SfPentru

  Daca (k =0) atunci    nc = nc + 1;   CostArb[nc] = much[I].cost;   

                    &nb sp;                CompCon[nc] = {much[I].x, much[I].y} Ales[I] = 1; // s-a ales muchia i

      Altfel   

             Daca (k=1) atunci (Daca nu apartin amandoua de aceeasi comp coexa)

                    &nb sp;    CompCon[u[1]] = CompCon[u[1]] U {x[I], y[I]}

                 CostArb[u[1]] = CostArb[u[1]] + much[I].cost;    Ales[I] = 1;

                    &nb sp; Altfel

                 CompCon[u[1]] = CompCon[u[1]] U CompCon[u[2]];

                        &n bsp;  CostArb[u[1]] = CostArb[u[1]] + CostArb[u[2]] + much[I].cost;  

                    &nb sp;       Ales[I] = 1;      nc = nc –1;

                     SfDaca

    SfDaca

SfPentru

                        m – numarul de muchii

much – vectorul muchiilor are trei componente { x, y, cost}

x – prima extremitate a muchiei

y -  a doua extremitate a muchiei

cost – costul muchiei

nc – numarul de componente conexe

NrElemente – intoarece numarul de element al unui vector

CompCon[j] – vector ce memoreaza varfurice ce fac parte din componenta conexa j.

u[k] – memoreaza numarul componentei conexe din care fac parte cele doua varfuri

k – ne spune in ce situatie ne aflam (1, 2, sau 3)

CostArb – vector ce reprezinta costul componentelor

Ales[I] – vector ce arata ca muchia I a fost aleasa sa faca parte din arbore