graf hamiltonian

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

#include<fstream.h>

int st[100],n,m,k,a[20][20];

int ns;

int e_valid()

{if(k>1)

if(!a[st[k-1]][st[k]])

return 0;

else

for(int i=1;i<=k-1;i++)

if(st[i]==st[k])

return 0;

if(k==n)

if(!a[st[1]][st[k]])

return 0;

return 1;

}

void afisare()

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

cout<<st[i]<<” “;

cout<<st[1];

k=0;

ns++;

}

void back()

{k=1;

while(k>0)

if(st[k]<n)

{st[k]++;

if(e_valid())

if(k==n)

afisare();

else

{k++;

st[k]=0;}

}

else

k–;

}

void main()

{

fstream f;

f.open(“hamiltonian.in”,ios::in);

int u,v;

if(f)

cout<<“ok!”;

else

cout<<“eroare”;

cout<<endl;

f>>n>>m;

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

{f>>u>>v;

a[u][v]=a[v][u]=1;

}

cout<<“matricea de adiacenta “<<endl;

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

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

cout<<a[i][j]<<” “;

cout<<endl;

}

back();

if(ns==0)

cout<<”nu exista solutii”;

}

{joscommentenable}

subgraf

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;
b[y][x]=1;
}
}

int subgraf()
{for(int i=1;i<=k;i++)
for(int j=1;j<=k;j++)
if(a[i][j]!=b[i][j]) return 0;
return 1;
}

void main()
{citire();
if(subgraf()) cout<<“da”;
else cout<<“nu”;
}

{joscommentenable}

roy floyd-grafuri orientate

#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 “
<<a[nodi][nodf]<<endl;
cout<<nodi<<” “;
drum(nodi,nodf);
}
else
cout<<“nu exista drum”;
}

void lungime()
{
int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if (a[i][j]>a[i][k]+a[k][j])
a[i][j]=a[i][k]+a[k][j];
}

void main()
{
citire(“ponderi.txt”,a,n);
lungime();
tipar(4,2);
getch();
}

{joscommentenable} 

parcurgere in latime bf recursiv

#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}