Parcurgerea in latime
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 nodurile a,b,..., adiacente lui varf, apoi cele adiacente lui a, cele adiacente lui b,... ,s.a.m.d.
Coada este folosita astfel:
- se pune primul nod in coada;
- se afla toate varfurile adiacente cu primul nod si se introduc dupa primul nod
- 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 nodurilor parcurse se va folosi un vector c[20] care va functiona ca o coada
-pentru a nu parcurge un nod de doua ori se va folosi un vector boolean viz[20] care va retine :
- viz[k]=0 daca nodul k nu a fost vizitat inca
- viz[k]=1 daca nodul 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 (nodurile 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 nodului varf se « cauta » pe linia acestui varf : daca a[varf][k]=1 inseamna ca nodurile varf si k sunt adiacente. Pentru ca nodul k sa fie adaugat in coada trebuie ca nodul sa nu fi fost vizitat : viz[k]=0
ALGORITMUL IN CODEBLOCKS C++:
#include<fstream>
#include <iostream>
using namespace std;
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++;
}
}
int main()
{
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]=a[y][x]=1;
}
cout<<"matricea de adiac "<<endl; // afisare matrice de adiacenta
for(int i=1;i<=n;i++)
{for(int j=1;j<=n;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
int nd;
prim=ultim=1;
cout<<"nodul de inceput=";
cin>>nd; // nodul de la care se porneste parcurgerea
viz[nd]=1;
c[prim]=nd;
bf_iterativ();
for(int i=1;i<=ultim;i++) //afisarea cozii
cout<<c[i]<<" ";
return 0;
}
--------------- Added after 2 minutes ---------------
Parcurgerea in adancime
-Graful se va memora utilizand matricea de adiacenta a[10][10]
-pentru a nu parcurge un nod de doua ori se va folosi un vector boolean vizcare va retine :
- viz[k]=0 daca nodul k nu a fost vizitat inca
- viz[k]=1 daca nodul k a fost vizitat
-ca si la parcurgerea in latime vecinii unui nod se « cauta » pe linia acestui nod : daca a[nod][k]=1 inseamna ca nodurile nod si k sunt adiacente. Pentru ca nodul k sa fie fie parcurs trebuie ca nodul sa nu fi fost vizitat : viz[k]=0
ALGORITMUL IN CODEBLOCKS C++ :
#include <fstream>
#include <iostream>
int a[20][20],n,m,viz[100],gasit;
void dfmr(int nod)
{
cout<<nod<<" ";
viz[nod]=1;
for(int k=1;k<=n;k++)
if(a[nod][k]==1&&viz[k]==0)
dfmr(k);
}
void main()
{
int x,y,j;
fstream f;
f.open("graf.txt",ios::in);
f>>n>>m;
for(int i=1;i<=m;i++)
{f>>x>>y;
a[x][y]=a[y][x]=1;}
cout<<endl<<"matricea de adiacenta"<<endl;
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
cout<<a[i][j]<<" ";
cout<<endl;}
cout<<endl<<"parcurgere in adancime incepand de la varful 1"<<endl;
dfmr(1);
return 0;
}