Informatica, Grafuri 11C

Arborele partial de cost minim poate fi construit muchie cu muchie, dupa urmatoarea metoda a lui Kruskal (1956): se alege intai muchia de cost minim, iar apoi se adauga repetat muchia de cost minim nealeasa anterior si care nu formeaza cu precedentele un ciclu. Alegem astfel X–1 muchii. Este usor de dedus ca obtinem in final un arbore. Este insa acesta chiar arborele partial de cost minim cautat?
Inainte de a raspunde la intrebare, sa consideram, de exemplu, graful din Figura 6.1.a. Ordonam crescator (in functie de cost) muchiile grafului: {1, 2}, {2, 3}, {4, 5}, {6, 7}, {1, 4}, {2, 5}, {4, 7}, {3, 5}, {2, 4}, {3, 6}, {5, 7}, {5, 6} si apoi aplicam algoritmul. Structura componentelor conexe este ilustrata, pentru fiecare pas, in Tabelul 1.

Figura 1 Un graf si arborele sau partial de cost minim.






Tabelul 1 Algoritmul lui Kruskal aplicat grafului din Figura1a.

Multimea A este initial vida si se completeaza pe parcurs cu muchii acceptate (care nu formeaza un ciclu cu muchiile deja existente in A). In final, multimea A va contine muchiile {1, 2}, {2, 3}, {4, 5}, {6, 7}, {1, 4}, {4, 7}. La fiecare pas, graful partial formeaza o padure de componente conexe, obtinuta din padurea precedenta unind doua componente. Fiecare componenta conexa este la randul ei un arbore partial de cost minim pentru varfurile pe care le conecteaza. Initial, fiecare varf formeaza o componenta conexa. La sfarsit, vom avea o singura componenta conexa, care este arborele partial de cost minim cautat (Figura 1b).Ceea ce am observat in acest caz particular este valabil si pentru cazul general.
In vectorul V vom sorta in ordine crescatoare numarul muchiilor in ordine crescatoare in functie de costul fiecareia.In vectorul X vom retine pentru fiecare nod numarul componenetei din care face parte acesta si care se schimba o data ce adaugam o noua muchie.Modificarea acestuia se face in functie de apartenenta uneia dintre extremitati la un arbore cu mai mult de un nod.In multimea B se retin numerele de ordine ale muchiilor ce apartin arborelui de cost minim.


procedure sortare; {se face sortarea intr-un vector v a muchiilor in ordine
var i,k,min:integer; crescatoare a costurilor muchiilor}
c:vector;
begin
c:=a;k:=0;
repeat
min:=maxint;
for i:=1 to m do
if (c[i].cost0) then
begin
min:=c[i].cost;
j:=i;
end;
inc(k);
v[k]:=j;
c[j].cost:=0;
until k=m;
end;
procedure kruskal;
var i,k,j:integer;
begin
k:=0;
for i:=1 to m do
begin
if (x[a[v[i]].vf1]=0) and (x[a[v[i]].vf2]=0) then {ambele extremitati
begin formeaza un arbore cu un singur nod}
b:=b+[v[i]];
inc(k);
x[a[v[i]].vf1]:=k;
x[a[v[i]].vf2]:=k;
end
else
if x[a[v[i]].vf1]<>x[a[v[i]].vf2] then {se verifica daca extremitatile
begin muchiei sunt din arbori diferiti}
b:=b+[v[i]];
if (x[a[v[i]].vf1]<>0) and (x[a[v[i]].vf2]<>0) then
begin
for j:=1 to n do
if (x[j]=x[a[v[i]].vf1]) and (a[v[i]].vf1<>j) then
x[j]:=x[a[v[i]].vf2];
x[a[v[i]].vf1]:=x[a[v[i]].vf2];
end;
if (x[a[v[i]].vf1]=0) then
x[a[v[i]].vf1]:=x[a[v[i]].vf2];
if (x[a[v[i]].vf2]=0) then
x[a[v[i]].vf2]:=x[a[v[i]].vf1];
end;
suma:=suma+a[v[i]].cost;
end;
end;
begin {main}
clrscr;
citire;
for i:=1 to m do
v[i]:=0;
sortare;
writeln('Vectorul sortat in ordinea muchiilor este:');
for i:=1 to m do
write(v[i],' ');
writeln;
for i:=1 to n do
x[i]:=0;
b:=[];
kruskal;
writeln('Muchiile arborelui sunt:');
suma:=0;
for i:=1 to m do
if i in b then
begin
writeln('Muchia ',i,':',a[i].vf1,' ',a[i].vf2,' de cost ',a[i].cost);
suma:=suma+a[i].cost;
end;
write('Costul arborelui este:',suma);
readkey;
end.

Scop:

Parcurgerea in latime se foloseste:
- pentru Inteligenta Artificiala (metoda neinformata de cautare... mai multe la cursul de IA);
- intr-o multime de aplicatii din teoria grafurilor (in special legate de drum minim de la un nod dat la un alt nod, componente conexe, grafuri bipartite);
- in jocuri pe calculator, pentru gasirea drumurilor, in special in jocuri Real Time Strategy (un mic exemplu in aplicatie);

Parcurgerea in adancime se foloseste:
- pentru Inteligenta Artificiala (metoda neinformata de cautare... mai multe la cursul de IA), insa combinarea sa cu euristici poate fi mai fructuoasa decat la parcurgerea in latime;
- sortarea topologica si alte aplicatii cu grafuri legate de componente conexe si tare conexe.


1. Parcurgerea in latime (Breadth First Search, BFS):

1.1. Teoria

Parcurgerea in latime foloseste o coada (Q) intr-un mod asemanator celui folosit de algoritmul AC-3. Initial in aceasta coada se gaseste doar nodul sursa. Vizitand pe rand vecinii sai ii adaugam si pe ei in coada. La sfarsit, dupa ce nu mai sunt vecini ai sursei nevizitati, scoatem nodul sursa din coada.


Pentru fiecare din nodurile prezente in coada, aplicam procedura de mai sus. Atentie insa: vizitand vecinii unui nod trebuie sa verificam ca acestia nu au mai fost deja vizitati (adica sunt inca albi).
. . .



In afara de coada q mai sunt necesare sau utile cateva structuri de date.
a) Putem diferentia intre nodurile nevizitate, cele asezate in coada si cele complet prelucrate printr-un vector denumit culoare:
c[nod] = alb, daca nodul nu a fost vizitat
gri, daca nodul a fost vizitat si asezat in q
negru, daca nodul a fost prelucrat si scos din q
b) Un vector d (distanta) care sa retina distanta (in numar de muchii) fata de sursa se poate dovedi util in unele probleme.
c) Vectorul de parinti p este necesar pentru a reface drumul de la sursa la un alt nod dupa parcurgere.


1.2. Algoritmul

Algoritmul conform specificatiilor de mai sus:

// =============== initializari ===================
pentru fiecare nod u
{
c[u] = alb;
d[u] = infinit;
p[u] = null;
}
c[sursa] = gri;
d[s] = 0;
q = {s};
// ================ algoritm ===================
cattimp (q nu este vida)
{
v = extrage nod din coada q;
pentru fiecare u dintre vecinii lui v
if (c[u] == alb)
{
c[u] = gri;
p[u] = v;
d[u] = d[v]+1;
insereaza in coada q (u);
}
c[v] = negru;
}

Obs: Pentru ca muchiile care unesc noduri deja gri nu sunt practic folosite, se intuieste asezarea muchiilor folosite intr-un graf conex si fara cicluri (adica un arbore):
Obs: Daca graful are mai multe componente conexe, algoritmul, in forma data aici, va parcurge doar componenta din care face parte nodul sursa. Pe grafuri alcatuite din mai multe componente conexe se vor obtine astfel mai multi arbori, cate unul pentru fiecare componenta.








2. Parcurgerea in adancime (Depth First Search, DFS):

2.1. Teoria:

DFS poate fi imaginata mai usor sub forma recursiva. Alegem un nod sursa. Dupa ce il marcam ca vizitat, consideram pe rand fiecare dintre vecinii sai ca fiind sursa. Muchiile catre noduri deja vizitate (inclusiv nodul original) practic nu vor conta (desi trebuiesc testate). In desenele de mai jos incerc sa simulez perspectiva nodului din pasul curent (observati cum acesta nu are acces la nodurile incetosate din cauza vecinilor deja vizitati):

Semnificatia culorilor ramane aceeasi ca la BFS:
- alb daca nodul nu a fost vizitat;
- gri daca nodul a fost vizitat dar nu i-am parcurs toti vecinii;
- negru daca am parcurs toti vecinii nodului.
Vom mai introduce doua variabile care se vor dovedi utile in unele aplicatii:
- tDesc (timpul descoperirii): pasul la care se marcheaza nodul cu gri;
- tFin (timpul final): pasul la care se marcheaza nodul cu negru.







2.2. Algoritmul:

Punand cap la cap informatiile de pana acum obtinem urmatorul algoritm:


// ================== initializari ====================
pentru fiecare nod u al grafului
{
culoare[u] = alb;
p[u] = NULL;
tDesc = 0;
tFin = 0;
}
timp = 0;

// === pentru a ne asigura ca se parcurg toate componentele conexe =
pentru fiecare nod al grafului
daca (culoare[nod] == alb)
PARCURGE(u);

// ==================== va parcurge o componenta conexa =======
PARCURGE(u)
{
culoare[u] = gri;
tDesc[u] = ++ timp;
pentru fiecare v vecin al lui u
{
daca (culoare[v] == alb)
{
p[v] = u;
PARCURGE[v];
}
}
culoare[u] = negru;
tFin[u] = ++timp;
}


Obs: Algoritmul este facut pentru a acoperi toate nodurile, chiar daca graful are mai multe componente conexe. Metoda PARCURGE corespunde acoperirii unei componente conexe.

Obs: Ganditi-va la asemanarile cu BKT. Daca am avea un arbore in care fiecare nod ar reprezenta asocierea unei variabile cu o valoare... si de la fiecare nod s-ar porni catre toate atribuirile posibile ale urmatoarei variabile... parca seamana, nu? Mai mult decat atat, si la DFS, ca si la BKT, ne putem intreba in ce ordine sa luam vecinii ca sa ajungem mai repede intr-un nod anume...






Obs.: Si la DFS, ca si la BFS, in urma parcurgerii se obtin arbori. Acestia se numesc arbori de adancime. Spre exemplu:

Evident, pe acest arbore s-ar putea adauga si muchiile pe care nu le-am folosit in parcurgere, dar l-ar face sa nu mai fie arbore. Totusi, in cazul grafurilor orientate, si aceste muchii au o semnificatie speciala.

Am transformat graful din exemplul precedent intr-unul orientat si i-am mai adaugat cateva noduri. Si de data asta i-am figurat toate muchiile. Acestea vor fi:
- muchii inainte: muchia (1,4);
- muchii inapoi: muchia (3,1);
- muchii de traversare: muchia (9,1).






2.3. Sortarea topologica:

Se da un graf orientat. Orientarea muchiilor corespunde unei relatii de ordine de la nodul sursa catre cel destinatie. Ni se cere sa asezam nodurile in asa fel incat pentru orice muchie (u,v), u sa apara inaintea lui v.
Sortarea topologica are sens numai daca este aplicata asupra unui graf orientat si aciclic. De ce? Daca nu ar fi graf orientat, nu am avea despre ce ordine sa discutam. Iar un ciclu ar fi indeajuns pentru a nu putea stabili o ordine intre nodurile care il alcatuiesc.
Sa consideram urmatorul exemplu:

Ei bine, de aici si pana la a obtine o succesiune de noduri ordonate nu este decat un singur pas: avem grija sa asezam nodul radacina al fiecarui subarbore intr-o stiva, iar pentru afisare scoatem pe rand cate un nod din stiva tiparind odata cu el si nodurile din arborele sau in ordinea obtinuta.

Obs: Pentru un graf dat pot exista mai multe insiruiri de noduri care sa respecte cerinta.

Convingeti-va ca solutia obtinuta este intr-adevar corecta si ca toate solutiile care se pot obtine prin aceasta metoda sunt si ele corecte.

Obs: Nu este singurul algoritm pentru sortare topologica.

Optional: Un alt algoritm pentru sortarea topologica:
Algoritmul urmator se aplica recursiv. La fiecare pas se elimina un nod in care nu intra nici o muchie, nod pe care il furnizam catre output. Prin eliminare se intelege implicit ca se elimina si muchiile adiacente nodului respectiv. Din moment ce nu erau muchii care sa intre in el, asta inseamna ca se elimina muchiile care pornesc din el.
Daca la un moment dat mai avem noduri si nu mai putem face eliminare, inseamna ca exista un ciclu in graf si nu exista sortare topologica pentru el.


3. Rezumat:

Parcurgerea in latime (BFS) foloseste o coada pentru a putea vizita toti vecinii unui nod dat inainte de a-l marca drept prelucrat. Se poate folosi inclusiv pentru determinarea drumurilor de lungime minima si returneaza cate un arbore pentru fiecare componenta conexa.
Are complexitatea O(E+V).

Parcurgerea in adancime (DFS) se poate implementa intuitiv in forma recursiva, iar principiul sau de functionare sta la baza BKT. DFS se foloseste in sortarea topologica si furnizeaza unul sau mai multi arbori de adancime. De o utilitate interesanta sunt timpii de descoperire si de finalizare a prelucrarii unui nod in cadrul operatiei de parcurgere.
Are complexitatea Θ(E+V).
Complexitatea spatiala este mai buna decat la BFS.

Notiuni introductive

     O categorie importanta de grafuri este aceea in care muchiile sun niste legaturi de tip parinte-fiu. Un astfel de graf se va numi ARBORE. 

Definitie 

 -Se numeste arbore un graf conex si fara cicluri.
 -Un arbore cu n varfuri are n-1 muchii.

Proprietati caracteristice unui arbore 

• Exista un nod in care nu intra nici un arc numit radacina arborelui.
• Cu exceptia radacinii, fiecare nod are proprietatea ca in el intra un singur arc.
Acesta leaga nodul respectiv de un alt nod numit numit predecesor sau parinte.
• Dintr-un nod pot iesi unul sau mai multe arce.Fiecare astfel de arc,leaga nodul
Respectivd de un alt nod numit Succesor sau fiu al nodului.
* Nodurile sunt organizate pe nivele primul nivel fiind ocupat de nodul radacina.
Nodurile de pe ultim nivel se caracterizeaza prin faptul ca din ele nu mai iese nici un arc ,si se numesc noduri terminale sau frunze.

• Nodurile pot contine o asa informatie utila ,carte poate fi de orice tip.\

Exemplu

Nodul  1  este radacina arborelui.

Frunzele arborelui sunt:  3,8,9.

     

     Algoritmul Prim (scris în 1957 si implementat în 1961 de catre Dijkstra) elimina acest neajuns. Se opereaza cu datele din acelasi graf. Se porneste initial, ca si în algoritmul lui Kruskal cu “n” vârfuri izolati (adica de la cele “n” varfuri, dar fara a fi trasat între aceste vârfuri vre-o muchie), urmând ca pe parcurs aceste vârfuri sa fie legate între ele de arborele cu lungimea minima.

1.Reprezentarea grafurilor cu ajutorul matricei de adiacenta.

Se citesc n, numarul nodurilor, si m, numarul muchiilor unui graf, de la tastatura. Se citesc, de asemenea, pe rand, m perechi de numere cu valori cuprinse intre 1 si n,reprezentand muchiile grafului.Sa se memoreze graful cu ajutorul matricei de adiacenta si sa se afiseze matricea .

#include

#define max 10

void citire(int &n, int a[max][max]);

void afisare(int n, int a[max][max]);

void initializare(int a[max][max]);

void main()

{int a[max][max], n; //a-matricea de adiacenta,n-nr noduri

initializare(a) ;

citire(n,a) ;

afisare(n,a);

}

void initializare(int a[max][max]) // initializarea matricei

{int i,j;

for(i=0;i

for(j=0;j

a[i][j]=0;

}

void citire(int &n, int a[max][max]) //construirea matricei de adiacenta

{int x,y,i,m;

cout<< ‘‘n=’’ ;cin>>n ;

cout<< ‘‘m=’’ ;cin>>m ; // m-nr muchii

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

{cout<< “muchia”<

cin>>x>>y;

a[x][y]=1;

a[y][x]=1; //construim matricea simetrica

}

}

void afisare(int n, int a[max][max]) //afisarea matricei de adiacenta

{int i,j ;

cout<<’’Matricea de adiacenta :’’<

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

{for(j=1 ;j<=n ;j++)

cout<

cout<

}

}

2.Reprezentarea grafului cu ajutorul listelor de adiacenta .

#include

#define max 10

void citire(int &n, int l[max][max]);

void afisare(int n, int l[max][max]);

void initializare(int l[max][max]);

void main()

{int a[max][max], n; //l-matricea de adiacenta,n-nr noduri

initializare(l) ;

citire(n,l) ;

afisare(n,l);

}

void initializare(int l[max][max])

{int i,j;

for(i=0;i

for(j=0;j

a[i][j]=0;

}

void citire(int &n, int l[max][max])

{int x,y,i,m;

cout<< ‘‘n=’’ ;cin>>n ; //n-nr nodurilor

cout<< ‘‘m=’’ ;cin>>m ; // m-nr muchii

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

{cout<< “muchia”<

cin>>x>>y; //citim doua noduri adiacente

i[x][0]++; //indicele de sfarsit a l listei nodului x

i[y]l[x][0]]=y; //element in lista nodului x

i[y][0]++ ; //indicele de sfarsit al listei nodului y

i[y][1[y][0]]=x ; //element in lista nodului x

}

}

void afisare(int n, int l[max][max])

{int i,j ;

cout<<’’Matricea de adiacenta :’’<

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

{cout<<’’nodul’’<

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

cout<

cout<

}

}

3.Reprezentarea grafurilor in memorie folosind lista muchiilor.

#include

#define max 10

Struct muchie //structura pentru memorarea unei muchii

{intx,y;

};

Muchie e[max]; //vectorul de muchii

int n,m ;

void citire() ;

void afisare() ;

void main()

{citire() ;

afisare() ;

}

void citire()

{int x,y,i ;

cout<<’’n=’’;cin>>n;

cout<<’’m=’’ ;cin>>m ; //m-nr muchii

for(j=1;i<=m;j++)

{cout<<’’muchia’’<<<’’:’’;

cin>>x>>y;

e[i].x=x //memoreaza un capat al muchiei

e[i].y=y //memoreaza al doilea capat al muchiei

}

}

void afisare()

{int i,j;

cout<<’’Graful are’’<

cout<<’’Muchiile grafului:”<

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

cout<

}