This is a Java Program to Implement Hamiltonian Cycle Algorithm. Hamiltonian cycle is a path in a graph that visits each vertex exactly once and back to starting vertex. This program is to determine if a given graph is a hamiltonian cycle or not. This program assumes every vertex of the graph to be a part of hamiltonian path.
Here is the source code of the Java Program to Implement Hamiltonian Cycle Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
/** ** Java Program to Implement Hamiltonian Cycle Algorithm **/ import java.util.Scanner; import java.util.Arrays; /** Class HamiltonianCycle **/ public class HamiltonianCycle { 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); System.out.println("HamiltonianCycle Algorithm Test\n"); /** Make an object of HamiltonianCycle class **/ HamiltonianCycle hc = new HamiltonianCycle(); /** Accept number of vertices **/ System.out.println("Enter number of vertices\n"); int V = scan.nextInt(); /** get graph **/ System.out.println("\nEnter matrix\n"); 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); } }
HamiltonianCycle Algorithm Test Enter number of vertices 8 Enter matrix 0 1 0 1 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 1 0 1 0 Solution found Path : 0 1 2 3 7 6 5 4 0
Related posts:
Encode a String to UTF-8 in Java
Guide to BufferedReader
Hamcrest Collections Cookbook
Java – Convert File to InputStream
A Guide to JUnit 5
Java Program to Implement Gauss Seidel Method
Java Program to Implement Doubly Linked List
Hướng dẫn Java Design Pattern – Decorator
Java – Reader to InputStream
Explain about URL and HTTPS protocol
An Introduction to ThreadLocal in Java
Java Program to Check Whether it is Weakly Connected or Strongly Connected for a Directed Graph
Inheritance with Jackson
Tránh lỗi NullPointerException trong Java như thế nào?
Login For a Spring Web App – Error Handling and Localization
Java Program to Generate All Possible Combinations of a Given List of Numbers
Java Program to Implement Rope
Using the Not Operator in If Conditions in Java
Creating a Custom Starter with Spring Boot
@Before vs @BeforeClass vs @BeforeEach vs @BeforeAll
Checking for Empty or Blank Strings in Java
Java Program to Implement Traveling Salesman Problem using Nearest neighbour Algorithm
Setting a Request Timeout for a Spring REST API
Java Program to Represent Graph Using Incidence Matrix
Spring REST API with Protocol Buffers
Getting Started with Forms in Spring MVC
Java Program to Perform Uniform Binary Search
Runnable vs. Callable in Java
JUnit5 @RunWith
Java Program to Perform Finite State Automaton based Search
Java Program to Implement Radix Sort
Logging a Reactive Sequence