如何使用BFS算法查找无向图中所有哈密顿回路

你现有代码的核心问题是：普通环检测逻辑使用全局共享的visited数组和parent数组，这套逻辑仅能判断图中是否存在环，无法跟踪每一条独立路径的访问状态——BFS产生路径分叉时，不同路径的已访问节点集合完全独立，共享数组会导致不同路径的访问标记互相干扰，自然无法实现哈密顿回路的查找。

核心实现思路 #

你之前梳理的两个核心逻辑完全正确，要落地成非递归BFS实现，只需要把BFS队列的存储单元从「单个节点ID」改成「独立路径状态」即可，完全不需要递归逻辑：

• 每个队列元素存储三类信息：当前所在节点、当前路径已访问的节点集合、当前路径的完整节点序列
• 固定一个起点（比如节点0）作为所有回路的遍历起点，避免同一条回路因为起点不同被重复统计
• 每次取出队首状态后，遍历当前节点的所有邻接节点做判断：
  • 若邻接节点是起点，且当前路径已经覆盖所有节点，说明找到合法哈密顿回路，存入结果集
  • 若邻接节点不是起点，且未出现在当前路径的已访问集合中，就将该节点加入路径，生成新的状态入队

注意：无向图的边是双向的，同一条哈密顿回路会被正向、反向各遍历一次，最终可以通过路径标准化规则过滤重复结果，也可以在遍历阶段增加方向限制减少无效入队。

针对你现有代码的修改点 #

• 删掉原来全局的visited和parent数组，不同路径的访问状态完全独立，全局共享的标记会导致不同路径的状态互相干扰，无法正确跟踪单条路径的访问情况
• 定义队列存储的状态结构，节点规模较小时可以用位掩码存储已访问节点集合，相比布尔数组读写效率更高，同时要存储当前路径序列用于最终输出回路
• 调整BFS循环逻辑，不再检测到第一个环就直接返回，需要遍历所有可能的路径分支，仅当路径覆盖全部节点且回到起点时，才判定为有效哈密顿回路记录下来

修改后的可运行代码 #

#include <bits/stdc++.h>
using namespace std;

void addEdge(vector<int> adj[], int u, int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}

// BFS队列中存储的单条路径状态
struct State {
    int curNode;
    int visitedMask; // 位掩码，第i位为1表示节点i已在当前路径中
    vector<int> path;
};

vector<vector<int>> findAllHamiltonianCycles(vector<int> adj[], int V, int start = 0)
{
    vector<vector<int>> res;
    queue<State> q;
    // 初始状态：位于起点，仅访问过起点，路径只包含起点
    q.push({start, 1 << start, {start}});

    while (!q.empty()) {
        State s = q.front();
        q.pop();

        for (int neighbor : adj[s.curNode]) {
            // 邻接节点为起点时，检查是否已覆盖所有节点
            if (neighbor == start) {
                if (__builtin_popcount(s.visitedMask) == V) {
                    vector<int> cycle = s.path;
                    cycle.push_back(start);
                    res.push_back(cycle);
                }
                continue;
            }
            // 邻接节点未访问过，生成新路径状态入队
            if (!(s.visitedMask & (1 << neighbor))) {
                State newState;
                newState.curNode = neighbor;
                newState.visitedMask = s.visitedMask | (1 << neighbor);
                newState.path = s.path;
                newState.path.push_back(neighbor);
                q.push(newState);
            }
        }
    }
    return res;
}

int main()
{
    int V = 4;
    vector<int> adj[V];
    addEdge(adj, 0, 1);
    addEdge(adj, 1, 2);
    addEdge(adj, 2, 0);
    addEdge(adj, 2, 3);
    addEdge(adj, 1, 3); 
    // 注：原测试用例中节点3仅连节点2（度数为1），不存在哈密顿回路，补1-3边后符合测试图结构

    vector<vector<int>> cycles = findAllHamiltonianCycles(adj, V);
    if (cycles.empty()) {
        cout << "No Hamiltonian cycle found" << endl;
    } else {
        cout << "Found " << cycles.size() << " Hamiltonian cycles:" << endl;
        for (auto& cycle : cycles) {
            for (int i = 0; i < cycle.size(); i++) {
                if (i > 0) cout << "->";
                cout << cycle[i];
            }
            cout << endl;
        }
    }
    return 0;
}

补充说明 #

• 代码中使用的位掩码方案适合节点数不超过32的场景（用int存储），如果节点规模更大，可以把visitedMask替换为vector<bool>或者bitset，核心逻辑不需要改动。
• 如果需要对结果去重（过滤同一条回路的反向遍历、不同起点的重复记录），可以在存储回路时做标准化处理，比如固定起点为路径中编号最小的节点，仅保留路径第二个节点小于倒数第二个节点的结果，即可过滤掉反向重复的回路。

内容的提问来源于stack exchange，提问作者Matias