Parcurgerea grafurilor in adancime

Parcurgerea grafurilor in adancime

Fie G = <V, M> un graf orientat sau neorientat, ale carui varfuri dorim sa le consultam. Presupunem ca avem posibilitatea sa marcam varfurile deja vizitate in tabloul global marca. Initial, nici un varf nu este marcat.

Pentru a efectua o parcurgere in adancime, alegem un varf oarecare, v I V, ca punct de plecare si il marcam. Daca exista un varf w adiacent lui v (adica, daca exista muchia (v, w) in graful orientat G, sau muchia in graful neorientat G) care nu a fost vizitat, alegem varful w ca noul punct de plecare si apelam recursiv procedura de parcurgere in adancime. La intoarcerea din apelul recursiv, daca exista un alt varf adiacent lui v care nu a fost vizitat, apelam din nou procedura etc. Cand toate varfurile adiacente lui v au fost marcate, se incheie consultarea inceputa in v. Daca au ramas varfuri in V care nu au fost vizitate, alegem unul din aceste varfuri si apelam procedura de parurgere. Continuam astfel, pana cand toate varfurile din V au fost marcate. Iata algoritmul:

procedure parcurge(G)
     for fiecare v I V do marca[v]   nevizitat
     for fiecare v I V do
          if marca[v] = nevizitat then ad(v)

procedure ad(v)
    
     marca[v] vizitat
     for fiecare virf w adiacent lui v do
          if marca[w] = nevizitat then ad(w)

Acest mod de parcurgere se numeste "in adancime", deoarece incearca sa initieze cat mai multe apeluri recursive inainte de a se intoarce dintr-un apel.

Parcurgerea in adancime a fost formulata cu mult timp in urma ca o tehnica de explorare a unui labirint. O persoana care cauta ceva intr-un labirint si aplica aceasta tehnica are avantajul ca "urmatorul loc in care cauta" este mereu foarte aproape.

Pentru graful din Figura 9.1a, presupunand ca pornim din varful 1 si ca vizitam vecinii unui varf in ordine numerica, parcurgerea varfurilor in adancime se face in ordinea: 1, 2, 3, 6, 5, 4, 7, 8.

Desigur, parcurgerea in adancime a unui graf nu este unica; ea depinde atat de alegerea varfului initial, cat si de ordinea de vizitare a varfurilor adiacente.

Cat timp este necesar pentru a parcurge un graf cu n varfuri si m muchii? Deoarece fiecare varf este vizitat exact o data, avem n apeluri ale procedurii ad. In procedura ad, cand vizitam un varf, testam marcajul fiecarui vecin al sau. Daca reprezentam graful prin liste de adiacenta, adica prin atasarea la fiecare varf a listei de varfuri adiacente lui, atunci numarul total al acestor testari este: m, daca graful este orientat, si 2m, daca graful este neorientat. Algoritmul necesita un timp in Q n) pentru apelurile procedurii ad si un timp in Q(m) pentru inspectarea marcilor. Timpul de executie este deci in Q max(m, n)) = Q(m n

Daca reprezentam graful printr-o matrice de adiacenta, se obtine un timp de executie in Q n

Parcurgerea in adancime a unui graf G, neorientat si conex, asociaza lui G un arbore partial. Muchiile arborelui corespund muchiilor parcurse in G, iar varful ales ca punct de plecare devine radacina arborelui. Pentru graful din Figura 9.1a, un astfel de arbore este reprezentat in Figura 9.1b prin muchiile "continue"; muchiile din G care nu corespund unor muchii ale arborelui sunt "punctate". Daca graful G nu este conex, atunci parcurgerea in adancime asociaza lui G o padure de arbori, cate unul pentru fiecare componenta conexa a lui G.

Daca dorim sa si marcam numeric varfurile in ordinea parcurgerii lor, adaugam in procedura ad, la inceput:

num num  1
preord[v]   num

unde num este o variabila globala initializata cu zero, iar preord[1 .. n] este un tablou care va contine in final ordinea de parcurgere a varfurilor. Pentru parcurgerea din exemplul precedent, acest tablou devine:

Cu alte cuvinte, se parcurg in preordine varfurile arborelui partial din Figura 9.1b.

Se poate observa ca parcurgerea in adancime a unui arbore, pornind din radacina, are ca efect parcurgerea in preordine a arborelui.

Parcurgerea grafurilor in latime

Procedura de parcurgere in adancime, atunci cand se ajunge la un varf v oarecare, exploreaza prima data un varf w adiacent lui v, apoi un varf adiacent lui w etc. Pentru a efectua o parcurgere in latime a unui graf (orientat sau neorientat), aplicam urmatorul principiu: atunci cand ajungem intr-un varf oarecare v nevizitat, il marcam si vizitam apoi toate varfurile nevizitate adiacente lui v, apoi toate varfurile nevizitate adiacente varfurilor adiacente lui v etc. Spre deosebire de parcurgerea in adancime, parcurgerea in latime nu este in mod natural recursiva.

Pentru a putea compara aceste doua tehnici de parcurgere, vom da pentru inceput o versiune nerecursiva pentru procedura ad. Versiunea se bazeaza pe utilizarea unei stive. Presupunem ca avem functia ftop care returneaza ultimul varf inserat in stiva, fara sa il stearga. Folosim si functiile push si pop din Sectiunea 3.1.1.

procedure iterad(v)
     S   stiva vida
     marca[v]   vizitat
     push(v, S)
     while S nu este vida do
          while exista un varf w adiacent lui ftop(S)
           astfel incat marca[w] = nevizitat   do
      marca[w] vizitat
      push(w, S)
          pop(S)

Pentru parcurgerea in latime, vom utiliza o coada si functiile insert-queue, delete-queue din Sectiunea Iata acum algoritmul de parcurgere in latime:

procedure lat(v)
     C   coada vida
     marca[v]   vizitat
     insert-queue(v, C)
     while C nu este vida do
          u   delete-queue(C)
          for fiecare virf w adiacent lui u do
      if marca[w] = nevizitat  then  marca[w]   vizitat
                      insert-queue(w, C)

Procedurile iterad si lat trebuie apelate din procedura

procedure parcurge(G)
     for fiecare v I V do marca[v]   nevizitat
     for fiecare v I V do
          if marca[v] = nevizitat then (v)

De exemplu, pentru graful din Figura 9.1, ordinea de parcurgere in latime a varfurilor este: 1, 2, 3, 4, 5, 6, 7, 8.

Ca si in cazul parcurgerii in adancime, parcurgerea in latime a unui graf G conex asociaza lui G un arbore partial. Daca G nu este conex, atunci obtinem o padure de arbori, cate unul pentru fiecare componenta conexa.

Analiza eficientei algoritmului de parcurgere in latime se face la fel ca pentru parcurgerea in adancime. Pentru a parcurge un graf cu n varfuri si m muchii timpul este in: i) Q(n m), daca reprezentam graful prin liste de adiacenta; ii) Q(n²), daca reprezentam graful printr-o matrice de adiacenta.

Parcurgerea in latime este folosita de obicei atunci cand se exploreaza partial anumite grafuri infinite, sau cand se cauta cel mai scurt drum dintre doua varfuri.