算法笔记_09 哈密顿环(NP、回溯法、分支定界)

引用

1. 哈密顿回路分支限界遍历法
2. 哈密顿回路-回溯法
3. 汉密尔顿路径（哈密顿路径）解析
4. 基于回溯法寻找哈密顿回路
5. 哈密顿回路

代码只有自己思考并能写的才是自己的。这段代码我是copy。

public class Hamiltonian {
    
    /**
     * 参数adjMatrix:给定图的邻接矩阵，其中值1表示两个顶点可以相同，值为-1
     * 表示两个顶点不能相同
     * @param adjMatrix
     */
    public void getHamilton(int[][] adjMatrix) {
        boolean[] used = new boolean[adjMatrix.length]; //用于标记图中顶点是否被访问
        int[] path = new int[adjMatrix.length];     //记录哈密顿回路路径
        for(int i = 0; i < adjMatrix.length; i++) {
            used[i] = false;        //初始化，所有顶点均未被遍历
            path[i] = -1;           //初始化，未选中起点及到达任何顶点
        }
        used[0] = true;     //表示从第一个顶点开始遍历
        path[0] = 0;        //表示哈密顿回路起点为第0个顶点
        dfs(adjMatrix, path, used, 1);  //从第0个顶点开始进行深度优先遍历，如果存在哈密顿
                                        //回路,输出一条回路，否则无输出
    }
    
    /**
     * @param adjMatrix
     * @param path
     * @param used
     * @param step      当前行走的步数
     * @return
     */
    public boolean dfs(int[][] adjMatrix, int[] path, boolean[] used, int step) {
        if(step == adjMatrix.length) {      //当已经遍历完图中所有的顶点
            if(adjMatrix[path[step - 1]][0] == 1) {     //最后一步到达的顶点可以回到起点
                for(int i = 0; i < path.length; i++) 
                    System.out.print((char)(path[i] + 'a') + "--->");
                System.out.print((char)(path[0] + 'a'));
                System.out.println();
                return true;
            }
            return false;
        } else {
            for(int i = 0; i < adjMatrix.length; i++) {
                if(!used[i] && adjMatrix[path[step - 1]][i] == 1) {
                    used[i] = true;
                    path[step] = i;
                    if(dfs(adjMatrix, path, used, step + 1))
                        return true;
                    else {
                        used[i] = false;    //回溯处理
                        path[step] = -1;
                    }
                }
            }
        }
        
        return false;
                
    }

    public static void main(String[] args) {
        Hamiltonian test = new Hamiltonian();
        int[][] adjMatrix = {{-1,1,1,1,-1,-1},
                {1,-1,1,-1,-1,1},
                {1,1,-1,1,1,-1},
                {1,-1,1,-1,1,-1},
                {-1,-1,1,1,-1,1},
                {-1,1,-1,-1,1,-1}};
        test.getHamilton(adjMatrix);
    }

}