寻找图中的哈密顿回路（回溯算法）

题目描述
给定一个无向图 \(G = (V, E)\)，判断图中是否存在一条哈密顿回路（Hamiltonian Cycle）。
哈密顿回路是一条经过图中每个顶点恰好一次，最后回到起点的回路。
输入：图的邻接矩阵表示，顶点数为 \(n\)。
输出：如果存在哈密顿回路，则返回一条回路（顶点顺序）；否则返回不存在。

解题过程循序渐进讲解

第一步：理解哈密顿回路的特点
哈密顿回路必须满足以下条件：

1. 访问每个顶点恰好一次。
2. 相邻顶点之间必须有边（根据邻接矩阵判断）。
3. 最后一个顶点必须与起点相邻，从而形成回路。

第二步：回溯算法的基本思路
我们可以从任意一个顶点开始（比如顶点 0），尝试构造一条路径，逐步添加未访问的顶点。
每一步，检查当前顶点是否可以连接到下一个候选顶点。
如果路径包含所有顶点，并且最后一个顶点与起点相邻，则找到哈密顿回路。
如果某一步无法继续，则回溯到上一步，尝试其他候选顶点。

第三步：算法步骤详解

1. 初始化

   • 路径数组 path[]，长度为 \(n+1\)（因为最后要回到起点，所以有 \(n+1\) 个顶点）。
   • 布尔数组 visited[] 记录每个顶点是否被访问。
   • 从顶点 0 开始，将顶点 0 加入路径，并标记为已访问。
   • 路径索引 pos 初始化为 1，表示接下来要放置第 1 个顶点（实际是路径的第二个位置，因为 0 已放好）。

2. 递归回溯函数
   函数 hamiltonianCycleUtil(path, pos) 的含义是：尝试为路径的第 pos 个位置选择一个顶点。

   • 如果 pos == n，说明已经放置了前 \(n\) 个顶点（0 到 n-1），此时检查顶点 path[n-1] 是否与起点 path[0] 相邻。
     如果相邻，则找到回路，输出路径。
   • 否则，对于当前顶点 path[pos-1]，尝试所有未访问的顶点 \(v\)，检查是否有边 graph[path[pos-1]][v] == 1。
     如果有，则将 \(v\) 加入路径，标记已访问，递归调用 pos+1。
     递归返回后，撤销选择（标记 \(v\) 未访问），尝试其他顶点。

3. 回溯过程示例
   假设图有 5 个顶点，邻接矩阵如下（1 表示有边）：

   0 1 1 0 1
   1 0 1 1 1
   1 1 0 1 0
   0 1 1 0 1
   1 1 0 1 0
   

   • 路径初始：[0, _, _, _, _, _]（最后一位留给起点重复）。
   • 从 0 出发，尝试顶点 1：有边，路径变为 [0,1,_,_,_,_]，递归。
   • 从 1 出发，尝试顶点 2：有边，路径 [0,1,2,_,_,_]，继续。
   • 从 2 出发，尝试顶点 3：有边，路径 [0,1,2,3,_,_]，继续。
   • 从 3 出发，尝试顶点 4：有边，路径 [0,1,2,3,4,_]，此时 pos=5（即已放好 0,1,2,3,4）。
   • 检查是否找到回路：需要检查顶点 4 与起点 0 是否有边。邻接矩阵中 graph[4][0]=1，有边，所以得到一条回路 [0,1,2,3,4,0]。
   • 如果某条路径失败（比如最后一个顶点与起点无边），则回溯到上一步尝试其他顶点。

4. 算法伪代码

   function isSafe(v, path, pos):
       if graph[path[pos-1]][v] == 0:  // 当前最后一个顶点与 v 无边
           return false
       if visited[v] == true:
           return false
       return true
   
   function hamiltonianCycleUtil(path, pos):
       if pos == n:
           if graph[path[pos-1]][path[0]] == 1:
               return true  // 找到回路
           else:
               return false
   
       for v from 1 to n-1:  // 尝试所有顶点（0 已用）
           if isSafe(v, path, pos):
               path[pos] = v
               visited[v] = true
               if hamiltonianCycleUtil(path, pos+1) == true:
                   return true
               visited[v] = false
               path[pos] = -1  // 回溯
       return false
   

5. 主函数

   • 初始化 path[0] = 0, visited[0] = true，其余顶点未访问。
   • 调用 hamiltonianCycleUtil(path, 1)。
   • 如果返回 true，输出路径；否则输出不存在。

第四步：复杂度分析

• 最坏情况下，需要尝试所有顶点的排列，但通过边存在的条件剪枝。
• 时间复杂度为 \(O(n!)\)，因为回溯搜索所有可能排列。
• 空间复杂度为 \(O(n)\)，用于存储路径和访问数组。

第五步：优化与注意事项

• 可以从每个顶点开始，但由对称性，从 0 开始即可。
• 可以通过启发式（如优先选择度数小的顶点）优化搜索顺序，但最坏复杂度仍为阶乘级。
• 哈密顿回路问题是 NP 完全问题，不存在多项式时间算法（除非 P=NP）。