哈密顿回路：原理、示例与回溯解法

在一个图 G 中，哈密顿回路（Hamiltonian Cycle）是指一条经过图中每个顶点恰好一次并回到起点的路径。

• 如果一个图中包含哈密顿回路，我们就称其为哈密顿图；否则，它就是非哈密顿图。
• 寻找哈密顿回路是一个 NP完全 问题，这意味着目前没有已知的高效算法能解决所有类型的图，但对于规模较小或特定类型的图，我们是有解法的。
• 哈密顿回路问题在物流、网络设计和计算机科学等领域有着广泛的应用。

示例问题

给定一个无向图，我们的任务是判断它是否包含哈密顿回路。如果找到了，请打印出路径；否则，打印“Solution does not exist”（解不存在）。

示例：

> 输入: N=5, adjMat[][] = [[0, 1, 0, 1, 0], [1, 0, 1, 1, 1], [0, 1, 0, 0, 1], [1, 1, 0, 0, 1], [0, 1, 1, 1, 0]]

> !409843078

> 输出: [0, 1, 2, 4, 3, 0]

>

> 输入: N=5, adjMat[][] = [[0, 1, 0, 1, 0], [1, 0, 1, 1, 1], [0, 1, 0, 0, 1], [1, 1, 0, 0, 0], [0, 1, 1, 0, 0]]

> !420851416

> 输出: "Solution Does Not Exists"

Try it on GfG Practice<img src="https://www.geeksforgeeks.org/problems/hamiltonian-path2522/1" alt="redirect icon" />

[朴素方法] 生成所有排列组合

> 生成所有可能的顶点排列组合，并打印满足给定约束条件的那个配置。这会产生 n! (n 的阶乘) 种配置。因此，这种方法的时间复杂度至少是 O(n!)。

[期望方法] 使用回溯法

> 我们可以使用回溯法来寻找哈密顿回路。首先初始化一个空的路径数组，将起始顶点（例如 0）放入第一个位置。然后递归地逐个尝试添加剩余的顶点，确保每个新顶点都与前一个顶点相邻，且不在当前路径中。如果找到了一个有效的顶点，就继续；否则，就回溯。

实例演示

让我们为下图找出哈密顿回路：

!409843078

• 从节点 0 开始。应用深度优先搜索 (DFS) 来寻找哈密顿路径。
• 当所有 ‘n‘ 个顶点都被遍历后，检查当前节点是否与起始节点相邻。
• 因为节点 2 不是 0 的邻居，所以返回。由于在路径 {0, 3, 1, 4, 2} 中没有找到回路，所以从节点 2 和 4 返回。

!3

• 探索节点 2。检查哈密顿回路。因为节点 4 不是 0 的邻居，所以返回。从节点 4、2 和 1 返回。

!1-1

• 探索节点 3。在路径 {0, 3, 4, 2, 1, 0} 中，找到了一个回路，打印这条循环路径。这就是我们要找的哈密顿回路。

!4

注意：目前的算法是从一个固定的顶点开始，但哈密顿回路允许从任意顶点开始。如果需要支持从任意节点开始循环，我们需要做一些微小的调整。

C++

`

#include 
#include 

using namespace std;

// 检查将顶点放在当前位置是否安全
bool isSafe(int vertex, vector<vector> &adjMat, 
            vector &path, int pos) {
    
    // 该顶点必须与前一个顶点相邻
    if (!adjMat[path[pos - 1]][vertex]) {
        return false;
    }

    // 该顶点必须还没有在路径中出现过
    for (int i = 0; i < pos; i++) {
        if (path[i] == vertex) {
            return false;
        }
    }

    return true;
}

// 递归回溯以构建哈密顿回路
bool hamCycleUtil(vector<vector> &adjMat, 
                  vector &path, int pos, int n) {
    
    // 基本情况：所有顶点都在路径中了
    if (pos == n) {
        
        // 检查是否存在从最后一个顶点回到第一个顶点的边
        return adjMat[path[pos - 1]][path[0]];
    }

    // 尝试所有可能的顶点作为下一个候选
    for (int v = 1; v < n; v++) {
        if (isSafe(v, adjMat, path, pos)) {
            path[pos] = v;

            if (hamCycleUtil(adjMat, path, pos + 1, n)) {
                return true;
            }

            // 如果 v 不能导致解，则回溯
            path[pos] = -1;
        }
    }

    return false;
}

// 初始化路径并调用回溯函数
vector hamCycle(vector<vector> &adjMat) {
    int n = adjMat.size();
    vector path(n, -1);

    // 将顶点 0 作为路径的起点
    path[0] = 0;

    if (!hamCycleUtil(adjMat, path, 1, n)) {
        return {-1};
    }

    return path;
}

// 主函数
int main() {
    
    vector<vector> adjMat = {
        {0, 1, 0, 1, 0}, 
        {1,