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:
A Guide to Java HashMap
Sort a HashMap in Java
Java Program to Implement Flood Fill Algorithm
Ways to Iterate Over a List in Java
Java Program to Implement Karatsuba Multiplication Algorithm
Runnable vs. Callable in Java
How to Get All Spring-Managed Beans?
Java Web Services – JAX-WS – SOAP
Java String Conversions
Derived Query Methods in Spring Data JPA Repositories
Java Program to Perform Insertion in a BST
How to Manually Authenticate User with Spring Security
Lấy ngày giờ hiện tại trong Java
Java Program to Implement Hash Tables with Quadratic Probing
Java Program to Implement WeakHashMap API
Java Program to Implement Floyd-Warshall Algorithm
Spring Boot - Tracing Micro Service Logs
Mảng (Array) trong Java
Java Program to Find MST (Minimum Spanning Tree) using Prim’s Algorithm
Feign – Tạo ứng dụng Java RESTful Client
Spring WebClient Filters
Introduction to Using Thymeleaf in Spring
Merging Two Maps with Java 8
Spring Data Java 8 Support
Converting a List to String in Java
Một số nguyên tắc, định luật trong lập trình
How to Change the Default Port in Spring Boot
Java Program to Implement Sorted Array
Sending Emails with Java
Spring Boot - Build Systems
Java Program to Check whether Graph is Biconnected
Phân biệt JVM, JRE, JDK