Hamiltonian Cycle program in java

import java.io.*;
public class Hamiltonian
{
static boolean found = false;
public static void main(String args[]) throws IOException
{
DataInputStream in=new DataInputStream(System.in);
System.out.println("\t\t\t\tHamiltonian Cycle");
System.out.print("\nEnter the number of the vertices: ");
int n = Integer.parseInt(in.readLine());
int G[][] =new int[n+1][n+1];
int x[] =new int[n+1];
System.out.print("\nIf edge between the following vertices enter 1 else 0:\n");
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if((i!=j)&&(i<j))
{
System.out.print(i+" and "+j+": ");
G[j][i]=G[i][j] = Integer.parseInt(in.readLine());
}
if(i==j)
G[i][j]=0;
}
for(int i=1;i<=n;i++)
x[i] = 0;
x[1] = 1;
System.out.println("\nSolution:");

Hamiltonian (2,G,x,n);
if (found == false)
System.out.println("No Solution possible!");
}
static void Hamiltonian(int k,int G[][],int x[],int n)
{
while(true)
{
NextValue(k,G,x,n);
if(x[k] == 0)
return;
if(k == n)
{
for(int i=1; i<=k;i++)
System.out.print(x[i]+" ");
System.out.println();
found = true;
return;
}
else
Hamiltonian(k+1,G,x,n);
}
}
static void NextValue(int k,int G[][],int x[],int n)
{
while(true)
{
x[k] = (x[k]+1)%(n+1);
if(x[k] == 0)
return;
if(G[x[k-1]][x[k]] !=0)
{
int j;
for(j = 1; j<k; j++)
if(x[k] == x[j])
break;
if(j==k)
if( (k<n) || ( (k==n) && G[x[n]][x[1]] != 0 ) )
return;
}
}
}
}
/*
Hamiltonian Cycle program in java Output:

Enter the number of the vertices: 4

If edge between the following vertices enter 1 else 0:
1 and 2: 1
1 and 3: 1
1 and 4: 1
2 and 3: 1
2 and 4: 0
3 and 4: 1

Solution:
1 2 3 4
1 4 3 2
*/

Facing difficulties in understanding the program ?

Ask Your Queries in Comment Box

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *