Extras din referat
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';
}
Conținut arhivă zip
- Parcurgerea Grafurilor Neorientate.ppt
Alții au mai descărcat și
Rezultatele din testul 3DS Max 7 SPECapc Test Testul alaturat consta in crearea modelelor 3D, modificarea si randarea scripturilor. Conform...
Introducere O semnatura digitala reprezinta o informatie care il identifica pe expeditorul unui document. Semnatura digitala este creata prin...
Caracteristici generale ale placii de baza Placa de baza este un dizpozitiv ‘de baza’ un ‘pamânt’ pe care ‘se planteaza’ celelalte componente ....
Acest sistem calculeaza gradul de avariere a unei cladiri în cazul unui cutremur, precum si posibila necesitate a reconstructiei cladirii (partiala...
Te-ar putea interesa și
Motivaţia lucrării Structurile de date reprezintă modalitatea în care datele sunt dispuse în memoria calculatorului(sau păstrate pe disc)....
1. Introducere 1.1 Ce este un algoritm?Tipuri de algoritmi folositi pentru calcularea drumului optim Scurt istoric: “Originile teoriei...
<<INTRODUCERE>> Procesele desfăşurate într-o activitate organizată nu au loc la întam-plare, ci sunt declanşate de anumite informaţii care...
GRAFURI NEORIENTATE NOTIUNI INTRODUCTIVE NOTIUNI DE BAZA DEFINITIE: Se numeste graf neorientat o pereche ordonata de multimi(X,U), X fiind o...
Grafuri neorientate Definiţie. Se numeşte graf neorientat o pereche ordonată de mulţimi (X, U), X fiind o mulţime finită şi nevidă de elemente...
I.METODA DIVIDE ET IMPERA 1.Notiuni introductive Asa cum spune si denumirea metodei (imparte si stapaneste), metoda se bazeaza pe impartirea unei...
8. Arbori 8.1. Arbori generalizaţi 8.1.1. Definiţii În definirea noţiunii de arbore se porneşte de la noţiunea de vector. Fie V o mulţime având...
Capitolul 1 INTRODUCERE Pentru noţiunile din acest paragraf am consultat Behzad, Chartrand, Foster, Croitoru, Olaru, Tomescu. Alte completări...