Hamiltonian Cycle

Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a Hamiltonian path that is a cycle. Hamiltonian Path problem is actually looking for a longest simple path in a graph. This is a classic NP-complete problem.

Write a program to find the Hamiltonian Cycle.

source Code

package com.dsacode.Algorithm.backtracking;
 
import java.util.Arrays;
 
public class HamiltonianCycle {
    private int V, pathCount;
    private int[] path;
    private int[][] graph;
 
    public HamiltonianCycle(int V){
        this.V=V;
    }
 
    public void findHamiltonianCycle(int[][] g) {  
        graph = g;
        path = new int[graph.length];
 
        Arrays.fill(path, -1);
         
        try {
            path[0] = 0;
            pathCount = 1;
            solve(0);
            System.out.println("No solution");
        } catch (Exception e) {
            System.out.println(e.getMessage());
            display();
        }
    }
 
 
    public void solve(int vertex) throws Exception {
        if (graph[vertex][0] == 1 && pathCount == graph.length)
            throw new Exception("Hamiltonian Cycle Solution found");
        if (pathCount == graph.length)
            return;
 
        for (int v = 0; v < graph.length; v++) {
            if (graph[vertex][v] == 1) {
 
                path[pathCount++] = v;
                graph[vertex][v] = 0;
                graph[v][vertex] = 0;
 
                if (!isPresent(v))
                    solve(v);
 
                graph[vertex][v] = 1;
                graph[v][vertex] = 1;
                path[--pathCount] = -1;
            }
        }
    }
 
    public boolean isPresent(int v) {
        for (int i = 0; i < pathCount - 1; i++)
            if (path[i] == v)
                return true;
        return false;
    }
 
    public void display() {
        System.out.print("Display the Hamiltonian Cycle Path : ");
        for (int i = 0; i <= V; i++)
            if(i==V)
                System.out.print(path[i % V]);
            else
                System.out.print(path[i % V] + "-> ");
         
        System.out.println();
    }
 
    public static void main(String[] args) {
     
        HamiltonianCycle hc = new HamiltonianCycle(5);
        int[][] graph1 = {{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},
                     };
        System.out.println("Print the values from graph: "+Arrays.deepToString(graph1));
        hc.findHamiltonianCycle(graph1);
    }
 
}

Output

Print the values from graph: [[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]]
Hamiltonian Cycle Solution found
Display the Hamiltonian Cycle Path: 0-> 1-> 2-> 4-> 3-> 0

Algorithm Explanation

	Give two dimension array of elements, Function to find cycle and find paths recursively.
	Create an empty path array and add vertex 0 to it. Add other vertices, starting from the vertex 1.
	Check for whether it is adjacent to the previously added vertex and not already added.
	If it finds such a vertex, we add the vertex as part of the solution. Otherwise, return false.

Reference

1. http://mathworld.wolfram.com/HamiltonianCycle.html
2. https://en.wikipedia.org/wiki/Hamiltonian_path
3. http://www.whitman.edu/mathematics/cgt_online/section05.03.html