Thursday, April 14, 2011

Hamiltonians Cycle


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...