I know this has been asked before, but I did not find its answer in any of the posts. Can someone please suggest me an algorithm which enumerates ALL Hamiltonian paths in a graph?
A little background: I am working on a problem in which I have to enumerate each Hamiltonian path, do some analysis, and return the result. For that, I need to be able to enumerate all the possible hamiltonian paths.
Thanks.
A complete graph with 8 vertices would have = 5040 possible Hamiltonian circuits. Half of the circuits are duplicates of other circuits but in reverse order, leaving 2520 unique routes.
Depth first search and backtracking can also help to check whether a Hamiltonian path exists in a graph or not. Simply apply depth first search starting from every vertex v and do labeling of all the vertices. All the vertices are labelled as either "IN STACK" or "NOT IN STACK".
Hamiltonian Graph Example-This graph contains a closed walk ABCDEFA. It visits every vertex of the graph exactly once except starting vertex. The edges are not repeated during the walk. Therefore, it is a Hamiltonian graph.
A Hamilton Path is a path that goes through every Vertex of a graph exactly once. A Hamilton Circuit is a Hamilton Path that begins and ends at the same vertex. *Unlike Euler Paths and Circuits, there is no trick to tell if a graph has a Hamilton Path or Circuit.
Use BFS/DFS as suggested but don't stop at the first solution. BFS/DFS primary use (in this case) will be to find all of the solution, you need to put a condition to it to stop at the first one.
My java code: (absolutely based on recursive method)
algorithm:
+Start at 1 point connect to another point it can see(to form a path).
+remove the path and recursively find new path at newest point until connect all points of graph.
+remove the path and backtrack to initial graph if cant form Hamilton path from newest point
public class HamiltonPath {
public static void main(String[] args){
HamiltonPath obj = new HamiltonPath();
int[][]x = {{0,1,0,1,0}, //Represent the graphs in the adjacent matrix forms
{1,0,0,0,1},
{0,0,0,1,0},
{1,0,1,0,1},
{0,1,0,1,0}};
int[][]y = {{0,1,0,0,0,1},
{1,0,1,0,0,1},
{0,1,0,1,1,0},
{0,0,1,0,0,0},
{0,0,1,0,0,1},
{1,1,0,0,1,0}};
int[][]z = {{0,1,1,0,0,1},
{1,0,1,0,0,0},
{1,1,0,1,0,1},
{0,0,1,0,1,0},
{0,0,0,1,0,1},
{1,0,1,0,1,0}};
obj.allHamiltonPath(y); //list all Hamiltonian paths of graph
//obj.HamiltonPath(z,1); //list all Hamiltonian paths start at point 1
}
static int len;
static int[]path;
static int count = 0;
public void allHamiltonPath(int[][]x){ //List all possible Hamilton path in the graph
len = x.length;
path = new int[len];
int i;
for(i = 0;i<len;i++){ //Go through column(of matrix)
path[0]=i+1;
findHamiltonpath(x,0,i,0);
}
}
public void HamiltonPath(int[][]x, int start){ //List all possible Hamilton path with fixed starting point
len = x.length;
path = new int[len];
int i;
for(i = start-1;i<start;i++){ //Go through row(with given column)
path[0]=i+1;
findHamiltonpath(x,0,i,0);
}
}
private void findHamiltonpath(int[][]M,int x,int y,int l){
int i;
for(i=x;i<len;i++){ //Go through row
if(M[i][y]!=0){ //2 point connect
if(detect(path,i+1))// if detect a point that already in the path => duplicate
continue;
l++; //Increase path length due to 1 new point is connected
path[l]=i+1; //correspond to the array that start at 0, graph that start at point 1
if(l==len-1){//Except initial point already count =>success connect all point
count++;
if (count ==1)
System.out.println("Hamilton path of graph: ");
display(path);
l--;
continue;
}
M[i][y]=M[y][i]=0; //remove the path that has been get and
findHamiltonpath(M,0,i,l); //recursively start to find new path at new end point
l--; // reduce path length due to the failure to find new path
M[i][y] = M[y][i]=1; //and tranform back to the inital form of adjacent matrix(graph)
}
}path[l+1]=0; //disconnect two point correspond the failure to find the..
} //possible hamilton path at new point(ignore newest point try another one)
public void display(int[]x){
System.out.print(count+" : ");
for(int i:x){
System.out.print(i+" ");
}
System.out.println();
}
private boolean detect(int[]x,int target){ //Detect duplicate point in Halmilton path
boolean t=false;
for(int i:x){
if(i==target){
t = true;
break;
}
}
return t;
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With