Parcurgerea grafurilor în adâncime
Foarte mulţi algoritmi de prelucrare a grafurilor necesită examinarea tuturor nodurilor unui graf.Pentru aceasta este necesară definirea unei strategii de traversare a grafului.Se poate vorbi în principal de două tehnici de traversare:
– în adâncime (Depth First)
– în lăţime (Breadth First)
În explicarea modului de funcţionare a primei variante se foloseşte un şir de întregi, VIZITAT, de lungime n cu ajutorul căruia se marchează nodurile deja “vizitate” pentru a evita trecerea de mai multe ori prin acelaşi nod.Cu alte cuvinte VIZITAT[j] = 1 dacă nodul j a fost deja atins şi VIZITAT[j] = 0 în caz contrar.Vom spune despre un nod i că a fost explorat dacă are toate nodurile adiacente vizitate.
Procedura recursivă care asigură parcurgerea unui graf în adâncime începând cu un anumit vârf i:
Procedura Parcurgere_în_adâncime(i)
pentru toate vârfurile k adiacente cu vârful i execută
daca vârful k este neparcurs
atunci se parcurge vârful k
apel parcurgere_în_adâncime(k)
Ieşirea din recursivitate se produce în momentul în care nu se mai găsesc vârfuri neparcurse adiacente cu vârfurile parcurse deja. Este posibil ca după un apel al procedurii incepând cu un anumit vârf i să rămână în graf vârfuri neparcurse.În această situaţie apelul procedurii se repetă pentru un alt vârf iniţial (dintre vârfurile neparcurse) până la parcurgerea tuturor nodurilor grafului. Programul apelant trebuie să asigure parcurgerea vârfului utilizat în apel.Condiţiile interne care apar în problemele particulare de backtracking pot impune o parcurgere integrală sau numai parţială a grafului.Procedura backtracking(i) este pentru cazul parcurgerii integrale a unui graf în adâncime:
Procedura Backtracking(i)
pentru toate vârfurile k adiacente cu vârful i execută
daca vârful k este neparcurs şi sunt îndeplinite condiţiile de continuare
atunci se parcurge vârful k
se utilizeaza vârful k în soluţie
dacă s-a ajuns la o soluţie se afişează
apel Backtracking(k)
Folosind această tehnică de traversare ne propunem să răspundem la întrebarea:
Fiind dat un graf neorientat G=(V,E), este acesta un graf conex?
Conform acestei metode explorarea unui nod este suspendată ori de câte ori un nou vârf este vizitat.Pentru graful G daca pornim din vârful 1, vizitarea nodurilor se va face în ordinea: 1,2,4,8,5,6,3,7.
Următoarea funcţie returnează true dacă graful este conex şi false în caz contrar folosind tehnica parcurgerii în adâncime:
Function Conex: boolean;
Procedura adâncime(s) {parcurge graful in adancime}
VIZITAT[s]:=1;
pentru fiecare nod w adiacent cu s execută
dacă VIZITAT[w] = 0 atunci apel adâncime(w)
sfârşit dacă;
sfârşit pentru;
sfârşit procedura;
pentru toate nodurile w execută
VIZITAT[w]:=0;
sfârşit pentru;
apel adâncime(1);
Conex:=true;
pentru toate nodurile w execută
dacă VIZITAT[w] = 0 atunci
conex:=false;
sfârşit dacă;
sfârşit pentru;
Sfârşit funcţie;
Parcurgerea grafurilor in latime
Rezolvarea multor probleme de grafuri, presupune parcurgerea lor de la un anumit nod. Pentru explorarea grafurilor, exista doua tipuri de algoritmi: de explorarea in latime si de explorare in adancime. Parcurgerea grafurilor orientate este similara cu a grafurilor neorientate, se tine cont insa de orientare.
Explorarea grafurilor in latime
La explorarea in latime, dupa vizitarea varfului initial, se exploreaza toate varfurile adiacente lui, se trece apoi la primul varf adiacent si se exploreaza toate varfurile adiacente acestuia si neparcurse inca, s.a.m.d.
Fiecare varf se parcurge cel mult odata.
De exemplul pentru garful din figura de mai jos, se va proceda in felul urmator:
se porneste din nodul 1, (se poate incepe de la oricare alt nod)
se exploreaza in vontinuare vecinii acestuia : nodul 2 si apoi 4,
se obtine 1,2,4
dupa care din 2 se exploreaza nodul adiacent acestuia 3. Nodul 1 nu se mai viziteaza odata
se obtine 1,2,4,3
In continuare ar trebui parcursi vecinii lui 4 (1,2,4,3 ) dar acesta nu mai are vecini nevizitati si se trece la vecinii lui 3 : 1,2,4,3 respectiv nodul 5 :
se obtine 1, 2, 4, 3, 5
Varful 6 ramane neparcurs
Daca se parcurge graful incepand de la varful 2, solutia este : 2,3,4,5, in timp ce parcurgerea incepand cu 4 va retine doar varful 4
Algoritmul
Se va folosi o coada in care se inscriu nodurile in forma in care sunt parcurse: nodul initial varf (de la care se porneste), apoi varfurilr a,b,…, adiacente lui varf, apoi cele adiacente lui a, cele adiacente lui b,… ,s.a.m.d.
Coada este folosita astfel:
– se incarca primul varf in coada;
– se afla toate varfurile adiacente cu primul nod si se introduc dupa primul varf
– se ia urmatorul nod si i se afla nodurile adiacente
– procesul se repeta pana cand se ajunge la sfarsitul cozii
-Graful se va memora utilizand matricea de adiacenta a[10][10]
-pentru memorarea succesiunii varfurilor parcurse se va folosi un vector c[20] care va functiona ca o coada
-pentru a nu parcurge un varf de doua ori se va folosi un vector boolean viz[20] care va retine :
– viz[k]=0 daca varful k nu a fost vizitat inca
– viz[k]=1 daca varful k a fost vizitat
-doua variabile : prim si ultim vor retine doua pozitii din vectorul c si anume :
– prim este indicele componentei pentru care se parcurg vecinii (indexul componentelor marcate cu rosu in sirurile parcurse anterior ). Prin urmare Varf=c[prim], este elementul pentru care se determina vecinii (varfurile adiacente)
-ultim este pozitia in vector pe care se va face o noua inserare in vectorul c (evident, de fiecare data cand se realizeaza o noua inserare se mareste vectorul)
-vecinii unui varf se « cauta » pe linia acestui varf : daca a[varf][k]=1 inseamna ca varf si k sunt adiacente. Pentru ca varful k sa fie adaugat in coada trebuie ca varful sa nu fi fost vizitat : viz[k]=0
#include<fstream.h>
#include<conio.h>
int a[10][10],c[20],viz[10];
int n,m,prim,ultim,varf;
void bf_iterativ() //parcurgerea in latime
{int k;
while(prim<=ultim)
{varf=c[prim];
for(k=1;k<=n;k++)
if(a[varf][k]==1&&viz[k]==0) //il adaug pe k in coada daca este vecin pt. varf si nu a fost vizitat
{ultim++;
c[ultim]=k;
viz[k]=1;}
prim++;
}
}
void main()
{clrscr();
int x,y;
fstream f; //memorare graf in matrice de adiacenta
f.open(„muchii.txt”,ios::in);
f>>n>>m;
for(int i=1;i<=m;i++)
{f>>x>>y;
a[x][y]=1;
}
cout<<„matricea de adiac „<<endl; // afisare matrice de adiacenta
for( i=1;i<=n;i++)
{for(int j=1;j<=n;j++)
cout<<a[i][j]<<” „;
cout<<endl;
}
int nd;
prim=ultim=1;
cout<<„varful de inceput=”;
cin>>nd; // varful de la care se porneste parcurgerea
viz[nd]=1;
c[prim]=nd;
bf_iterativ();
for(i=1;i<=ultim;i++) //afisarea cozii
cout<<c[i]<<” „;
getch();
}
Varianta recursiva de parcurgere se obtine modificand functia de parcurgere iterativa adaugand conditia necesara autoapelului:
void bf_recursiv() //parcurgerea in latime
{int k;
if(prim<=ultim)
{varf=c[prim];
for(k=1;k<=n;k++)
if(a[varf][k]==1&&viz[k]==0) //il adaug pe k in coada daca este vecin pt. varf si nu a fost vizitat
{ultim++;
c[ultim]=k;
viz[k]=1;}
prim++;
bf_recursiv();
}
}
Parcurgerea in latime a grafurilor memorate prin liste este similara cu diferenta cavecinii unui nod adaugat in coada se cauta in lista corespunzatoare lui :
#include<conio.h>
#include<fstream.h>
struct nod
{int nd;
nod *next;};
nod *L[20];
int viz[100]; //marchez cu 1 nodurile vizitate
int m,n;
int prim,ultim,C[100];
void bfi_lis()
{int varf,nr;
nod *p;
while(prim<=ultim)
{varf=C[prim];
p=L[varf]; // se parcurge lista elementelor din varful cozii
while(p)
{nr=p->nd;
if(viz[nr]==0) //numai daca nu a fost vizitat
{ultim++; //maresc coada
C[ultim]=nr; //il adaug in coada
viz[nr]=1;}; //il marchez ca fiind vizitat
p=p->next;
}
prim++; //avansez la urmatorul varf din coada
}
}
void afisare(int nr_nod)
{nod *p=L[nr_nod];
if(p==0)
cout<<nr_nod<<” este izolat „<<endl;
else
{cout<<„lista vecinilor lui „<<nr_nod<<endl;
nod *c=p;
while(c)
{cout<<c->nd<<” „;
c=c->next;}
cout<<endl;}
}
void main()
{fstream f;
int i,j;
nod *p,*q;
f.open(„muchii.txt”,ios::in);
clrscr();
f>>n>>m;
while(f>>i>>j)
{p=new nod;
p->nd=j;
p->next=L[i];
L[i]=p;
}
f.close();
cout<<endl<<„listele de adiacente „;
for(i=1;i<=n;i++)
afisare(i);
int ndr;
cout<<endl<<„nodul de inceput „;
cin>>ndr;
viz[ndr]=1;
prim=ultim=1;
C[prim]=ndr;
cout<<endl<<„parcurgere in latime „<<endl;
bfi_lis();
for(i=1;i<=ultim;i++)
cout<<C[i]<<” „;
getch();
}
Functia recursiva :
void bfr_lis()
{int varf,nr;
nod *p;
if(prim<=ultim)
{varf=C[prim];
p=L[varf];// se parcurge lista elementelor din varful cozii
while(p)
{nr=p->nd;
if(viz[nr]==0)//numai daca nu a fost vizitat
{ultim++;//maresc coada
C[ultim]=nr;//il adaug in coada
viz[nr]=1;};//il marchez ca fiind vizitat
p=p->next;}
prim++; //avansez la urmatorul nod din coada
bfr_lis();
}
}
Probleme rezolvate
Se citeste din fisierul “graf.in” de pe prima linie numarul de noduri de pe urmatoarele n linii matricea de adiacenta.
a) Sa se determine gradul fiecarui nod
Rezolvare:
#include<iostream.h>
#include<fstream.h>
ifstream f(“graf.in”)
int a[20][20],n;
void grad()
{ int i,j,s;
for(i=1;i<=n;i++)
{s=0;
for(j=1;j<=n;j++)
s=s+a[i][j];
cout<<”grad nod”<<i<<s<<endl;
}
}
int main()
{f>>n;
int i,j ;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
f>>a[i][j];
grad();
f.close()
}
Aplicatii :
1.Sa se parcurga graful in latime pornind pe rand de la toate varfurile
2. Sa se determine daca pornind de la nodul x se poate ajunge la nodul y
3. Sa se determine daca se poate parcurge pornind de la un nod tot graful
4. . Se consideră un graf neorientat exprimat prin intermediul unei matrici de adiacenţă (analog
cu cel din problema anterioară).
a) Scrieţi un program care calculează gradul fiecărui nod din graf, sortează descrescator şi
afişează nodurile şi gradele aferente.
b) Scrieţi un program care determină câte noduri sunt izolate în graf şi afişează toate
aceste noduri.
c) Să se construiască şi să se afişeze pentru fiecare nod din graf lista de adiacenţă
definită dinamic.
d) Să se verifice dacă o secvenţă de noduri citită de la tastatură (încheiată cu -1) formează
un lanţ în graf.
e) Să se verifice dacă o secvenţă de noduri citită de la tastatură (încheiată cu -1) formează
un ciclu în graf.
f) Scrieţi un program care să verifice dacă un graf este conex. Dacă graful nu este conex să
se determine (și afișeze) componentele conexe ale grafului.
g) Scrieţi un program care să verifice dacă un graf este eulerian1
.
h) Scrieţi un program care să verifice dacă un graf este regulat.
i) Scrieţi un program care să verifice dacă un graf este complet.
j) Realizați un o funcție care verifică dacă într-un graf neorientat, memorat cu ajutorul
matricei de adiacență există un ciclu elementar de lungime k (unde k este citit de la
tastatură). Graful conține n noduri (n≤25). Matricea de adiacență și numărul de noduri din
graf vor fi primite de subprogram prin intermediul parametrilor. Funcția va întoarce 1 în
caz afirmativ și 0, în caz contrar
informatica.cnet 