圆桌骑士座位问题：DFS实现哈密顿环检测失败排查

问题描述 #

大厅中有一张圆桌，周围有N把椅子。每位骑士仅愿意坐在朋友身旁。输入第一行为整数n（3<=n<=100），代表骑士数量，编号1到n。接下来n行每行包含n个0或1的数值，构成邻接矩阵，第i行第j列的值为1表示骑士i和j是朋友，0则不是，且友谊是双向的。若骑士能按要求围坐圆桌，输出YES，否则输出NO。

我的思路与问题 #

思路是检测图中是否存在长度为N的哈密顿环，存在则输出YES，否则NO。代码能通过基础测试用例，但在n较大的测试用例中出现Wrong Answer（非超时）。

我的代码 #

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

void dfs_search(vector<vector<int>> &matrix, vector<bool> &visited, int node, int parent, int n, int path, bool &found){
    if(found)
        return;
    else if(visited[node] && node == parent && path == n){
        found = 1;
        return;
    }
    else if(visited[node])
        return;
    else{
        visited[node] = 1;
        path++; 
        //cout<<node<<" "<<path<<endl;
        
        for(int i=0; i < n; i++){
            if(matrix[node][i] == 1){
                dfs_search(matrix, visited, i, parent, n, path, found);
            }
        }

        visited[node] = 0;
        path--;
    }

}
int main(){

    int n;

    cin >> n;

    bool found = 0;

    vector<vector<int>> matrix(n, vector<int>(n));
    vector<bool> visited(n, 0);

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++)
            cin>>matrix[i][j];
    }

    for(int i=0; i<n; i++){
        dfs_search(matrix, visited, i, i, n, 0, found);
        if(found){
            break;
        }
    }
    
    if(found)
        cout<<"YES";
    else
        cout<<"NO";

    return 0;
}

错误分析与修复建议 #

1. 未重置访问标记数组（致命错误） #

每次更换起点搜索时，visited数组没有被重置为初始状态。第一次搜索后，数组中残留的已访问标记会导致后续搜索路径被错误限制，无法遍历所有可能的环。

修复：在main函数的循环中，每次调用DFS前重置visited：

for(int i=0; i<n; i++){
    fill(visited.begin(), visited.end(), false); // 重置所有节点为未访问
    dfs_search(matrix, visited, i, i, n, 0, found);
    if(found){
        break;
    }
}

2. DFS终止条件逻辑错误 #

原代码的终止条件visited[node] && node == parent && path == n完全错误：当访问完n个不同节点时，只需要检查当前节点是否与起点相连即可形成环，无需等到回到起点且节点已被访问（起点在搜索开始时就已标记为访问）。

修复：修改DFS的终止判断逻辑：

void dfs_search(vector<vector<int>> &matrix, vector<bool> &visited, int node, int parent, int n, int path, bool &found){
    if(found)
        return;
    // 已访问完所有n个节点，检查是否能连回起点
    if(path == n){
        if(matrix[node][parent] == 1){
            found = true;
        }
        return;
    }
    if(visited[node])
        return;
    
    visited[node] = true;
    // 遍历所有未访问的邻居节点
    for(int i=0; i < n; i++){
        if(matrix[node][i] == 1 && !visited[i]){
            dfs_search(matrix, visited, i, parent, n, path + 1, found);
        }
    }
    visited[node] = false;
}

同时调整了path的传递方式，直接在递归调用时path + 1，避免在函数内修改path导致的回溯错误。

3. 无效递归调用 #

原代码中会递归访问已标记的节点，导致大量无效搜索，甚至可能干扰正确路径的判断。修复后仅对未访问的邻居进行递归，减少无效操作。

示例输入输出 #

示例输入：
5
0 1 1 0 1
1 0 0 1 1
1 0 0 1 1
0 1 1 0 1
1 1 1 1 0

示例输出：YES

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