import java.io.*;
class Hamilton
{
void Nextvalue(int k,int n,int g[][],int x[])
{
int j;
do
{
x[k]=(x[k]+1)%(n+1);
if(x[k]==0)
return;
if(g[x[k-1]][x[k]]!=0)
{
for(j=1;j<=k-1;j++)
{
if(x[j]==x[k])
break;
}
if(j==k)
{
if((k<n)||((k==n)&&(g[x[n]][x[1]]!=0)))
return;
}
}
}
while(true);
}
void Hamilt(int k,int n,int count,int x[],int g[][])
{
int i;
while(true)
{
Nextvalue(k,n,g,x);
if(x[k]==0)
{
return;
}
if(k==n)
{
System.out.println("Hamiltonian Cycle"+((count++)+1));
for(i=1;i<=n;i++)
System.out.println(x[i]+" ");
System.out.println(x[1]);
}
else
Hamilt(k+1,n,count,x,g);
}
}
}
class Hamiltonian
{
public static void main(String args[]) throws IOException
{
int i,j,v1,v2;
int x[]=new int[20];
int g[][]=new int[20][20];
int count=0;
DataInputStream d = new DataInputStream(System.in);
Hamilton h= new Hamilton();
System.out.println("Enter the vertices of graph");
int n=Integer.valueOf(d.readLine()).intValue();
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
g[i][j]=0;
}
System.out.println("Enter the no. of edges");
int ed=Integer.valueOf(d.readLine()).intValue();
for(i=1;i<=ed;i++)
{
System.out.println("Enter the edge");
v1=Integer.valueOf(d.readLine()).intValue();
v2=Integer.valueOf(d.readLine()).intValue();
g[v1][v2]=1;
g[v2][v1]=1;
}
for(i=1;i<=n;i++)
x[i]=0;
x[1]=1;
h.Hamilt(2,n,count,x,g);
if(count==0)
System.out.println("No hamiltonian cycles exist");
}
}
Output:
Enter the vertices of graph
8
Enter the no. of edges
11
Enter the edge
1
2
Enter the edge
1
3
Enter the edge
1
7
Enter the edge
2
3
Enter the edge
2
8
Enter the edge
3
4
Enter the edge
3
6
Enter the edge
4
5
Enter the edge
5
6
Enter the edge
6
7
Enter the edge
7
8
Hamiltonian Cycle1
1
2
8
7
6
5
4
3
1
Hamiltonian Cycle1
1
3
4
5
6
7
8
2
1
Press any key to continue...
No comments:
Post a Comment