Repository: TheAlgorithms/Java
Pull request #3151 (2022-06-20 09:45:10)

Hamiltonian cycle implementation
### **Describe your change:**

- [X] Add an algorithm?
- [ ] Fix a bug or typo in an existing algorithm?
- [ ] Documentation change?

#### References

https://github.com/TheAlgorithms/Java/issues/3057 Implementation of Hamiltonian Cycle

### **Checklist:**

<!-- Remove items that do not apply. For completed items, change [ ] to [x]. -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized.
- [x] I know that pull requests will not be merged if they fail the automated tests.
- [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
- [x] All new Java files are placed inside an existing directory.
- [x] All filenames are in all uppercase characters with no spaces or dashes.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in its comments that points to Wikipedia or other similar explanation.
- [x] If this pull request resolves one or more open issues then the commit message contains `Fixes: #{$ISSUE_NO}`.



Patch:
diff --git a/src/main/java/com/thealgorithms/datastructures/graphs/HamiltonianCycle.java b/src/main/java/com/thealgorithms/datastructures/graphs/HamiltonianCycle.java
new file mode 100644
index 00000000..e0f373bf
--- /dev/null
+++ b/src/main/java/com/thealgorithms/datastructures/graphs/HamiltonianCycle.java
@@ -0,0 +1,100 @@
+package com.thealgorithms.datastructures.graphs;
+
+/**
+ * Java program for Hamiltonian Cycle (https://en.wikipedia.org/wiki/Hamiltonian_path)
+ * @author Akshay Dubey (https://github.com/itsAkshayDubey)
+ */
+public class HamiltonianCycle {
+
+    private int V, pathCount;
+    private int[] cycle;
+    private int[][] graph;
+
+    /**
+     * Find hamiltonian cycle for given graph G(V,E)
+     * @param graph Adjacency matrix of a graph G(V, E) 
+     * for which hamiltonian path is to be found
+     * @return Array containing hamiltonian cycle 
+     * else returns 1D array with value -1.
+     */
+    public int[] findHamiltonianCycle(int[][] graph){
+        this.V = graph.length;
+        this.cycle = new int[this.V+1];
+
+        //Initialize path array with -1 value
+        for(int i=0 ; i<this.cycle.length ; i++) {
+            this.cycle[i] = -1;
+        }
+
+        this.graph = graph;        
+
+        this.cycle[0] = 0;
+        this.pathCount = 1;            
+        if(!isPathFound(0)) {
+            for(int i=0 ; i<this.cycle.length ; i++) {
+                this.cycle[i] = -1;
+            }
+        }
+        else {
+        	this.cycle[this.cycle.length-1] = this.cycle[0];
+        }
+        
+        return cycle;
+    }
+
+    /** function to find paths recursively
+     * Find paths recursively from given vertex
+     * @param vertex Vertex from which path is to be found
+     * @returns true if path is found false otherwise
+     */
+    public boolean isPathFound(int vertex) {
+        if (this.graph[vertex][0] == 1 && this.pathCount == this.V) {
+            return true;
+        }
+
+        /** all vertices selected but last vertex not linked to 0 **/
+        if (this.pathCount == this.V) {
+            return false;
+        }
+
+        for (int v = 0; v < this.V; v++){
+            /** if connected **/
+            if (this.graph[vertex][v] == 1 ){
+                /** add to path **/            
+                this.cycle[this.pathCount++] = v;    
+
+                /** remove connection **/            
+                this.graph[vertex][v] = 0;
+                this.graph[v][vertex] = 0;
+
+                /** if vertex not already selected  solve recursively **/
+                if (!isPresent(v)) {
+                    return isPathFound(v);
+                }
+
+                /** restore connection **/
+                this.graph[vertex][v] = 1;
+                this.graph[v][vertex] = 1;
+
+                /** remove path **/
+                this.cycle[--this.pathCount] = -1;
+            }
+        }
+        return false;
+    }    
+
+    /** function to check if path is already selected
+     * Check if path is already selected
+     * @param vertex Starting vertex 
+     */
+    public boolean isPresent(int vertex){
+
+        for (int i = 0; i < pathCount - 1; i++) {
+            if (cycle[i] == vertex) {
+                return true;
+            }
+        }
+
+        return false;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/graphs/HamiltonianCycleTest.java b/src/test/java/com/thealgorithms/datastructures/graphs/HamiltonianCycleTest.java
new file mode 100644
index 00000000..6b4c5102
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/graphs/HamiltonianCycleTest.java
@@ -0,0 +1,39 @@
+package com.thealgorithms.datastructures.graphs;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+import org.junit.jupiter.api.Test;
+
+class HamiltonianCycleTest {
+
+	private HamiltonianCycle hamiltonianCycle = new HamiltonianCycle();
+
+	@Test
+	void testFindHamiltonianCycleShouldReturnHamiltonianCycle() {
+		int[] expectedArray = {0,1,2,4,3,0};
+		int[][] inputArray =  {
+				{0, 1, 0, 1, 0},
+				{1, 0, 1, 1, 1},
+				{0, 1, 0, 0, 1},
+				{1, 1, 0, 0, 1},
+				{0, 1, 1, 1, 0}
+		};
+
+		assertArrayEquals(expectedArray, hamiltonianCycle.findHamiltonianCycle(inputArray));
+	}
+
+	@Test
+	void testFindHamiltonianCycleShouldReturnInfinityArray() {
+		int[] expectedArray = {-1,-1,-1,-1,-1,-1};
+
+		int[][] inputArray =  {
+				{0, 1, 0, 1, 0},
+				{1, 0, 1, 1, 1},
+				{0, 1, 0, 0, 1},
+				{1, 1, 0, 0, 0},
+				{0, 1, 1, 0, 0}
+		};
+
+		assertArrayEquals(expectedArray, hamiltonianCycle.findHamiltonianCycle(inputArray));
+	}
+}