grafuri

graf hamiltonian

by

Sa se verifice daca un graf este hamiltonian Fiind dat un graf neorientat memorat prin matricea de adiacenta sa se determine daca graful este Hamiltonian sau nu. Notiuni teoretice Definitie: Se numeste ciclu hamiltonian un ciclu elementar care trece prin toate varfurile grafului Definitie: Un graf care admite un ciclu hamiltonian se numeste graf hamiltonian … Read more

subgraf

by

Subgraf Se citesc 2 grafuri neorientate, unul cu n noduri si m muchii, iar celalalt cu k varfuri si l muchii, ambele date prin vectorul muchiilor. Sa se determine daca al doilea graf este subgraf al primului. #include<fstream.h>fstream f(“date.in”,ios::in);fstream g(“date2.in”,ios::in); int a[100][100],b[100][100],n,m,k,l;void citire() {int x,y,i; f>>n>>m; for(i=1;i<=m;i++) {f>>x>>y; a[x][y]=1; a[y][z]=1; } g>>k>>l; for(i=1;i<=l;i++) {g>>x>>y; b[x][y]=1; … Read more

roy floyd-grafuri orientate

by

#include<fstream.h>#include<conio.h>const float pinf=1.e20;float a[50][50];int n; void citire(char nume[20],float a[50][50],int& n){int i,j;float c;fstream f(nume,ios::in);f>>n;for(i=1;i<=n;i++) for(j=1;j<=n;j++) if (i==j) a[i][j]=0; else a[i][j]=pinf;while(f>>i>>j>>c) a[i][j]=c;f.close();} void drum(int i,int j){int k=1,gasit=0;while ((k<=n) && !gasit){ if ((i!=k) && (j!=k) && (a[i][j]==a[i][k]+a[k][j])) { drum(i,k);drum(k,j); gasit=1; } k++;}if (!gasit) cout<<j<<” “;} void tipar(int nodi,int nodf){if (a[nodi][nodf]<pinf){ cout<<“drumul de la “<<nodi<<” la “<<nodf<<” are lungimea … 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}