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:
Java Program to Find Minimum Element in an Array using Linear Search
Java Program to Implement LinkedHashSet API
Xây dựng ứng dụng Client-Server với Socket trong Java
Java Program to Perform Polygon Containment Test
Java Program to Check Whether an Undirected Graph Contains a Eulerian Path
wait() and notify() Methods in Java
Spring Boot - Build Systems
Spring Boot - Cloud Configuration Server
Adding Shutdown Hooks for JVM Applications
So sánh HashMap và Hashtable trong Java
Hướng dẫn sử dụng lớp Console trong java
Vector trong Java
Java Program to Implement PrinterStateReasons API
Spring @Primary Annotation
Java Program to Solve Tower of Hanoi Problem using Stacks
Guide to DelayQueue
Introduction to the Java NIO2 File API
Spring JDBC
Comparing Strings in Java
Configure a RestTemplate with RestTemplateBuilder
Introduction to Spring Cloud Netflix – Eureka
New Features in Java 15
Java Program to Implement Splay Tree
Spring MVC + Thymeleaf 3.0: New Features
Java – String to Reader
Guide to Java 8 groupingBy Collector
Hướng dẫn Java Design Pattern – Observer
Java Program to Evaluate an Expression using Stacks
Extra Login Fields with Spring Security
Java Program to subtract two large numbers using Linked Lists
How to Get All Dates Between Two Dates?
Intro to Spring Boot Starters