回溯法-哈密尔顿回路

野性酷女 2022-11-18 04:48 146阅读 0赞

#### 一、哈密顿回路 ####

哈密顿回路的定义： G=(V,E)是一个图，若G中一条路径通过且仅通过每一个顶点一次，称这条路径为哈密顿路径。若G中一个回路通过且仅通过每一个顶点一次，称这个环为哈密顿回路。若一个图存在哈密顿回路，就称为哈密顿图。

#### 二、java程序代码 ####

运用了深度优先搜索方法，即递归和回溯法思想

public class HamiltonCount { 
        /** * 连通图:4个顶点 5条边 * 0. . . . . .1 * . . . * . . . * .2. . . . . 3 */
        //邻接矩阵
        private static int[][] matrix = { 
                { 0, 1, 1, 0},
                { 1, 0, 1, 1},
                { 1, 1, 0, 1},
                { 0, 1, 1, 0}
        };
    
        public static void main(String[] args) { 
            boolean[] used = new boolean[matrix.length]; //用于标记图中顶点是否被访问
            int[] path = new int[matrix.length]; //记录哈密尔顿路径
            for (int i = 0; i < matrix.length; i++) { //进行初始化
                used[i] = false;//默认没被访问过
                path[i] = 0;//未选择起点和到达其他顶点
            }
            //从第0个顶点开始进行深度优先遍历
            used[0] = true;//代表从第一个顶点开始遍历
            path[0] = 0;//代表起点为第0个起点
            dfs(path,used,1);
        }
    
        //step：所走的步数
        public static boolean dfs(int[] path,boolean[] used,int step){ 
            //如果满足条件：当前是最后一步且最后一步能回到顶点
            if(step==matrix.length&&matrix[path[step-1]][0]==1){ 
                //输出
                System.out.println("结果："+Arrays.toString(path));
                return true;
            }else { 
                //查找
                for (int i=0;i<matrix.length;i++){ 
                    //满足当前顶点没被访问过且当前路径可连通，则继续下一步
                    if(!used[i]&&matrix[path[step-1]][i]==1){ 
                        used[i]=true;//设置当前顶点被访问过
                        path[step]=i;//设置当前路径
                        //进行下一步深搜
                        if(dfs(path,used,step+1)){ 
                            return true;
                        }else { 
                            //无法满足下一步
                            used[i]=false;//设置当前顶点访问还原
                            path[step]=0;//将当前路径清空
                            //此时进行回溯，返回到上一个step再进行遍历判断是否满足下一步
                        }
                    }
                }
            }
            return false;
        }
    }