# Java Program to Find Hamiltonian Cycle in an UnWeighted Graph

«
»
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.

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

Output:

```\$ javac HamiltonianCycle.java
\$ java HamiltonianCycle

Enter number of vertices
6
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. 