- Figura 1 -
De exemplu, pentru a explora în lățime graful neorientat din figura
1 pornind de la nodul 1, vizitarea nodurilor se face în următoarea
ordine: 1, 2, 3, 4, 5, 6, 7. Dacă același graf se explorează în lățime
pornind de la nodul 4, vizitarea nodurilor se face în ordinea 4, 1, 3,
2, 5, 6, 7. Pornind de la nodul 6, explorarea se face în ordinea 6, 3,
5, 7, 2, 1, 4.
Pentru explorarea unui graf în lățime se folosesc două
structuri de date auxiliare. Prima, ca și la traversarea în lățime a
arborilor, este o coadă. A doua structură este o mulțime a vârfurilor
deja vizitate, care este consultată la fiecare trecere la un vârf nou,
pentru ca să nu se viziteze același vârf de doua ori. Tehnica de
parcurgere este similară cu cea de la traversarea în lățime a
arborilor: - se începe cu punerea în coadă a vârfului de la care începe explorarea; - la fiecare pas ulterior, se extrage un vârf din coadă (evident, cel din capul cozii) și se vizitează, fiind pus și în mulțimea vârfurilor vizitate, după care se pun în coadă toate vârfurile adiacente acestuia, cu excepția celor care se găsesc deja în coadă sau în mulțimea vârfurilor deja vizitate; - explorarea se încheie când coada este vidă. În clasa Graf din fișierul Graf.java, explorarea în lățime a grafului se face cu un iterator, care este o instanță a clasei interioare IteratorLatime și se obține invocând metoda Iterator iteratorLatime(String etichetaVarfPornire). În clasa IteratorLatime se folosesc ca structuri auxiliare coada (campul LinkedList coada) și mulțimea vârfurilor vizitate (campul TreeSet parcurse). S-a folosit clasa TreeSet, deoarece instanțele ei sunt mulțimi sortate, realizate ca arbori bicolori, asigurându-se astfel pentru punerea si regăsirea vârfurilor complexitatea O(log n). Iteratorul de explorare în lățime este folosit și de metoda List explorareLatime(String etichetaVarfPornire), care întoarce lista varfurilor vizitate în ordinea explorării în lățime. |
De exemplu, la explorarea în adâncime a grafului neorientat din figura
1 începand cu nodul 1, nodurile sunt vizitate în următoarea ordine:
1, 2, 3, 5, 6, 7, 4. La explorarea in adancime a aceluiasi graf incepand
cu nodul 3, vizitarea se face in ordinea 3, 1, 2, 4, 5, 6, 7. La
explorarea incepand cu nodul 6, ordinea de vizitare este 6, 3, 4, 1, 2,
5, 7. Se vizitează astfel toate vârfurile către care există cel puțin o
cale de la vârful inițial.
La explorarea grafurilor în adâncime se folosesc două
structuri de date auxiliare: o stivă (la fel ca la traversarea
arborilor în preordine) și o mulțime a vârfurilor deja vizitate.
Tehnica de parcurgere este similară cu cea de la traversarea în
preordine a arborilor: - se vizitează vârful cu care se începe explorarea și se pune atat în stivă, cât și în mulțimea vârfurilor vizitate; - la fiecare pas ulterior se procedează astfel: * se examinează vârful de graf situat în vârful stivei, fie acesta vk; * dacă vârful vk mai are fii neparcurși, se vizitează următorul său fiu și se pune acest fiu atât în vârful stivei, cât și în mulțimea vârfurilor vizitate; * dacă vârful vk nu mai are fii neparcursi, se scoate din stivă; - explorarea se oprește când stiva este vidă. În clasa Graf din fișierul Graf.java, explorarea în adâncime a grafului se face cu un iterator, care este o instanța a clasei interioare IteratorAdancime și se obține invocând metoda Iterator iteratorAdancime(String etichetaVarfPornire). În clasa IteratorAdancime se folosesc ca structuri auxiliare stiva (câmpul Stack stiva) și mulțimea vârfurilor vizitate (câmpul TreeSet parcurse). S-a folosit clasa TreeSet, din aceleași motive ca la explorarea în lățime. Iteratorul de explorare în adâncime este folosit și de metoda List explorareAdancime(String etichetaVarfPornire), care întoarce lista vârfurilor vizitate în ordinea explorării în adâncime. |