- Figura 1 -
De exemplu, pentru a explora in latime graful neorientat din figura
1 pornind de la nodul 1, vizitarea nodurilor se face in urmatoarea
ordine: 1, 2, 3, 4, 5, 6, 7. Daca acelasi graf se exploreaza in latime
pornind de la nodul 4, vizitarea nodurilor se face in ordinea 4, 1, 3,
2, 5, 6, 7. Pornind de la nodul 6, explorarea se face in ordinea 6, 3,
5, 7, 2, 1, 3.
Pentru explorarea unui graf in latime se folosesc doua structuri de
date auxiliare. Prima, ca si la traversarea in adancime a arborilor, este
o coada. A doua structura este o multime a varfurilor deja vizitate, care
permite sa nu se viziteze acelasi varf de doua ori. Tehnica de parcurgere
este similara cu cea de la traversarea in latime a arborilor:
- se incepe cu punerea in coada a varfului de la care incepe explorarea; - la fiecare pas ulterior, se extrage un varf din coada (evident, cel din capul cozii) si se viziteaza, fiind pus si in multimea varfurilor vizitate, dupa care se pun in coada toate varfurile adiacente acestuia, cu exceptia celor care se gasesc deja in multimea varfurilor deja vizitate; - explorarea se incheie cand coada este vida. In clasa Graf din fisierul Graf.java, explorarea in latime a grafului se face cu un iterator, care este o instanta a clasei interioare IteratorLatime si se obtine invocand metoda Iterator iteratorLatime(String etichetaVarfPornire). In clasa IteratorLatime se folosesc ca structuri auxiliare coada (campul LinkedList coada) si multimea varfurilor vizitate (campul TreeSet parcurse). S-a folosit clasa TreeSet, deoarece instantele ei sunt multimi sortate, realizate ca arbori bicolori, asigurandu-se astfel pentru punerea si regasirea varfurilor complexitatea O(log n). Iteratorul de explorare in latime este folosit si de metoda List explorareLatime(String etichetaVarfPornire), care intoarce lista varfurilor vizitate in ordinea explorarii in latime. |
De exemplu, la explorarea in adancime a grafului neorientat din figura
1 incepand cu nodul 1, nodurile sunt vizitate in urmatoarea 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, 1, 2, 4, 5, 7. Se viziteaza
astfel toate varfurile catre care exista cel putin o cale de la varful
initial.
La explorarea grafurilor in adancime se folosesc doua structuri de
date auxiliare: o stiva (la fel ca la traversarea arborilor in preordine)
si o multime a varfurilor deja vizitate. Tehnica de parcurgere este similara
cu cea de la traversarea in preordine a arborilor:
- se viziteaza varful cu care se incepe explorarea si se pune atat in stiva, cat si in multimea varfurilor vizitate; - la fiecare pas ulterior se procedeaza astfel: * se examineaza varful de graf situat in varful stivei, fie acesta vk; * daca varful vk mai are fii neparcursi, se viziteaza urmatorul sau fiu si se pune acest fiu atat in varful stivei, cat si in multimea varfurilor vizitate; * daca varful vk nu mai are fii neparcursi, se scoate din stiva; - explorarea se opreste cand stiva este vida. In clasa Graf din fisierul Graf.java, explorarea in adancime a grafului se face cu un iterator, care este o instanta a clasei interioare IteratorAdancime si se obtine invocand metoda Iterator iteratorAdancime(String etichetaVarfPornire). In clasa IteratorAdancime se folosesc ca structuri auxiliare stiva (campul Stack stiva) si multimea varfurilor vizitate (campul TreeSet parcurse). S-a folosit clasa TreeSet, din aceleasi motive ca la explorarea in latime. Iteratorul de explorare in adancime este folosit si de metoda List explorareAdancime(String etichetaVarfPornire), care intoarce lista varfurilor vizitate in ordinea explorarii in adancime. |