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:
Java Program to Implement Fisher-Yates Algorithm for Array Shuffling
Java Program to Implement Queue
Lớp Properties trong java
Request Method Not Supported (405) in Spring
Hướng dẫn Java Design Pattern – Proxy
Java Program to Solve TSP Using Minimum Spanning Trees
Multi Dimensional ArrayList in Java
Server-Sent Events in Spring
Lập trình đa luồng với CompletableFuture trong Java 8
Java Program to Perform Inorder Recursive Traversal of a Given Binary Tree
Converting a Stack Trace to a String in Java
Java equals() and hashCode() Contracts
Java Program to Describe the Representation of Graph using Incidence Matrix
A Guide to JUnit 5
@Order in Spring
Removing all duplicates from a List in Java
An Introduction to ThreadLocal in Java
Examine the internal DNS cache
Spring REST API + OAuth2 + Angular
Java Program to Implement Heap’s Algorithm for Permutation of N Numbers
Hướng dẫn sử dụng Java String, StringBuffer và StringBuilder
Giới thiệu Java Service Provider Interface (SPI) – Tạo các ứng dụng Java dễ mở rộng
Immutable Map Implementations in Java
Java Program to Find Minimum Number of Edges to Cut to make the Graph Disconnected
Batch Processing with Spring Cloud Data Flow
Hướng dẫn Java Design Pattern – MVC
Practical Java Examples of the Big O Notation
Spring Cloud AWS – EC2
Extract network card address
Java Program to Perform Addition Operation Using Bitwise Operators
Apache Commons Collections MapUtils
Java Program to Implement ArrayList API