回溯法---哈密顿回路（5）

回溯法---哈密顿回路（5）<?xml version="1.0" encoding="UTF-8"?>
在给定图中任取一点，要求经过图中所有点，最后回到起始点，要求同一个点不允许重复经过

在（2）算法框架基础上：

importjava.util.Vector;

publicclassHamiltonextendsCombineProblem{

        intstart;

        int[][]graph;

        publicHamilton(int[][]graph,intstart,intn){
                this.graph=graph;

                this.flag=false;

                this.n=n;

                this.x=newInteger[n];

                this.start=start-1;

        }

        @Override
        publicVector<Comparable>makeIterm(intk){
                Vector vec=newVector();
                if(k==0){
                        vec.add(start);
                }else
                        for(inti=0;i<n;i++){
                                if(graph[(Integer)x[k-1]][i]==1){
                                        vec.add(i);
                                }
                        }
                returnvec;
        }

        @Override
        publicbooleancomplete(intk){
                if(k>=n){
                        returngraph[(Integer)x[k-1]][(Integer)x[0]]==1;
                }
                returnfalse;
        }

        @Override
        publicvoidprintsolution(intk){
                for(inti=0;i<n;i++){
                        System.out.print((Integer)x[i]+1+" ");
                }
                System.out.println();
        }

        @Override
        publicbooleanisPartial(intk){
                for(inti=0;i<k;i++){
                        if(x[i].compareTo(x[k])==0){
                                returnfalse;
                        }
                }
                returntrue;
        }
}

运行结果：

1 2 5 4 3
1 3 2 5 4
1 3 4 5 2
1 4 5 2 3 




转载于:https://www.cnblogs.com/ZhangJinkun/p/4531359.html