Java Program to Implement Hamiltonian Cycle Algorithm

This is a Java Program to Implement Hamiltonian Cycle Algorithm. Hamiltonian cycle is a path in a graph that visits each vertex exactly once and back to starting vertex. This program is to determine if a given graph is a hamiltonian cycle or not. This program assumes every vertex of the graph to be a part of hamiltonian path.

Here is the source code of the Java Program to Implement Hamiltonian Cycle Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /**
  2.  **   Java Program to Implement Hamiltonian Cycle Algorithm
  3.  **/
  4.  
  5. import java.util.Scanner;
  6. import java.util.Arrays;
  7.  
  8. /** Class HamiltonianCycle **/
  9. public class HamiltonianCycle
  10. {
  11.     private int V, pathCount;
  12.     private int[] path;     
  13.     private int[][] graph;
  14.  
  15.     /** Function to find cycle **/
  16.     public void findHamiltonianCycle(int[][] g)
  17.     {
  18.         V = g.length;
  19.         path = new int[V];
  20.  
  21.         Arrays.fill(path, -1);
  22.         graph = g;        
  23.         try
  24.         {            
  25.             path[0] = 0;
  26.             pathCount = 1;            
  27.             solve(0);
  28.             System.out.println("No solution");
  29.         }
  30.         catch (Exception e)
  31.         {
  32.             System.out.println(e.getMessage());
  33.             display();
  34.         }
  35.     }
  36.     /** function to find paths recursively **/
  37.     public void solve(int vertex) throws Exception
  38.     {
  39.         /** solution **/
  40.         if (graph[vertex][0] == 1 && pathCount == V)
  41.             throw new Exception("Solution found");
  42.         /** all vertices selected but last vertex not linked to 0 **/
  43.         if (pathCount == V)
  44.             return;
  45.  
  46.         for (int v = 0; v < V; v++)
  47.         {
  48.             /** if connected **/
  49.             if (graph[vertex][v] == 1 )
  50.             {
  51.                 /** add to path **/            
  52.                 path[pathCount++] = v;    
  53.                 /** remove connection **/            
  54.                 graph[vertex][v] = 0;
  55.                 graph[v][vertex] = 0;
  56.  
  57.                 /** if vertex not already selected  solve recursively **/
  58.                 if (!isPresent(v))
  59.                     solve(v);
  60.  
  61.                 /** restore connection **/
  62.                 graph[vertex][v] = 1;
  63.                 graph[v][vertex] = 1;
  64.                 /** remove path **/
  65.                 path[--pathCount] = -1;                    
  66.             }
  67.         }
  68.     }    
  69.     /** function to check if path is already selected **/
  70.     public boolean isPresent(int v)
  71.     {
  72.         for (int i = 0; i < pathCount - 1; i++)
  73.             if (path[i] == v)
  74.                 return true;
  75.         return false;                
  76.     }
  77.     /** display solution **/
  78.     public void display()
  79.     {
  80.         System.out.print("\nPath : ");
  81.         for (int i = 0; i <= V; i++)
  82.             System.out.print(path[i % V] +" ");
  83.         System.out.println();
  84.     }    
  85.     /** Main function **/
  86.     public static void main (String[] args) 
  87.     {
  88.         Scanner scan = new Scanner(System.in);
  89.         System.out.println("HamiltonianCycle Algorithm Test\n");
  90.         /** Make an object of HamiltonianCycle class **/
  91.         HamiltonianCycle hc = new HamiltonianCycle();
  92.  
  93.         /** Accept number of vertices **/
  94.         System.out.println("Enter number of vertices\n");
  95.         int V = scan.nextInt();
  96.  
  97.         /** get graph **/
  98.         System.out.println("\nEnter matrix\n");
  99.         int[][] graph = new int[V][V];
  100.         for (int i = 0; i < V; i++)
  101.             for (int j = 0; j < V; j++)
  102.                 graph[i][j] = scan.nextInt();
  103.  
  104.         hc.findHamiltonianCycle(graph);        
  105.     }    
  106. }

HamiltonianCycle Algorithm Test
 
Enter number of vertices
 
8
 
Enter matrix
 
0 1 0 1 1 0 0 0
1 0 1 0 0 1 0 0
0 1 0 1 0 0 1 0
1 0 1 0 0 0 0 1
1 0 0 0 0 1 0 1
0 1 0 0 1 0 1 0
0 0 1 0 0 1 0 1
0 0 0 1 1 0 1 0
Solution found
 
Path : 0 1 2 3 7 6 5 4 0

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.