import java.util.ArrayList;
class GFG {
boolean isSafe(int v, int graph[][],
ArrayList<Integer> path,
int pos)
{
if (graph[path.get(pos - 1)][v]
== 0)
return false;
for (int i = 0; i < pos; i++)
if (path.get(i) == v)
return false;
return true;
}
boolean hasCycle;
void hamCycle(int graph[][])
{
hasCycle = false;
ArrayList<Integer> path
= new ArrayList<>();
path.add(0);
boolean[] visited
= new boolean[graph.length];
for (int i = 0;
i < visited.length; i++)
visited[i] = false;
visited[0] = true;
FindHamCycle(graph, 1, path,
visited);
if (!hasCycle) {
System.out.println(
"No Hamiltonian Cycle"
+ "possible ");
return;
}
}
void FindHamCycle(int graph[][], int pos,
ArrayList<Integer> path,
boolean[] visited)
{
if (pos == graph.length) {
if (graph[path.get(path.size() - 1)]
[path.get(0)]
!= 0) {
path.add(0);
for (int i = 0;
i < path.size(); i++) {
System.out.print(
path.get(i) + " ");
}
System.out.println();
path.remove(path.size() - 1);
hasCycle = true;
}
return;
}
for (int v = 0;
v < graph.length; v++) {
if (isSafe(v, graph, path, pos)
&& !visited[v]) {
path.add(v);
visited[v] = true;
FindHamCycle(
graph, pos + 1,
path, visited);
visited[v] = false;
path.remove(
path.size() - 1);
}
}
}
public static void main(String args[])
{
GFG hamiltonian = new GFG();
int[][] graph = {
{ 0, 1, 1, 0, 0, 1 },
{ 1, 0, 1, 0, 1, 1 },
{ 1, 1, 0, 1, 0, 0 },
{ 0, 0, 1, 0, 1, 0 },
{ 0, 1, 0, 1, 0, 1 },
{ 1, 1, 0, 0, 1, 0 },
};
hamiltonian.hamCycle(graph);
}
}
Original page link
Best Cool Tech Gadgets
Top favorite technology gadgets
0 comments:
Post a Comment