# Java Program to Implement Hamiltonian Cycle Algorithm

«
»
This is a Java Program to Implement Hamiltonian Cycle Algorithm. Hamiltonian cycle is a path in a graph that visits each vertex exactly once and back to starting vertex. This program is to determine if a given graph is a hamiltonian cycle or not. This program assumes every vertex of the graph to be a part of hamiltonian path.

Here is the source code of the Java Program to Implement Hamiltonian Cycle Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

1. `/**`
2. ` **   Java Program to Implement Hamiltonian Cycle Algorithm`
3. ` **/`
4. ` `
5. `import java.util.Scanner;`
6. `import java.util.Arrays;`
7. ` `
8. `/** Class HamiltonianCycle **/`
9. `public class HamiltonianCycle`
10. `{`
11. `    private int V, pathCount;`
12. `    private int[] path;     `
13. `    private int[][] graph;`
14. ` `
15. `    /** Function to find cycle **/`
16. `    public void findHamiltonianCycle(int[][] g)`
17. `    {`
18. `        V = g.length;`
19. `        path = new int[V];`
20. ` `
21. `        Arrays.fill(path, -1);`
22. `        graph = g;        `
23. `        try`
24. `        {            `
25. `            path = 0;`
26. `            pathCount = 1;            `
27. `            solve(0);`
28. `            System.out.println("No solution");`
29. `        }`
30. `        catch (Exception e)`
31. `        {`
32. `            System.out.println(e.getMessage());`
33. `            display();`
34. `        }`
35. `    }`
36. `    /** function to find paths recursively **/`
37. `    public void solve(int vertex) throws Exception`
38. `    {`
39. `        /** solution **/`
40. `        if (graph[vertex] == 1 && pathCount == V)`
41. `            throw new Exception("Solution found");`
42. `        /** all vertices selected but last vertex not linked to 0 **/`
43. `        if (pathCount == V)`
44. `            return;`
45. ` `
46. `        for (int v = 0; v < V; v++)`
47. `        {`
48. `            /** if connected **/`
49. `            if (graph[vertex][v] == 1 )`
50. `            {`
51. `                /** add to path **/            `
52. `                path[pathCount++] = v;    `
53. `                /** remove connection **/            `
54. `                graph[vertex][v] = 0;`
55. `                graph[v][vertex] = 0;`
56. ` `
57. `                /** if vertex not already selected  solve recursively **/`
58. `                if (!isPresent(v))`
59. `                    solve(v);`
60. ` `
61. `                /** restore connection **/`
62. `                graph[vertex][v] = 1;`
63. `                graph[v][vertex] = 1;`
64. `                /** remove path **/`
65. `                path[--pathCount] = -1;                    `
66. `            }`
67. `        }`
68. `    }    `
69. `    /** function to check if path is already selected **/`
70. `    public boolean isPresent(int v)`
71. `    {`
72. `        for (int i = 0; i < pathCount - 1; i++)`
73. `            if (path[i] == v)`
74. `                return true;`
75. `        return false;                `
76. `    }`
77. `    /** display solution **/`
78. `    public void display()`
79. `    {`
80. `        System.out.print("\nPath : ");`
81. `        for (int i = 0; i <= V; i++)`
82. `            System.out.print(path[i % V] +" ");`
83. `        System.out.println();`
84. `    }    `
85. `    /** Main function **/`
86. `    public static void main (String[] args) `
87. `    {`
88. `        Scanner scan = new Scanner(System.in);`
89. `        System.out.println("HamiltonianCycle Algorithm Test\n");`
90. `        /** Make an object of HamiltonianCycle class **/`
91. `        HamiltonianCycle hc = new HamiltonianCycle();`
92. ` `
93. `        /** Accept number of vertices **/`
94. `        System.out.println("Enter number of vertices\n");`
95. `        int V = scan.nextInt();`
96. ` `
97. `        /** get graph **/`
98. `        System.out.println("\nEnter matrix\n");`
99. `        int[][] graph = new int[V][V];`
100. `        for (int i = 0; i < V; i++)`
101. `            for (int j = 0; j < V; j++)`
102. `                graph[i][j] = scan.nextInt();`
103. ` `
104. `        hc.findHamiltonianCycle(graph);        `
105. `    }    `
106. `}`

```HamiltonianCycle Algorithm Test

Enter number of vertices

8

Enter matrix

0 1 0 1 1 0 0 0
1 0 1 0 0 1 0 0
0 1 0 1 0 0 1 0
1 0 1 0 0 0 0 1
1 0 0 0 0 1 0 1
0 1 0 0 1 0 1 0
0 0 1 0 0 1 0 1
0 0 0 1 1 0 1 0
Solution found

Path : 0 1 2 3 7 6 5 4 0```

Sanfoundry Global Education & Learning Series – 1000 Java Programs. 