Enumerate *all* hamiltonian paths

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.

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;
}  

}

Solution in Python3:

def hamiltonians(G, vis = []):
    if not vis:
        for n in G:
            for p in hamiltonians(G, [n]):
                yield p
    else:
        dests = set(G[vis[-1]]) - set(vis)
        if not dests and len(vis) == len(G):
            yield vis
        for n in dests:
            for p in hamiltonians(G, vis + [n]):
                yield p
G = {'a' : 'bc', 'b' : 'ad', 'c' : 'b', 'd' : 'ac'}
print(list(hamiltonians(G)))

A depth-first exhaustive search gives you the answer. I just finished a write-up on a Java implementation for this problem (including the code):

http://puzzledraccoon.wordpress.com/2012/06/07/how-to-cool-a-data-center/