Java Program to Check if a Given Graph must Contain Hamiltonian Cycle or Not

This is a java program to check if the graph contains any Hamiltonian cycle. 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 Check if a Given Graph Contain Hamiltonian Cycle or Not. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

```
 
```
```
package com.sanfoundry.hardgraph;
```
```
 
```
```
import java.util.Arrays;
```
```
import java.util.Scanner;
```
```
 
```
```
public class CheckHamiltonianCycle
```
```
{
```
```
    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 **/

        CheckHamiltonianCycle hc = new CheckHamiltonianCycle();

        /** 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 CheckHamiltonianCycle.java
$ java CheckHamiltonianCycle
 
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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

« Prev - Java Program to Find the Minimum Number of Edges to Remove to Disconnect a Graph

» Next - Java Program to Find the Longest Path in a Directed Acyclic Graph

Related Posts:

Recommended Articles: