This is a java program to find hamilton cycle in graph. 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 Find Hamiltonian Cycle in an UnWeighted Graph. 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 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); /** Make an object of HamiltonianCycle class **/ HamiltonianCycle hc = new HamiltonianCycle(); /** 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 HamiltonianCycle.java $ java HamiltonianCycle 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:
Quick Guide to @RestClientTest in Spring Boot
Spring MVC Setup with Kotlin
Spring Boot Gradle Plugin
Guide to the Synchronized Keyword in Java
Beans and Dependency Injection
Inject Parameters into JUnit Jupiter Unit Tests
Java Program to Implement ArrayList API
A Guide to JUnit 5 Extensions
Java Program to Perform Searching Based on Locality of Reference
Java Program to Implement Branch and Bound Method to Perform a Combinatorial Search
Java Program to Implement Circular Doubly Linked List
Java Program to Implement AttributeList API
A Guide to TreeMap in Java
Apache Camel with Spring Boot
How to use the Spring FactoryBean?
Java Program to Find MST (Minimum Spanning Tree) using Kruskal’s Algorithm
Java Program to Implement LinkedBlockingDeque API
Using a List of Values in a JdbcTemplate IN Clause
“Stream has already been operated upon or closed” Exception in Java
Spring Boot - Enabling HTTPS
Vấn đề Nhà sản xuất (Producer) – Người tiêu dùng (Consumer) và đồng bộ hóa các luồng trong Java
Quick Guide to Spring Controllers
Getting Started with Custom Deserialization in Jackson
Mix plain text and HTML content in a mail
Removing Elements from Java Collections
Converting Between an Array and a Set in Java
A Guide to Java 9 Modularity
Read an Outlook MSG file
A Guide to WatchService in Java NIO2
A Guide to the finalize Method in Java
Remove the First Element from a List
Java Program to Implement Hash Tables with Double Hashing