Parcurgerea Grafurilor Neorientate

Imagine preview
(6/10 din 1 vot)

Acest referat descrie Parcurgerea Grafurilor Neorientate.
Mai jos poate fi vizualizat un extras din document (aprox. 2 pagini).

Arhiva contine 1 fisier ppt de 12 pagini .

Profesor indrumator / Prezentat Profesorului: Arnautu V

Iti recomandam sa te uiti bine pe extras iar daca este ceea ce-ti trebuie pentru documentarea ta, il poti descarca. Ai nevoie de doar 4 puncte.

Domeniu: Calculatoare

Extras din document

Obiective

Notiuni teoretice despre parcurgeri (semnificatie, mod de realizare, scop);

Metode de parcurgere;

Parcurgerea în “latime” (prezentarea metodei, exemple);

Algoritmul BF.

Parcurgere (notiuni teoretice)

Semnificatie: examinarea în mod sistematic a nodurilor unui graf;

Realizare: se pleaca dintr-un nod dat i, astfel încât fiecare nod accesibil din i pe muchii incidente doua câte doua, sa fie atins o singura data.

Alte expresii similare: vizitare, traversare.

Scop:

prelucrarii informatiilor asociate nodurilor;

determinarea aranjarii lineare a nodurilor în vederea trecerii de la unul la altul

Observatii:

Presupunem ca multimea vârfurilor este X={1, 2, … , n};

Presupunem ca ordinea vârfurilor este data de relatia „<”, existenta în multimea numerelor naturale.

Metode de parcurgere

Parcurgere în „latime” (Breadth First - BF)

Parcurgerea în „adâncime” (Depth First - DF)

Parcurgerea în „latime” Breadth First - BF

#include <iostream.h>

void main (void)

{

int a[20][20],trecut[20],n,i,j,u,pc, m,e1,e2,x,sol[20];

cout<<"numarul de noduri: ";

cin>>n;

cout<<"numarul de muchii: ";

cin>>m;

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

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

a[i][j]=0;

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

{

cout<<"Muchia "<<i<<":n";

cout<<"e1=";

cin>>e1;

cout<<"e2=";

cin>>e2;

a[e1][e2]=a[e2][e1]=1;

}

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

trecut[i]=0;

cout<<"Nodul initial: ";

cin>>x;

pc=1;

u=1;

sol[1]=x;

trecut[x]=1;

while (u<n)

{

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

if (a[sol[pc]][i] && !trecut[i])

{

u++;

sol[u]=i;

trecut[i]=1;

}

pc++;

}

cout<<"Parcurgerea BFS:";

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

cout<<sol[i]<<',';

cout<<'b';

}

Fisiere in arhiva (1):

  • Parcurgerea Grafurilor Neorientate.ppt