基于DFS实现邻接矩阵两顶点路径计数的代码存在疑问求解答

API 探路者

2026-9-24

现有代码存在的问题

visited数组缺少回溯逻辑：你在进入节点时将visited[i]设为1，但遍历完该节点的所有邻接节点后没有将其重置为0，会导致同一个节点无法出现在多条不同路径中，大量合法路径会被漏统计。
计数逻辑错误：当前通过上层节点累加子节点返回的成功次数实现计数，仅能正确统计长度为2的路径，路径长度超过2后计数结果会出现偏差；且匹配到终点时没有直接累加计数，逻辑链路冗余且易出错。
边界情况未处理：没有考虑起点s和终点d为同一个节点的场景，此时正确结果应为1（空路径），但现有代码会返回0。
visited数组未初始化：每次调用countPath时没有重置全局visited数组，多次调用函数时上一次的标记会干扰本次统计结果。

修正后的实现代码

第一步：修正countPath函数

void countPath(int s,int d){
    // 每次调用先重置visited数组
    memset(visited, 0, sizeof(visited));
    int count = 0;
    // 处理起点等于终点的边界情况
    if(s == d){
        cout << 1 << endl;
        return;
    }
    visited[s] = 1; // 标记起点已访问
    for (int i = 0; i < V;i++){
        if(visited[i]==0 && adj_mat[s][i]==1){
            cout << s << " ";
            searchForNode(i, d, &count);
        }
    }
    cout << count << endl;
}

第二步：修正searchForNode函数

void searchForNode(int i,int k,int *c){
    // 匹配到终点直接计数
    if(i==k){
        cout << "f" << i << endl;
        *c = *c + 1;
        return;
    }
    visited[i] = 1;
    cout << i << " ";
    for (int j = 0; j < V;j++){
        if(visited[j]==0 && adj_mat[i][j]==1){
            searchForNode(j,k,c);
        }
    }
    // 回溯：当前节点所有分支遍历完成后重置访问标记
    visited[i] = 0;
}