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}

Facebook Comments