Determinarea arborelui de acoperire minim al unui graf ponderat. Algoritmul de cautare cu prioritate

1. Scopul lucrarii este prezentarea modului de determinare a arborelui de acoperire minim pentru grafuri ponderate folosind tehnica cautarii bazata pe prioritate, impreuna cu un exemplu pentru implementarea grafurilor cu liste.

2. Aspecte teoretice.

Pentru exemplele din aceasta lucrare, vom folosi graful din figura 10.1.

Tehnica cautarii bazata pe prioritate folosita pentru determinarea arborelui de acoperire minim este ca principiu identica cu algoritmul lui Prim, diferentele constand doar in modul de implementare. Principiul este: alegem nodul radacina, apoi, pana la adaugarea in arbore a tuturor nodurilor, la fiecare pas alegem nodul legat prin cea mai "ieftina" muchie de unul dintre nodurile alese deja.

Nodurile nealese care sunt legate direct de cel putin un nod dintre cele alese formeaza asa-numita "vecinatate". Nodul ales la fiecare pas, apartine, asadar, vecinatatii. El va fi cel cu prioritatea maxima. In acest caz, "prioritatea maxima" o are nodul care conduce la arcul cu ponderea minima.

Metoda utilizeaza o coada bazata pe prioritate in cadrul careia sunt introduse, pe rand, toate nodurile din clasa "vecinatate", in functie de prioritatea acestora (cost mic, prioritate mare). Rand pe rand, aceste noduri sunt extrase din coada cu prioritate (avand in vedere ca nodul cu prioritate maxima, deci cost minim, va fi intotdeauna primul). La extragerea unui nod, x, acesta va fi marcat (inclus in arborele de acoperire minim), apoi, pentru fiecare nod adiacent lui x si neales, y, se incearca introducerea acestuia in coada cu prioritate cu prioritatea p egala cu ponderea arcului (x, y). In coada cu prioritate, nodurile sunt intotdeauna ordonate in functie de prioritatea lor. La incercarea de a introduce pe y cu prioritatea p in coada, avem cazurile:

- daca y se afla deja in coada

- cu o prioritate mai mare sau egala cu p (cost mai mic pentru ajunge la el de la nodurile deja alese), nu-l mai introducem

- cu o prioritate mai mica decat p, atunci il vom muta in coada pe pozitia corespunzatoare noii ponderi p

- daca y nu se afla in coada, il vom introduce cu ponderea p.

La introducerea lui y in coada, se stie ca pana la acel moment, x va fi parintele lui y in arbore.

In figura 10.2 sunt prezentati pasi in constructia arborelui de acoperire minim folosind coada cu prioritate, pornind de la nodul 1 (initial coada contine doar nodul 1). Primul pas consta in extragerea lui 1 si actualizarea cozii in consecinta. Pentru fiecare nod din coada sunt date in paranteza prioritatea, respectiv cheia parintelui lui la pasul respectiv. Nodurile deja incluse in arbore sunt marcate cu *. Dintre arcele ce leaga nodurile alese cu vecinatatea, sunt reprezentate (cu linie intrerupta) doar arcele cu cost minim. Nici arcele nealese care leaga noduri alese nu mai sunt reprezentate.

Referat: Contabilitatea tertilor Referat: Structurarea elementelor de activ si pasiv dupa criterii financiare

Astfel, pentru graful din figura 10.1, aplicarea algoritmului conduce la arborele de acoperire minim format din arcele: (1, 3), (3, 4), (4, 6), (6, 7), (6, 5) si (1,2).

Observatie. Modul de stabilire a prioritatii determina rezultatul algoritmului. Astfel, alegand in alte moduri prioritatea, se obtin alti algoritmi.

Daca nodurile de introdus au intotdeauna prioritatea cea mai mare fata de toate care sunt deja in coada, se obtine traversarea in adancime, iar daca au intotdeauna prioritatea cea mai mica, se obtine traversarea prin cuprindere. Pentru o prioritate egala cu costul drumului de la origine prin nodul nou ales, se obtine algoritmul lui Dijkstra (determinarea drumurilor minime de la un nod (originea) la toate celelalte).

3. Problema rezolvata

Se dau n orase, precum si costul conectarii directe a anumitor perechi de orase. Sa se aleaga acele conectari directe care asigura existenta unei legaturi intre oricare doua orase (intre care poate exista legatura), astfel incat costul total al cablului utilizat pentru conectare sa fie minim si sa se calculeze acest cost. (aceeasi problema ca la lucrarea anterioara)

Rezolvare

Problema se rezolva determinand arborele de acoperire minim pentru graful conectarilor intre orase. Vom aplica tehnica data de algoritmul cautarii cu prioritate. Datele problemei vor fi citite dintr-un fisier cu formatul: numarul de conectari directe, apoi, pentru fiecare conectare directa: identificatorii celor doua orase conectate si costul conectarii (identificatorii si costul se considera a fi un numere intregi). Pentru graful din figura 10.1 fisierul arata astfel:

12 1 2 5 1 3 3 1 4 6 2 3 8 2 5 7 3 4 1 3 5 6 3 6 7 4 6 4 4 7 5 5 6 3 6 7 2

Programul functioneaza si daca graful nu este conex. Daca graful contine noduri izolate, in fisier vom avea, de exemplu, pentru un nod izolat cu cheia 8: 8 8 0    

Nodurile cozii cu prioritate sunt aceleasi cu nodurile grafului. Pentru aceasta, fiecare nod are un camp de inlantuire in graf si altul in coada cu prioritate. Pentru o mai usoara prelucrare a cozii se folosesc doua noduri suplimentare, incCP si sfCP.

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

typedef struct _nodGnodG;

typedef struct _nodLnodL;

enum ;

nodG *incG, *sfG, *incCP, *sfCP;

//inc. si sf. pentru graf, resp. pentru coada

int n, m[3], i, j, costTotal;

FILE *f;

nodG *AdaugNod(int k)else

incG = sfG = p;

return p;

void AdaugMuchie(nodG *s, nodG *d, int cost)else//lista de adiacente este vida

s->incL = s->sfL = l;

nodG *CautaNod(int k)

void AfisImplGraf(void)

p = p->urmG;

}

void adaugaCP(nodG *na, nodG* par, int cost)

void CautPr(nodG *p)

q->marc = marcat;

l = q->incL;

//pozitionarea pe inc. listei de adiacente

while(l)//while(l)

}//sf. prelucrarii cozii

}//sf. if p->marc==nemarcat

p = p->urmG;//trecerea la urmatorul nod al grafului

}//sf. while(p)

void StergGraf()

delete incG;

incG = sfG;

}

void main(void)

//crearea grafului din fisier

fscanf(f, '%d', &n);

for(i=0;i<n;i++)

if(p[0]!=p[1])

}

fclose(f);

AfisImplGraf();

printf('nnMuchiile arborelui de acoperire minim');

CautPr(incG);

printf('nCostul total este %d.', costTotal);

getch();

delete incCP;

delete sfCP;

StergGraf();

4. Probleme propuse

4.1. Pornind de la problema rezolvata de mai sus sa se realizeze urmatoarele:

- sa se evidentieze structura cozii cu prioritate construita; in plus, sa se afiseze in final ordinea relativa in care sunt introduse pe rand nodurile in coada;

- este aceasta ordine relativa aceeasi intotdeauna? Argumentati raspunsul prin alegerea unor exemple concludente.

4.2. Sa se particularizeze algoritmul cautarii cu prioritate pentru grafuri neponderate. Cum trebuie sa consideram prioritatea nodurilor astfel incat sa obtinem traversarea in adancime respectiv prin cuprindere utilizand acest algoritm?