- Figura 1 -
- Figura 2 -
S-au obtinut astfel arbori liberi. Alegand in fiecare din ei un nod oarecare drept radacina si rearanjand celelalte noduri pe nivele, se obtin arbori obisnuiti.
Daca graful nu este conex, se poate construi cate un arbore de acoperire pentru fiecare subgraf conex al sau.
Conceptul de arbore de acoperire poate fi cu usurinta extins si la grafurile
orientate.
In cazul arborilor de acoperire construit prin explorarea grafului in
latime, calea de la varful initial la oricare din celelalte varfuri se
realizeaza prin parcurgerea unui numar minim de arce. Aceasta proprietate
rezulta din insasi tehnica folosita la construirea arborelui. In consecinta,
arborele de acoperire obtinut prin explorare in latime are cea mai mica
inaltime dintre toti arborii de acoperire care pornesc din acelasi varf
al grafului.
Generarea arborelui de acoperire prin explorarea grafului in latimeGenerarea arborelui de acoperire cu explorare a grafului in latime, pornind dintr-un varf initial dat se face astfel:- se creeaza un arbore vid; - se creeaza coada varfurilor de vizitat si multimea varfurilor parcurse (initial ambele sunt vide); - se pune varful initial in multime; - se pune in coada un element (varfInitial, null), care contine o referinta la varful initial si o referinta nula (catre "parintele" varfului initial); - se intra intr-un ciclu in care, cat timp coada nu este vida: * se scoate din capul cozii elementul curent (varfCurent, parinte); * se ataseaza nodului parinte al arborelui un nou nod, care contine o referinta la varfCurent; daca referinta la parinte este nula, varfCurent devine radacina arborelui; * pentru fiecare varf adiacent al lui varfCurent, care nu este in multime, se pune aest varfAdiacent in multime si sepune in coada un element de forma (varfAdiacent, varfCurent), in care varfCurent este pe pozitia de parinte al lui varfAdiacent. Generarea arborelui de acoperire se incheie cand coada este vida. Ca exemplu, in clasa Graf.java exista metoda
Observatie: La executarea aplicatiei TestGraf1 trebuie sa aveti in acelasi fisier codurile de octeti ale claselor TestGraf1, Graf1, Graf si Arbore. Generarea arborelui de acoperire prin explorarea grafului in adancimeGenerarea arborelui de acoperire prin explorarea grafului in adancime, pornind de la un varfInitial dat, se face astfel:- se creeaza multimea varfurilor parcurse si stiva varfurilor deExplorat; initial acestea sunt vide; - se pune varfInitial in multimea varfurilor parcurse; - se creeaza un arbore care contine ca radacina un nodArbore, avand ca informatie eticheta lui varfInitial; - se pune in stiva varfurilor deExplorat un element de forma (nodArbore, iteratorFii) unde iteratorFii este un iterator al listei fiilor lui varfInitial. - se intra intr-un ciclu in care, cat timp stiva nu este
vida:
Generarea arborelui de acoperire se incheie cand stiva devine vida. In locul utilizarii explicite a stivei, in modul descris mai sus, generarea
arborelui de acoperire pentru explorarea grafului in adancime se poate
face utilizand o metoda recursiva. In acest caz, se utilizeaza
explicit numai multimea varfurilor parcurse, iar drept stiva se foloseste
in mod implicit cea folosita de sistem pentru realizarea recursiei. In
clasa Graf1, din fisierul Graf.java, generarea
unui astfel de arbore se face prin metoda
Aceasta posibilitate a abordarii recursive constituie un avantaj al arborilor de acoperire obtinuti prin explorarea grafului in adancime. Desavantajul unor astfel de arbori (indiferent ca au fost obtinuti recursiv sau folosind stiva in mod explicit) este ca au, de regula, inaltime mai mare ca cei obtinuti prin explorare in latime. Testarea pentru graful din figura 3 este facuta in aplicatia din fisierul TestGraf1.java. |