Tehnici de explorare a grafurilor

Tehnicile de explorare a grafurilor sunt, în principiu, asemănătoare cu cele de traversare a arborilor, cu urmatoarele deosebiri importante:
   - în timp ce traversarea arborilor se face întotdeauna începand de la rădăcină, explorarea grafurilor se poate face începand de la orice vârf (nod);
   - la explorarea grafurilor este necesar să se evite parcurgerea repetată a cicluruilor (circuitelor), care poate duce la situații în care executarea programului nu se mai oprește.

Explorarea grafului în lățime

La explorarea grafului în lățime (engleză: breadth first search) se pornește de la un vârf oarecare, dat de utilizator. Se vizitează acest vârf. Se vizitează apoi toate vârfurile adiacente acestuia, diferite de el însuși (să nu uităm că într-un digraf există și bucle, adică arce cu originea și destinația în același vârf). Acestea sunt vârfuri de nivel 1. In continuare, după ce s-au vizitat toate vârfurile de un nivel oarecare i, se trece la vizitarea tuturor vârfurilor adiacente acestora, care nu au fost deja vizitate, acestea fiind vârfurile de nivel i+1. Se continuă astfel până se epuizează toate vârfurile către care există cel puțin o cale din vârful inițial. În mod similar se procedează și la grafurile neorientate.


- 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.

Explorarea grafului în adâncime

Pentru explorarea unui graf în adâncime (engleză: depth-first search) se pornește de la un vârf oarecare și se parcurg vârfurile prin metoda căutării cu revenire (backtracking). Vizitarea fiecarui vârf se face la prima sa parcurgere. Tehnica este similară celei de traversare a arborilor în preordine, cu deosebirea că, atunci când deplasarea se face în sensul depărtării de vârful inițial, se verifică dacă vârful către care conduce arcul nu a fost deja vizitat.

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.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați