Grafuri

Parcurgerea DF a grafurilor neorientate

Fie G=(V,M) un graf neorientat. Ca de obicei, notam n=|V| si m=|M|

Parcurgere in adancime a grafurilor (DF = Depth First) generalizeaza parcurgerea in preordine a arborilor oarecare. Eventuala existenta a ciclurilor conduce la necesitatea de a marca varfurile vizitate. Ideea de bazǎ a algoritmului este urmǎtoarea: se pleacǎ dinr-un varf i₀ oarecare, apeland procedura DF pentru acel varf. Orice apel de tipul DF(i) prevede urmǎtoarele operatii:

marcarea varfului i ca fiind vizitat;

pentru toate varfurile j din lista L_i a vecinilor lui i se executǎ apelul DF(j) daca si numai dacǎ varful j nu a fost vizitat.

Simpla marcare a unui varf ca fiind sau nu vizitat poate fi inlocuitǎ cu atribuirea unui numǎr de ordine fiecǎrui varf; mai precis, in nrdf(i), initial egal cu 0, va fi memorat al catelea este vizitat varful i nrdf(i) poartǎ numele de numǎrul (de ordine) DF al lui i

Este evident cǎ plecand din varful i₀ se pot vizita numai varfurile din componenta conexǎ a lui i₀. De aceea, in cazul in care graful nu este conex, dupǎ parcurgerea componentei conexe a lui i₀ vom repeta apelul DF pentru unul dintre eventualele varfuri incǎ neatinse.

procedure DF(i)

ndf ndf+1; nrdf(i) ndf; vizit(i);

for toti jIL_i

if nrdf(j)=0 then DF(j)

Programul principal este:

citeste graful;

ndf

for i=1,n

nrdf(i)

for i=1,n

if nrdf(i)=0 then DF(i)

scrie nrdf;

Lucrul cu tablouri in Java

Un tablou este o secventa de componente de acelasi tip. Acest tip poate fi un tip primitiv sau un tip referinta (deci putem lucra cu tablouri de obiecte).

Un tablou a poate fi declarat folosind una dintre urmatoarele modalitati:

tip[] a;

tip a[];

unde tip este tipul componentelor tabloului. In continuare vom folosi numai prima forma.

Declararea unui tablou nu are drept consecinta crearea sa. Crearea tabloului a declarat mai sus trebuie facuta explicit, prin:

a = new tip[n];

unde n este o constanta sau o variabila intreaga ce a primit o valoare strict pozitiva.

Cele de mai sus devin clare daca specificam faptul ca un tablou este un tip referinta. Prin creare se obtine un obiect de tip tablou (obiect numit prin abuz de limbaj tot tablou).

Componentele tabloului pot fi referite prin a[i], cu i luand valori in intervalul 0..n-1; daca i nu este in acest interval, va fi semnalata o eroare la executare. Lungimea tabloului poate fi referita prin a.length

Declararea si crearea pot fi facute si simultan prin:

tip[] a = new tip[n];

sau printr-o initializare efectiva, ca de exemplu:

int[] a =

prin care, evident, a.length devine 5.

Variabilei referinta la tablou i se poate asocia o referinta la un tablou de acelasi tip.

Exemplul 1. Urmatoarea secventa de program:

tip[] a ;

a = new tip[10];

a = new tip[20];

este corecta. Evident, noul tablou nu are nici o legatura cu cel vechi (in particular nu se pastreaza valoarea nici unei componente a tabloului vechi).

Exemplul 2. Pentru interschimbarea continutului a doua tablouri se poate proceda la fel ca pentru interschimbarea valorilor a doua variabile primitive:

int[] a = , b = , c;

c=a; a=b; b=c;

deci practic se interschimba referintele la cele doua tablouri.

Exemplul 3. Deoarece un tablou este un tip referinta, transmiterea sa ca argument la invocarea unei metode se supune regulilor referitoare la apelul prin valoare. Astfel, executarea urmatorului program:

class C

class Tablou2 {

public static void main(String[] s) {

int[] a = ;

C Ob = new C(); Ob.met(a);

for (int i=0 ; i<a.length; i++) IO.write(a[i]+' ');

}

va produce la iesire:

Mai precizam ca un tablou de caractere nu este un sir de caractere.

Limbajul Java permite lucrul cu tablouri multidimensionale. De exemplu expresia C[][] este un tip ce reprezinta tablouri bidimensionale ale caror componente au tipul C

Tablourile multidimensionale trebuie gandite ca tablouri unidimensionale ale caror elemente sunt tablouri unidimensionale etc. De aceea referirea la un element al unui tablou multidimensional a se face prin: a[indice₁][indice_n]

Este suficient sa reducem discutia la tablouri bidimensionale, generalizarea fiind imediata. Sa consideram urmatorul exemplu:

int[][] a = new int[3][];

a[0] = new int[3];

a[1] = new int[4];

a[2] = new int[2];

Ia nastere astfel un tablou de forma:

ceea ce arata ca in Java tablourile nu sunt neaparat dreptunghiulare; aceasta conduce desigur la economie de spatiu.

Evident, a[1].length=4

La aceeasi structura se poate ajunge si printr-o initializare efectiva:

int[][] a = , , };

care in plus atribuie valori elementelor tabloului.

Daca in referirea la un element al unui tablou unul dintre indici nu este in intervalul corespunzator, va aparea eroarea (numita in Java exceptie) cu numele:

IndexOutOfBoundsException

Parcurgerea in adancime a unui graf neorientat (program Java)

Vom folosi pentru exemplificare urmatorul graf:

pentru care listele vecinilor varfurilor sunt:

L L₁=; L₂=; L₃=;

L L₅=; L₆=Æ L₇=.

class df

mat[i] = new int[ntemp];

for (int j=0; j<ntemp; j++) mat[i][j] = temp[j];

}

IO.writeln(' ** ** ');

}

void parcurg()

}

private void DF(int i)

}

class ParcDF

Parcurgerea DF a grafurilor neorientate (continuare)

Observatie. Dacǎ dorim doar sǎ determinǎm dacǎ un graf este conex, vom inlocui al doilea ciclu for din programul principal prin:

DF(1)

if ndf=n then write('CONEX')

else write('NECONEX');

Observatie. Parcurgerea DF imparte muchiile grafului in:

muchii de avansare: sunt acele muchii (i,j) pentru care in cadrul apelului DF(i) are loc apelul DF(j). Aceste muchii formeazǎ un graf partial care este o pǎdure: fiecare varf este vizitat exact o datǎ, deci nu existǎ un ciclu format din muchii de avansare.

muchii de intoarcere: sunt acele muchii ale grafului care nu sunt muchii de avansare.

Determinarea multimilor A si I a muchiilor de avansare si intoarcere, precum si memorarea arborilor partiali din padurea DF se poate face astfel:

in programul principal se fac initializarile:

A Æ; I Æ

for i=1,n

tata(i)

instructiunea if din procedura DF devine:

if nrdf(j)=0

then A AÈ; tata(j) i; DF(j);

else if tata(j)¹ i

then I IÈ

Exemplu. Pentru graful urmator:

cu urmatoarele liste ale vecinilor varfurilor:

L₁ L₂=; L₃=;

L₄ L₅=; L₆=;

L₇ L₈= L₉=

padurea DF este formata din urmatorii arbori partiali corespunzatori componentelor conexe:

Timpul cerut de algoritmul de mai sus este O(max)=O(n+m), adica liniar, deoarece:

pentru fiecare varf i, apelul DF(i) are loc exact o datǎ;

executarea unui apel DF(i) necesitǎ un timp proportional cu grad(i)=|L_i|; in consecintǎ timpul total va fi proportional cu m=|M|

Propozitie. Dacǎ (i,j) este muchie de intoarcere, atunci i este descendent al lui j

Muchia (i,j) este detectatǎ ca fiind muchie de intoarcere in cadrul executǎrii apelului DF(i), deci nrdf(j)<nrdf(i). Deoarece existǎ muchie intre varfurile i si j, rezultǎ cǎ in timpul executǎrii lui DF(j) va fi vizitat si varful i, deci i este descendent al lui j

Propozitia de mai sus spune cǎ muchiile de intoarcere leagǎ totdeauna douǎ varfuri situate pe aceeasi ramurǎ a pǎdurii partiale DF. In particular, nu exista muchii de traversare (care sa lege doi descendenti ai aceluiasi varf dintr-un arbore DF).

Observatie. Un graf este ciclic (contine cel putin un ciclu) dacǎ si numai dacǎ in timpul parcurgerii sale in adancime este detectatǎ o muchie de intoarcere.

Aplicatie. Sǎ se determine dacǎ un graf este ciclic si in caz afirmativ sǎ se identifice un ciclu.

Vom memora pǎdurea formatǎ din muchiile de avansare cu ajutorul vectorului tata si in momentul in care este detectatǎ o muchie de intoarcere (i,j) vom lista drumul de la i la j format din muchii de avansare si apoi muchia (j,i)

Procedura DF va fi modificata astfel:

procedure DF(i)

ndf ndf+1; nrdf(i) ndf; vizit(i);

for toti jIL_i

if nrdf(j)=0

then tata(j) i; DF(j)

else if tata(j)¹i

then k i;

while k¹j

write(k,tata(k)); k tata(k);

write(j,i); stop

end.

Observatii:

daca notam prin nrdesc(i) numarul descendentilor lui i in subarborele de radacina i, aceasta valoare poate fi calculata plasand dupa ciclul for din procedura DF instructiunea nrdesc(i) ndf-nrdf(i)+1

un varf j este descendent al varfului i in subarborele DF de radacina i Û nrdf(i)£nrdf(j)<nrdf(i)+nrdesc(i)

O aplicatie: Problema barfei

Se considera n persoane. Fiecare dintre ele emite o barfa care trebuie cunoscuta de toate celelalte persoane.

Prin mesaj intelegem o pereche de numere (i,j) cu i,jI si cu semnificatia ca persoana i transmite persoanei j barfa sa, dar si toate barfele care i-au parvenit pana la momentul acestui mesaj.

Se cere una dintre cele mai scurte succesiuni de mesaje prin care toate persoanele afla toate barfele.

Cu enuntul de mai sus, o solutie este imediata si consta in succesiunea de mesaje: (1,2),(2,3),,(n-1,n),(n,n-1),(n-1,n-2),,(2,1)

Sunt transmit deci n-2 mesaje. Dupa cum vom vedea mai jos, acesta este numarul minim de mesaje prin care toate persoanele afla toate barfele.

Problema se complica daca exista persoane care nu comunica intre ele (sunt certate) si deci nu-si vor putea transmite una alteia mesaje.

Aceasta situatie poate fi modelata printr-un graf in care varfurile corespund persoanelor, iar muchiile leaga persoane care nu sunt certate intre ele. Vom folosi matricea de adiacenta a de ordin n in care a_ij este daca persoanele i si j sunt certate intre ele (nu exista muchie intre i si j) si in caz contrar.

Primul pas va consta in detectarea unui arbore partial; pentru aceasta vom folosi parcurgerea DF. Fiecarei persoane i ii vom atasa variabila booleana v_i, care este true daca si numai daca varful corespunzator a fost atins in timpul parcurgerii; initial toate aceste valori sunt false. Vom pune a_ij=2 pentru toate muchiile de inaintare.

v_i false, i=1,n

nr

DF(1)

if nr<n

then write('Problema nu are solutie (graf neconex)')

else rezolva problema pe arborele partial construit

unde procedura DF are forma cunoscuta:

procedure DF(i)

v_i true

for j=1,n

if a_ij=1 & not v_j

then a_ij 2; DF(j)

end

Sa observam ca in acest mod am redus problema de la un graf la un arbore! Descriem in continuare modul in care rezolvam problema pe acest arbore partial, bineinteles in ipoteza ca problema are solutie (graful este conex).

Printr-o parcurgere in postordine, in care vizitarea unui varf consta in transmiterea de mesaje de la fiii sai la el, radacina (presupusa a fi persoana 1) va ajunge sa cunoasca toate barfele. Aceasta se realizeaza prin apelul postord(1), unde procedura postord are forma:

procedure postord(i)

for j=1,n

if a_ij=2

then postord(j); write(j,i)

end

In continuare, printr-o parcurgere in preordine a arborelui DF, mesajele vor circula de la radacina catre frunze. Vizitarea unui varf consta in transmiterea de mesaje fiilor sai. Pentru aceasta executam apelul preord(1), unde procedura preord are forma:

procedure preord(i)

for j=1,n

if a_ij=2

then write(i,j); preord(j);

end

Observam ca atat la parcurgerea in postordine, cat si la cea in preordine au fost listate n-1 perechi (mesaje), deoarece un arbore cu n varfuri are n-1 muchii. Rezulta ca solutia de mai sus consta intr-o succesiune de 2n-2 mesaje. Mai ramane de demonstrat ca acesta este numarul minim posibil de mesaje care rezolva problema.

Propozitie. Orice solutie pentru problema barfei contine cel putin 2n-2 mesaje.

Sa consideram o solutie oarecare pentru problema barfei.

Punem in evidenta primul mesaj prin care o persoana a ajuns sa cunoasca toate barfele; fie k aceasta persoana. Deoarece celelate persoane trebuie sa le fi emis, inseamna ca pana acum au fost transmise cel putin n-1 mesaje. Dar k este prima persoana care a aflat toate barfele, deci celelalte trebuie sa mai afle cel putin o barfa. Rezulta ca in continuare trebuie sa apara inca cel putin n-1 mesaje. In concluzie, solutia considerata este formata din cel putin 2n-2 mesaje.

Parcurgerea BF a grafurilor neorientate

Fie un graf G=(V,M) si fie i₀ un varf al sau. In unele situatii se pune probleme determinarii varfului j cel mai apropiat de i₀ cu o anumita proprietate. Parcurgerea DF nu mai este adecvata.

Parcurgerea pe latime BF (Breadth First) urmareste vizitarea varfurilor in ordinea crescatoare a distantelor lor fata de i₀. Este generalizata parcurgerea pe niveluri a arborilor, tinandu-se cont ca graful poate contine cicluri. Va fi deci folosita o coada C

La fel ca si la parcurgerea DF, varfurile vizitate vor fi marcate.

Pentru exemplul din primul paragraf al acestui capitol, parcurgerea BF produce varfurile in urmatoarea ordine:

Algoritmul care urmeaza parcurge pe latime componenta conexa a lui i₀

for i=1,n

vizitat(i) false

C (i₀}; vizitat(i₀) true

while C ¹ Æ

i C; viziteaza i

for toti j vecini ai lui i

if not vizitat(j)

then vizitat(i) true; j Þ C

Programul Java corespunzator foloseste:

Clasa Vector

Un vector (obiect de tipul Vector) are lungime variabila si contine obiecte oarecare.

Vector() : constructor ce produce vectorul vid (de lungime 0);

void addElement(Object) : adauga obiectul la sfarsitul vectorului;

boolean removeElementAt(i) : elimina, cu deplasare la stanga, obiectul de pe pozitia i

boolean isEmpty() : verifica daca vectorul este vid;

Object firstElement() : intoarce primul element al vectorului. Obiectul intors trebuie convertit explicit la tipul sau real.

Clasa infasuratoare Integer permite sa asociem un obiect unui intreg si sa obtinem dintr-un astfel de obiect intregul asociat astfel:

Integer(int): constructor ce construieste obiectul asociat intregului respectiv;

int intValue(): intoarce intregul asociat obiectului.

Programul in Java este urmatorul:

import java.util.*;

class BF

class nivel

mat[i] = new int[ntemp];

for (int j=0; j<ntemp; j++) mat[i][j] = temp[j];

}

IO.writeln(' ** ** ');

}

void parc()

}

}

}

La fel ca pentru parcurgerea DF, algoritmul poate fi completat pentru parcurgerea intregului graf, pentru determinarea unei paduri in care fiecare arbore este un arbore partial al unei componente conexe etc.