java program to Design and implement the presence of Hamiltonian Cycle in an undirected Graph G of n vertices

				
					import java.util.*;
class Hamiltoniancycle
{
private int adj[][],x[],n;
public Hamiltoniancycle()
{
Scanner src = new Scanner(System.in);
System.out.println("Enter the number of nodes");
n=src.nextInt();
x=new int[n];
x[0]=0;
for (int i=1;i
x[i]=-1;
adj=new int[n][n];
System.out.println("Enter the adjacency matrix");
for (int i=0;i
for (int j=0; j
adj[i][j]=src.nextInt();
}
public void nextValue (int k)
{
int i=0;
while(true)
{ x[k]=x[k]+1;
if (x[k]==n)
x[k]=-1;
if (x[k]==-1)
return;
if (adj[x[k-1]][x[k]]==1)
for (i=0; i
if (x[i]==x[k])
break;
if (i==k)
if (k
return;
}}
public void getHCycle(int k)
{
while(true)
{
nextValue(k);
if (x[k]==-1)
return;
if (k==n-1)
{
System.out.println("\nSolution : ");
for (int i=0; i
System.out.print((x[i]+1)+" ");
System.out.println(1);
}
else getHCycle(k+1);

}}
}
class HamiltoniancycleExp
{
public static void main(String args[])
{
Hamiltoniancycle obj=new Hamiltoniancycle();
obj.getHCycle(1);
}
}

				
			
Output:
Enter the number of nodes
6
Enter the adjacency matrix
0 1 1 1 0 0
1 0 1 0 0 1
1 1 0 1 1 0
1 0 1 0 1 0
0 0 1 1 0 1
0 1 0 0 1 0
Solution :
1 2 6 5 3 4 1
Solution :
1 2 6 5 4 3 1
Solution :
1 3 2 6 5 4 1
Solution :
1 3 4 5 6 2 1
Solution :
1 4 3 5 6 2 1
Solution :
1 4 5 6 2 3 1

Leave a Reply