Lucrarea nr.9

TRAVERSAREA GRAFURILOR. APLICATII

1.TRAVERSAREA GRAFURILOR

Rezolvarea multor probleme de grafuri presupune explorarea grafului prin vizitarea (parcurgerea) tuturor nodurilor pornind de la un nod dat. Trecerea de la un nod la altul se face parcurgand arcul de conexiune.

Traversarea se poate face in doua variante: in adancime sau prin cuprindere.

1.1.Traversarea grafurilor in adancime (depth-first search)

Aceasta tehnica generalizeaza traversarea in preordine a arborilor.

Inižial toate nodurile grafului se considera nevizitate, parcurgerea fiecaruia, marcandu-l ca vizitat. Algoritmul face explorarea tuturor nodurilor accesibile dintr-un nod initial. Daca mai raman noduri nevizitate, se alege un nod de pornire din acestea, algoritmul repetandu-se pana toate nodurile sunt marcate ca vizitate.

Exemplul1: Se considera graful din figura 1.

Fig. 1. Exemplu de traversare a unui graf prin cautare in adancime

Se porneste cautarea in adancime pornind de la nodul "a". Noduri accesibile din "a" si nevizitate sunt nodurile "b", "c" si "g". Se alege nodul "b". (Se presupune ca se foloseste o astfel de reprezentare a grafului, astfel incat atunci cand exista mai multe posibilitati de selectare a urmatorului nod, va fi selectat primul in ordinea alfabetica). Din "b", urmatorul nod vizitat va fi nodul "c". Nodul "c" neavand alti vecini nevizitati, traversarea se intoarce la "b", de unde continua cu "d", s.a.m.d.

Pentru implementarea unei proceduri care realizeaza traversarea unui graf prin cautare in adancime, se asociaza fiecarui nod i al grafului o valoare marc[i], care semnifica faptul ca nodul a fost sau nu vizitat. O posibila asignare de valori pentru marc[i] este: marc[i]=0 , daca i este nevizitat, si marc[i]=k, daca i este al k-lea nod vizitat. In functie si de maniera de implementare a grafului, marc poate fi un tablou paralel cu tabloul de noduri sau fiecare nod poate fi completat cu un camp pentru marcare. 

procedure CautaInAdancime(g: Graf; x: Nod);
    { se parcurg toate nodurile din aceeasi componenta 
conexa cu x  prin cautare in adancime }
  var y:Nod;
  begin
   marc[x] := vizitat;
     for * fiecare nod y adiacent lui x   do
        if  (marc[y] = nevizitat) then
    	 CautaInAdancime(g,y)
  end; { CautaInAdancime }

procedure TraversareInAdancime (g:Graf)
  var  x:Nod;
begin
for * fiecare nod x din g  do 
     	marc[x] := nevizitat;
for * fiecare nod x din g do
    if  (marc[x]= nevizitat ) then 
CautaInAdancime(g, x)
  end; {TraversareInAdincime}

Fiecare apel din TraversareInAdancime al procedurii CautaInAdancime, realizeaza parcurgerea cate unei componente conexe a grafului, deci a cate unui arbore de acoperire. Arborii corespunzatori componentelor conexe formeaza o padure de arbori de acoperire. Bineanteles, padurea nu e unica, depinzand de alegerea nodurilor initiale de pornire pentru fiecare arbore.

1.2.Traversarea grafurilor prin cuprindere ( breadth-first search )

Initial toate nodurile grafului se considera nevizitate, parcurgerea fiecaruia, marcandu-l ca vizitat. Algoritmul viziteaza toate nodurile adiacente unui nod initial, apoi se revine la primul nod adiacent si se viziteaza nodurile adiacente acestuia, apoi la al doilea, s.a.m.d. Daca mai raman noduri nevizitate, se alege un nod de pornire din acestea, algoritmul repetandu-se pana toate nodurile sunt marcate ca vizitate. Nodurile adiacente celui initial vor fi trecute intr-o coada. Similar cu traversarea in adancime, cea prin cuprindere, duce la gasirea unei paduri de arbori de acoperire ( componente conexe ) pentru graf.

Exemplul 2. Se considera graful din figura 1. Ordinea nodurilor la cautarea prin cuprindere este data in figura 2.

Fig. 2. Exemplu de traversare a grafului prin cautare prin cuprindere

Nodul de start este nodul "a". Pornind din "a", se viziteaza nodurile "b","c" si "g". Aceste 3 noduri se introduc in coada de asteptare. Primul nod extras din coada va fi "b", si pornind de la "b" se viziteaza "e" si "d". Coada va fi "c","g","e","d". Pornind de la "c" nu mai exista noduri accesibile nevizitate, iar pornind de la "g" se poate vizita nodul "f". De la nici unul din nodurile "e", "d", "f" nu se mai poate continua traversarea., deci algoritmul de cautare prin cuprindere s-a terminat.

Pentru implementarea algoritmului de cautare prin cuprindere, se va folosi o coada de noduri, apartinand unui TDA Coada avand operatorii ADAUGA, SCOATE si VID. 

procedure CautaPrinCuprindere(g: Graf; x: Nod);
{ se parcurg toate nodurile din aceeasi componenta 
conexa cu x prin cautare prin cuprindere }
	var Q:CoadaNoduri;
	begin
 ADAUGA(x,Q);  
 repeat
 x := SCOATE(Q);
 marc[x]:=vizitat;
 for  * fiecare nod y adiacent lui x do
 if  (marc[y] = nevizitat) then
 begin
 marc[y] := vizitat;
 ADAUGA(y,Q);
      end;
until VID(Q);
end; { CautaPrinCuprindere }
           
procedure TraversarePrinCuprindere (g:Graf);
var x:Nod;
begin
for * fiecare nod x din g  do
   marc[x] := nevizitat;
 for * fiecare nod x din g do 
 if (marc[ x]=nevizitat) then
CautaPrinCuprindere(g, x)
end; { TraversarePrinCuprindere }

2.APLICAtII ALE TRAVERSaRII GRAFURILOR

2.1.Determinarea arborilor de acoperire

Dupa cum s-a aratat la traversari, ele conduc la gasirea unei paduri de arbori de acoperire, cate unul pentru fiecare componenta conexa a grafului. Corespunzator celor doua tehnici de traversare (CA - in adancime, CC - prin cuprindere , se pot da doua variante de construire a unui arbore de acoperire. Pentru un graf implementat cu structuri de adiacenta (ultimul caz), pentru marcarea nodurilor vizitate, se adauga campul boolean marc la structura CelulaListNod. Pentru marcarea arcelor arborelui de cautare, se adauga campul boolean marc_Arb la CelulaListArc, valoarea true indicand ca arcul e din arbore.

2.2. Determinarea componentelor conexe

S-a aratat la traversari, ca fiecare apel Cauta pentru cate un nod initial, nevizitat, gaseste cate o componenta conexa. Pentru evidentierea componentelor conexe se poate proceda:

a)Se pot tipari pe cate un rand cheile nodurilor fiecarei componente conexe daca fiecare apel din Traversare la Cauta e precedat de o trecere la linie noua , iar fiecare marcare ca vizitat a unui nod, e urmata de tiparirea cheii nodului.

b)Pentru prelucrarea ulterioara a componenetelor conexe, se introduce tabloul invmarc, paralel cu marc. La marcarea cu marc[x]:=id in Traversare, se va face invmarc[x]:=-id, iar in Cauta, invmarc[x]:=id ca marc. in urma traversarii, ordinea de parcurgere a nodurilor este data de valoarea absoluta din invmarc, valoarea negativa semnaland trecerea la o componenta conexa noua.

2.3.Puncte de articulatie si componente biconexe

Un punct de articulatie intr-un graf conex este un nod care daca este suprimat, graful se divide in mai multe componente conexe. Un graf conex care nu contine puncte de articulatie se numeste biconex - orice pereche de noduri e conectata prin cel putin doua drumuri distincte. Punctele de articulatie se pot determina la parcurgerea in adancime. Se construieste arborele de acoperire obtinut la traversarea in adancime. Un nod x nu este punct de articulatie daca fiecare fiu y al sau are printre descendenti vreun nod conectat cu un nod situat in arbore deasupra lui x. Daca exista o asemenea legatura inseamna ca exista un drum alternativ de la x la y. Radacina este punct de articulatie daca are cel putin doi fii.

Fig. 3. Arbore de cautare in adancime pentru determinarea punctelor de articulatie

Determinarea punctelor de articulatie poate fi implementata pornind de la cautarea in adancime, prin transformarea procedurii de cautare intr-o functie care returneaza cel mai inalt punct din cadrul arborelui de cautare. Se precizeaza ca marcarea nodurilor vizitate se face atribuind nodului numarul de ordine in cadrul traversarii, acelasi ordin rezultand si din traversarea in preordine a arborelui de cautare in adancime. 

  

   function Articulatie(x: integer): integer;

       var t: legatura;
           m,min: integer;

       begin
         id := id + 1; marc[x] := id; min := id;
         t := Stradj[x];
         while t <> z do
           begin
             if marc[t^.nume] = 0 then
               begin
                 m := Articulatie(t^.nume);
                 if (m < min) then min := m;
                 if (m  >= marc[x]) then 
                       writeln(x) {x=punct  de articulatie}
               end
             else
               if marc[t^.nume] < min then 
                        min := marc[t^.nume];
             t := t^.urm
           end;
         Articulatie := min
       end; { Articulatie }
Functia Articulatie determina intr-o maniera recursiva cel mai inalt punct al arborelui care poate fi atins via un arc de retur pentru orice descendent al unui nod x si utilizeaza aceasta informatie pentru a stabili daca x este punct de articulatie.