Tehnici de explorare a grafurilor

Tehnicile de explorare a grafurilor sunt, in principiu, asemanatoare cu cele de traversare a arborilor, cu urmatoarele deosebiri importante:
   - in timp ce traversarea arborilor se face intotdeauna incepand de la radacina, explorarea grafurilor se poate face incepand de la orice varf (nod);
   - la explorarea grafurilor este necesar sa se evite parcurgerea repetata a cicluruilor (circuitelor), care poate duce la situatii in care executarea programului nu se mai opreste.

Explorarea grafului in latime

La explorarea grafului in latime (engleza: breadth first search) se porneste de la un varf oarecare, dat de utilizator. Se viziteaza acest varf. Se viziteaza apoi toate varfurile adiacente acestuia, diferite de el insusi (sa nu uitam ca intr-un digraf exista si bucle, adica arce cu originea si destinatia in acelasi varf). Acestea sunt varfuri de nivel 1. In continuare, dupa ce s-au vizitat toate varfurile de un nivel oarecare i, se trece la vizitarea tuturor varfurilor adiacente acestora, care nu au fost deja vizitate, acestea fiind varfurile de nivel i+1. Se continua astfel pana se epuizeaza toate varfurile catre care exista cel putin o cale din varful initial. In mod similar se procedeaza si la grafurile neorientate.


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

Explorarea grafului in adancime

Pentru explorarea unui graf in adancime (engleza: depth-first search) se porneste de la un varf oarecare si se parcurg varfurile prin metoda cautarii cu revenire (backtracking). Vizitarea fiecarui varf se face la prima sa parcurgere. Tehnica este similara celei de traversare a arborilor in preordine, cu deosebirea ca, atunci cand deplasarea se face in sensul departarii de varful initial, se verifica daca varful nu a fost deja vizitat.

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.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunarea de Jos" din Galati