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

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
I’m Manish - Founder and CTO at Sanfoundry. I’ve been working in tech for over 25 years, with deep focus on Linux kernel, SAN technologies, Advanced C, Full Stack and Scalable website designs.

You can connect with me on LinkedIn, watch my Youtube Masterclasses, or join my Telegram tech discussions.

If you’re in your 40s–60s and exploring new directions in your career, I also offer mentoring. Learn more here.