Algorithms/Java/Graphs/Hamiltonian_path.java at main · Kumar-laxmi/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
importjava.util.Scanner;
importjava.util.Arrays;


publicclassHamiltonian_path
{
privateintV, count;
privateint[] path;
privateint[][] graph;

/** Function to find cycle **/
publicvoidfindHamiltonianCycle(int[][] g)
 {
V = g.length;
path = newint[V]; //Path array is declared

Arrays.fill(path, -1); //Used to fill the path array
graph = g;
try
 {
path[0] = 0;
count = 1;
solve(0);
System.out.println("No solution");
 }
catch (Exceptione)
 {
System.out.println(e.getMessage());
display();
 }
 }

publicvoidsolve(intvertex) throwsException
 {

if (graph[vertex][0] == 1 && pathCount == V)
thrownewException("Solution found");

if (count == V)
return;

for (intv = 0; v < V; v++)
 {
if (graph[vertex][v] == 1 )
 {
/** add to path **/
path[count++] = 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[--count] = -1;
 }
 }
 }
/** function to check if path is already selected **/
publicbooleanisPresent(intv)
 {
for (inti = 0; i < count - 1; i++)
if (path[i] == v)
returntrue;
returnfalse;
 }
/** display solution **/
publicvoiddisplay()
 {
System.out.print("\nPath : ");
for (inti = 0; i <= V; i++)
System.out.print(path[i % V] +" ");
System.out.println();
 }

publicstaticvoidmain (String[] args)
 {
Scannerscan = newScanner(System.in);
System.out.println("HamiltonianCycle Algorithm Test\n");

HamiltonianCyclehc = newHamiltonianCycle();

/** Accept number of vertices **/
System.out.println("Enter number of vertices\n");
intV = scan.nextInt();

/** get graph **/
System.out.println("\nEnter matrix\n");
int[][] graph = newint[V][V];
for (inti = 0; i < V; i++)
for (intj = 0; j < V; j++)
graph[i][j] = scan.nextInt();

hc.findHamiltonianCycle(graph);
 }
}

//T(n) = O(2^n*n^2)