- Figura 1 -
- Figura 2 -
S-au obținut astfel arbori liberi. Alegând în fiecare din ei un nod oarecare drept rădăcină și rearanjând celelalte noduri pe niveluri, se obțin arbori obisnuiți.
Dacă graful nu este conex, se poate construi câte un arbore de acoperire pentru fiecare subgraf conex al său.
Conceptul de arbore de acoperire poate fi cu usurință extins și la
grafurile orientate.
În cazul arborilor de acoperire construiți prin explorarea grafului
în lățime, calea de la vârful inițial la oricare din celelalte vârfuri
se realizează prin parcurgerea unui număr minim de arce. Această
proprietate rezultă din însăși tehnica folosită la construirea
arborelui. În consecință, arborele de acoperire obținut prin explorare
în lățime are cea mai mică înălțime dintre toți arborii de acoperire
care pornesc din același vârf al grafului.
Generarea arborelui de acoperire prin explorarea grafului în lățimeGenerarea arborelui de acoperire cu explorare a grafului în lățime, pornind dintr-un vârf inițial dat se face astfel:- se creează un arbore vid; - se creează coada vârfurilor de vizitat și mulțimea vârfurilor parcurse (inițial ambele sunt vide); - se pune vârful inițial în mulțime; - se pune în coadă un element de forma (varfInitial, null), care conține o referință la vârful inițial și o referință nulă (către "părintele" vârfului inițial); - se intră într-un ciclu în care, cât timp coada nu este vidă: * se scoate din capul cozii elementul curent (varfCurent, parinte); * se ataseaza nodului parinte al arborelui un nou nod, care conține o referință la varfCurent; daca referința la părinte este nulă, varfCurent devine rădăcina arborelui; * pentru fiecare vârf adiacent al lui varfCurent, care nu este în mulțime sau în coada, se pune aest varfAdiacent în mulțime și se pune în coada un element de forma (varfAdiacent, varfCurent), în care varfCurent este pe poziția de părinte al lui varfAdiacent. Generarea arborelui de acoperire se încheie când coada este vidă. Ca exemplu, în clasa Graf.java există
metoda
Observatie: La executarea aplicației TestGraf1 trebuie să avem în acelasi director codurile de octeți ale claselor TestGraf1, Graf1, Graf și Arbore. Generarea arborelui de acoperire prin explorarea grafului în adâncimeGenerarea arborelui de acoperire prin explorarea grafului în adâncime, pornind de la un varfInitial dat, se face astfel:- se creează mulțimea vârfurilor parcurse și stiva vârfurilor deExplorat; inițial acestea sunt vide; - se pune varfInitial în mulțimea vârfurilor parcurse; - se creează un arbore care conține ca rădăcină un nodArbore, având ca informație eticheta nodului varfInitial; - se pune în stiva vârfurilor deExplorat un element de forma (nodArbore, iteratorFii) unde iteratorFii este un iterator al listei fiilor lui varfInitial. - se intră într-un ciclu în care, cât timp stiva nu este
vidă: Generarea arborelui de acoperire se încheie cănd stiva devine vidă. În locul utilizarii explicite a stivei în modul descris mai
sus, generarea arborelui de acoperire pentru explorarea grafului în
adancime se poate face utilizand o metodă recursivă. În
acest caz, se utilizează explicit numai mulțimea vârfurilor parcurse,
iar drept stivă se folosește în mod implicit cea folosită de sistem
pentru realizarea recursiei. În clasa Graf1, din fișierul Graf.java, generarea unui astfel de arbore se
face prin metoda Această posibilitate a abordării recursive constituie un avantaj al arborilor de acoperire obtinuți prin explorarea grafului în adâncime. Desavantajul unor astfel de arbori (indiferent că au fost obtinuți recursiv sau folosind stiva în mod explicit) este că au, de regulă, înălțimea mai mare ca cei obtinuți prin explorare în lățime. Testarea pentru graful din figura 3 este făcută în aplicația din fișierul TestGraf1.java. |