Java Program to Check if a Given Graph must Contain Hamiltonian Cycle or Not

This is a java program to check if the graph contains any Hamiltonian cycle. In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian path that is a cycle. Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem, which is NP-complete.

Here is the source code of the Java Program to Check if a Given Graph Contain Hamiltonian Cycle or Not. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

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

Output:

$ javac CheckHamiltonianCycle.java
$ java CheckHamiltonianCycle
 
Enter number of vertices
6
Enter adjacency matrix
0 1 0 0 0 0
1 0 1 1 0 0
0 1 0 0 0 1 
0 1 0 0 1 1
0 0 0 1 0 1
0 0 1 1 1 0
No solution

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

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.