parcurgerea grafurilor

Conex

by

#437 Se dă lista muchiilor unui graf neorientat. Să se verifice dacă graful este sau nu conex. Date de intrare Fişierul de intrare conex.in conţine pe prima linie numărul n, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o pereche de numere i j, cu semnificația că există muchie între i … Read more

BFS

by

#19 Se consideră un graf neorientat cu n vârfuri și m muchii și de asemenea un vârf X. Cerinţa Să se afișeze vârfurile vizitate în urma parcurgerii în lățime (Breadth First Search) a grafului, pornind din vârful X. Date de intrare Fişierul de intrare BFS.in conţine pe prima linie trei numere naturale n m X, … Read more

DFS

by

#539 Se consideră un graf neorientat cu n vârfuri și m muchii și de asemenea un vârf X. Cerinţa Să se afișeze vârfurile vizitate în urma parcurgerii în adâncime (Depth First Search) a grafului, pornind din vârful X. Date de intrare Fişierul de intrare dfs.in conţine pe prima linie trei numere naturale n, m, X, … Read more

parcurgere in latime bf recursiv

by

#include<fstream.h>#include<conio.h>struct nod{int inf;nod* adr;}; nod* l[20];int c[20],s[20],i,sf,n; void citire(char fisier[20],nod* l[20],int& n){nod* p;int i,j;fstream f(fisier,ios::in);f>>n;for(i=1;i<=n;i++) l[i]=0;while(f>>i>>j){p=new nod;p->adr=l[i];p->inf=j;l[i]=p;}f.close();} void bf(){nod* p;if(i<=sf){p=l[c[i]];while(p){if(s[p->inf]==0){sf++;c[sf]=p->inf;s[p->inf]=1;}p=p->adr;}i++;bf();}} void main(){citire(“graf.txt”,l,n);i=1;sf=1;c[1]=1;s[1]=1;bf();for(int i=1;i<=sf;i++) cout<<c[i]<<” “;cout<<endl;getch();} {joscommentenable}