REPREZENTAREA SI PARCURGEREA GRAFURILOR OARECARE

REPREZENTAREA SI PARCURGEREA GRAFURILOR OARECARE

1 Reprezentarea grafurilor oarecare

Am definit un graf neorientat o pereche de multimi G = (A, B) in care A este multimea nodurilor (este finita si nevida) si B e mutimea relatiilor/muchiilor.

B = I(x, y) / x apartine lui A, y apartine lui AS

A = I1, 2, 3, 4, 5S

B = I(1,2), (1,3), (2,3), (2,5)S

Fig. IV.1

Daca (x, y) apartine de B atunci:

     - x si y sunt noduri adiacente

     - x si y sunt extremitatile arcului (x, y)

     - x si y sunt incidente cu (x, y)

     - in cazul grafurilor orientate:

        - x este extremitatea initiala a (x, y)

        - y este extremitatea finala a (x, y)

     u = (x, y); v = (y, z); => u si v sunt incidente

Exemplu:

• 1 este adiacent cu 2 si 3

• 1 si 2 sunt extremitatile (1,2)

• nodul 1 este incident cu (1,2)

• (5,2) si (2,3) sunt incidente

Gradul unui nod: numarul de muchii incidente cu el

d(x) - gradul nodului x

d(

d(

Nodurile de grad 0 se numesc noduri izolate.

Nodurile de grad 1 se numesc noduri terminale.

Pentru grafuri neorientate

Lantul este o succesiune de noduri x₁ x_k, cu proprietatea ca oricare doua noduri vecine (x_i, x_i+1) apartin de B.

x₁, x_k sunt extremitatile lantului.

Lungimea lantului este egala cu numarul de muchii care il compun, k-1.

Daca nodurile din lant sunt distincte, atunci lantul este elementar.

1, 2, 3,1, 4 - Lant neelementar (lungime 4)

1, 2, 3, 4 - Lant elementar (lungime 3)

1, 2, 3, 1, 2, 5 - Lant neelementar (lungime 5)

1, 2, 3, 5 - Nu este lant

Fig. IV.2

Cicluri - pentru grafuri neorientate

Se numeste ciclu intr-un graf neorientat un lant x₁, x₂ x_k si oricare 2 muchii (x_i, x_i+1) sunt distincte.

Daca un ciclu are toate nodurile distincte 2 cate 2 cu exceptia capetelor, atunci el se numeste ciclu elementar.

1, 2, 3, 4, 1 - Ciclu elementar

2, 3, 4, 1, 2 - Ciclu elementar

1, 2, 3, 4, 2, 3, 1 - Nu este ciclu

1, 2, 3, 4, 2, 5, 1 - Ciclu neelementar

Fig IV.3

Reprezentarea grafurilor in memorie

1. Reprezentarea prin matrice de adiacenta
2. Liste de adiacenta
3. Vector de muchii
4. Matrice arce-noduri

Matricea de adiacenta

Definitie Fie G = (X, G) un graf si n = TXT, p = TGT. Se numeste matrice de adiacenta a grafului G, matricea A_nxn = (a_ij) matricea ale carei elemente satisfac relatia :

aii, js = 1, daca (x_ix_j) IG

aii, js = 0 altfel,

Unde X = Ix₁, x₂, . ., x_nS si unde s-a ales o ordine pe multimea varfurilor.

Observatii:

Pe diagonala principala toate elementele sunt 0 (nu avem bucle).

Matricea este simetrica fata de diagonala principala, deci: aii, js = aij, is.

Citirea unui graf memorat cu ajutorul matricei de adiacenta :

Varianta 1

Citirea numarului de varfuri, citirea regiunii de deasupra diagonalei principale urmata de simetrizare.

var a:arrayi1..120,1..120s of 0..1;

x, d, i, j, n:byte;

begin

write ('nr de varfuri:='); readln(n);

for i:=1 to n-1 do

for j:=i+1 to n do begin

write('ai',i,',',j,'s:='); readln(aii,js);

aij,is:=aii,js;

end;

end.

Varianta 2

Se citesc n-nr de varfuri, m-nr de muchii;

-initializarea matricei de adiacenta cu zero;

-citirea extremitatii fiecarei muchii;

-completarea matricei de adiacenta.

var a:array i1..120,1..120s of 0..1;

x, d, i, j, n:byte;

begin

write('n:='); readln(n);

write('m:='); readln(m);

for i:=1 to n do

for j:=1 to n do aii, js:=0;

for i:=1 to m do begin

writeln ('Muchia ',i,' este:');

readln (x, y);

aix, ys:=1;

aiy, xs:=1;

end;

end

Liste de adiacenta

Daca pe multimea X a grafului G = (X, G) s-a ales o ordine atunci, pentru fiecare varf putem stabili o lista a varfurilor adiacente acestuia (se memoreaza o lista a vecinilor sai). Pentru intregul graf este necesar un vector de liste (P) in care P_i este adresa primului element al listei asociate lui i.

Fig. IV.4

De exemplu, pentru i = 1, informatia din lista figurata mai sus se va completa astfel: pi1s - 2 - 3 - 5.

Fig. IV.5

Observatie: pentru grafurile orientate se memoreaza in lista lui i nodurile k pentru care exista arcul (i, k).

struct elem I

 int nod;

 elem *next; S;

elem *pi100s;

int n;

Vector de muchii

struct muchieI

int x,y; // capetele arcului

S vi100s;

int n,m;

Matricea noduri-arce

Este folosita in special pentru grafurile orientate.

Observatie: matricea noduri-arce poate fi adaptata si pentru grafurile neorientate.
2 Metoda de parcurgere BF

In scopul utilizarii informatiei din varfurilor unui graf este necesara parcurgerea grafului. Parcurgerea unui graf presupune vizitarea (prelucrarea) nodurilor grafului, o singura data fiecare, intr-o anumita ordine.

Nodurile vizitate sunt legate intre ele direct sau indirect.

In functie de ordinea relativa a nodurilor exista 3 metode de parcurgere:

• Metoda parcurgerii pe nivele (pe latime) - Breadth First (BF)
• Metoda de parcurgere D
• Metoda parcurgerii in adancime - Depth First (DF)

Metoda parcurgerii pe latime - Breadh First (BF)

Pentru grafuri neorientate

x = 1

Fig. IV.6

Se porneste de la un nod oarecare x.

Se viziteaza toti vecinii directi ai nodului x daca nu au fost deja vizitati.

Fiecare dintre nodurile vizitate la pasul anterior devine nod curent si este prelucrat la fel ca nodul x.

Structuri de date necesare pentru implementare sunt:

• Matrice de adiacenta (sau alte variante de reprezentare): a
• Coada (in care se memoreaza in ordinea parcursa nodurile vizitate): c
• p, u - indicatorii primului si ultimului element din coada
• Vectorul nodurilor vizitate: v
• viis = 1, daca i a fost vizitat;
• viis = 0, altfel.

Exemplu:

int ai20si20s,n

int vi20s;

void BF(int x)I

 int ci20s,p,u,i; p=u=0; cips=x; vixs=1;

 while (p<=u)I

  cout << cips <<' ';

  for (i=1;i<=n;i++)

   if (aicipssiis && !viis)I

    u++;

    cius=i;

    viis=1;

   S

  p++;

 S

S

Algoritmul BF realizeaza o parcurgere « in latime » a grafului in sensul urmator : se viziteaza un varf initial, etichetat initial cu i, apoi vecinii acestuia (varfurile adiacente lui i), apoi descendentii inca nevizitati ai acestora. De exemplu, pentru graful din figura de mai jos, metoda va furniza urmatoarea ordine de vizitatori : 1, 2, 3, 4, 5, 6, 7, 8.

Fig. IV.7

Asa cum am precizat vom folosi un vector vizins, n=TxT in care :

Viziis = 0 varful i nu a fost vizitat

Viziis =1 varful i a fost vizitat

Vom mai folosi o coada z in care vom introduce varfurile vizitate. Prelucarea nodului (varfului) din fata cozii presupune introducerea in coada a tuturor vecinilor acestuia, inca nevizitati urmata de vizitarea lor.

Algoritmul BF:

procedure BF (i,n)

i: varful de la care se pleaca

n: nr de varfuri; n=TxT

z: coada cu indicii F(fata) si R(spatele)

VIZITARE : functie care prelucreaza informatia dintr-un varf

for k=1,n do

Viziks

next k

VIZITARE (i) ; viziis 1 ; F R z(R) i ;

while F≤R do

for k=1, n do

if exista (xiz(F)s, xiks) I G and (viziks=0) then

R R+1 ; z k ;

VIZITARE(k) ; viziks

End if

next k

F F+1

end while

I

Pentru a arata modul cum s-a facut vizitarea se pot afisa nodurile din z

S

end BF

Se poate demonstra ca algoritmul lucreaza corect, adica sunt vizitate toate varfurile j care sunt legate printr-un lant de varful i.

Fie d (i, j) = lungimea minima (masurata in muchii) a unui lant care uneste pe i cu j. Daca nu exista un astfel de lant atunci d (i, j) = . Aratam prin inductie ca mIN, algoritmul viziteaza toate varfurile j cu d (I, j) = m.

Pentru m = 0, este evident ca varful i este vizitat la inceput. Presupunem ca sunt vizitate toate varfurile j cu d (i,j) <= m.

Fie j un varf cu d (i, j) = m+1 si fie k predecesorl lui j. Atunci d (i, k) = m si daca k este vizitat, conform ipotezei de inductie. Cum vizitarea lui k este insotita de introducerea lui k in coada, iar aceasta genereaza prelucarea lui k rezulta ca varful j va fi vizitat.

Observatie Algoritmul BF parcurge varfurile legate de i prin lanturi in ordine crescatoare a distantei fata de i. Algoritmul BF viziteaza, dupa un varf k, pe primul dintre vecinii acestuia inca nevizitati.

Pentru a efectua o parcurgere in latime a unui graf (orientat sau neorientat), aplicam practic 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.

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

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

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

Procedurile iterad si lat trebuie apelate din procedura

procedure parcurge(G)
     for fiecare v V do marcaivs   nevizitat
     for fiecare v  V do
          if marcaivs = nevizitat then Iiterad sau latS (v)

De exemplu, pentru graful din III.8, 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) (n+m), daca reprezentam graful prin liste de adiacenta; ii) (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.

Program pentru BF

Se va utiliza o coada. Initial, in coada se afla doar varful initial, la fiecare pas se va prelucra varful aflat la inceputul cozii.Consideram toti vecinii nevizitati ai acestuia si ii adaugam in coada dupa care,varful fiind prelucrat va fi eliminat din coada. Prelucrarea se va face atata timp cat exista elemente in coada.

Pentru a retine varfurile vizitate folosim un vector boolean cu semnificatia:

Viz iis = true,daca varful i a fost vizitat

= false, altfel

Initial, toate varfurile sunt nevizitate.

var c:arrayi1..20sf byte;

a:arrayi1..20 ..20sof 0..1;

viz:arrayi1..20sof boolean;

vi,vc,n,u,i,p:byte;

Ip-indicele primului element din coada

u-indicele ultimului

vi:varful initial;

vc:varful curentS

begin

Icitire grafS

write('varf initial:='); readln(vi);

for i:=1 to n do viziis:=false;

p

u

ci1s:=vi;

vizivis:=true;

while p<=u do begin

vc:=cips;

for i:=1 to n do

if aivc,is=1 and not viz(i) then

begin

u:=u+1;

cius:=i;

viziis:=true;

end;

p:=p+1;

end

for i:=1 to n do write(ciis,' ');

readln

end

3 Metoda de parcurgere D

Metoda D se deosebeste de algoritmul BF prin faptul ca dupa prelucarea varfului k, se trece la prelucarea ultimului vecin al lui k dintre cei nevizitati. Aceasta se va concretiza prin utilizarea unei stive in care sunt introduse varfurile vizitate. Spre exemplu pentru graful de mai sus, metoda va produce urmatoarea ordine de vizitare :

4 Metoda de parcurgere DF

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  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 Iv, wS 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  V do marcaivs  nevizitat
     for fiecare v  V do
          if marcaivs = nevizitat then ad(v)

procedure ad(v)
     Ivirful v nu a fost vizitatS
     marcaivs  vizitat
     for fiecare virf w adiacent lui v do
          if marcaiws = 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 de mai jos, 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.

Fig. IV.8 Un graf neorientat si unul din arborii sai partiali

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 n) pentru apelurile procedurii ad si un timp in (m) pentru inspectarea marcilor. Timpul de executie este deci in (max(m, n)) =  (m+n).

Daca reprezentam graful printr-o matrice de adiacenta, se obtine un timp de executie in (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 de mai sus, un astfel de arbore este reprezentat in figura alaturata 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
preordivs  num

unde num este o variabila globala initializata cu zero, iar preordi1 .. ns 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 de mai sus.

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

Algoritmul DF incearca sa mearga in 'adancimea grafului' ori de cate ori este posibil. Astfel, prelucarea varfului v_k, care are vecinii v_k¹, . , v_k^p, inseamna prelucarea primului dintre acesti vecini care este nevizitat, sa presupunem v_k^j , 1 j p. Deci se va trece la prelucarea varfului v_k^j si a vecinilor nevizitati ai lui v_k.

Va trebui sa utilizam o stiva care, la pasul curent, sa ne dea posibilitatea de a memora varful v_k pentru a reveni la el si a prelucra vecinii lui ramasi nevizitati. Vom mai folosi un vector ultim ins, n=TxT cu elemente avand semnificatia : ultimiks = ultim vizitat dintre vecinii lui k.

Pentru graf-ul din figura de mai jos ordinea de parcurgere este: 1, 2, 5, 3, 7, 6, 4, 8

Fig. IV.9

Exemplu X = 1

Se porneste de la un nod oarecare x.

Se alege primul vecin al lui x care nu a fost inca vizitat.

Pentru nodul ales se reia procedeul.

Daca un nod nu are nici un vecin nevizitat se revine la nodul vizitat anterior acestuia.

Structuri de date necesare implementarii:

• Matrice de adiacenta (sau alte variante): a
• Stiva: s (in care se memoreaza nodurile in ordinea parcurgerii)

Dacase implementeaza varianta recursivase va folosi stiva procesorului

• Vectorul nodurilor vizitate: v

int ai20si20s,u;

int vi20s;

void DF(int x)I

 cout<<x<<' ';

 vixs=1;

 for(int i=1;i<=n;i++)

  if(aixsiis && !viis)

   DF(i);

S