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.
package com.maixuanviet.hardgraph; import java.util.Arrays; import java.util.Scanner; public class CheckHamiltonianCycle { private int V, pathCount; private int[] path; private int[][] graph; /** Function to find cycle **/ public void findHamiltonianCycle(int[][] g) { V = g.length; path = new int[V]; Arrays.fill(path, -1); graph = g; try { path[0] = 0; pathCount = 1; solve(0); System.out.println("No solution"); } catch (Exception e) { System.out.println(e.getMessage()); display(); } } /** function to find paths recursively **/ public void solve(int vertex) throws Exception { /** solution **/ if (graph[vertex][0] == 1 && pathCount == V) throw new Exception("Solution found"); /** all vertices selected but last vertex not linked to 0 **/ if (pathCount == V) return; for (int v = 0; v < V; v++) { /** if connected **/ if (graph[vertex][v] == 1) { /** add to path **/ path[pathCount++] = v; /** remove connection **/ graph[vertex][v] = 0; graph[v][vertex] = 0; /** if vertex not already selected solve recursively **/ if (!isPresent(v)) solve(v); /** restore connection **/ graph[vertex][v] = 1; graph[v][vertex] = 1; /** remove path **/ path[--pathCount] = -1; } } } /** function to check if path is already selected **/ public boolean isPresent(int v) { for (int i = 0; i < pathCount - 1; i++) if (path[i] == v) return true; return false; } /** display solution **/ public void display() { System.out.print("\nPath : "); for (int i = 0; i <= V; i++) System.out.print(path[i % V] + " "); System.out.println(); } /** Main function **/ public static void main(String[] args) { Scanner scan = new Scanner(System.in); /** Make an object of HamiltonianCycle class **/ CheckHamiltonianCycle hc = new CheckHamiltonianCycle(); /** Accept number of vertices **/ System.out.println("Enter number of vertices"); int V = scan.nextInt(); /** get graph **/ System.out.println("Enter adjacency matrix"); int[][] graph = new int[V][V]; for (int i = 0; i < V; i++) for (int j = 0; j < V; j++) graph[i][j] = scan.nextInt(); hc.findHamiltonianCycle(graph); scan.close(); } }
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
Related posts:
Apache Tiles Integration with Spring MVC
Java Program to Find k Numbers Closest to Median of S, Where S is a Set of n Numbers
Removing all duplicates from a List in Java
A Guide to LinkedHashMap in Java
Spring Boot Gradle Plugin
Java Program to Perform Right Rotation on a Binary Search Tree
Java Program to Perform Left Rotation on a Binary Search Tree
Convert String to Byte Array and Reverse in Java
Spring @RequestMapping New Shortcut Annotations
REST Pagination in Spring
Working With Maps Using Streams
Java Program to Implement Self Balancing Binary Search Tree
Giới thiệu Java 8
Comparing Long Values in Java
ClassNotFoundException vs NoClassDefFoundError
Spring Boot - Build Systems
Java Program to find the number of occurrences of a given number using Binary Search approach
Spring Boot - Web Socket
Java Program to Implement Sparse Array
Add Multiple Items to an Java ArrayList
Java Program to Perform Stooge Sort
Java Program to Implement LinkedBlockingDeque API
Java Program to Search Number Using Divide and Conquer with the Aid of Fibonacci Numbers
Hướng dẫn sử dụng luồng vào ra nhị phân trong Java
Object Type Casting in Java
JWT – Token-based Authentication trong Jersey 2.x
Java Program to Implement the Hill Cypher
Test a REST API with Java
Java Program to Perform Naive String Matching
Java Program to Solve Knapsack Problem Using Dynamic Programming
Một số nguyên tắc, định luật trong lập trình
HashMap trong Java hoạt động như thế nào?