基于DFS实现无向图连通分量查找时输出异常的问题排查

问题描述 #

我正在尝试实现一个能够将离散图的所有连通分量以二维vector数组返回的程序，编写的代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

void checkConnected(int** edges, int n, int s,int* visited, vector<int> &v) {
    v.push_back(s);
    visited[s] = 1;
    for(int i=0; i<n; i++) {
        if(s == i) {
            continue;
        }
        if(!visited[i] && edges[s][i] == 1) {
            checkConnected(edges,n,i,visited,v);
        } 
    }
}

void returnAllConnected(int** edges, int n, int st ,vector<vector<int>> &ans, int* visited) {
    vector<int> v;
    checkConnected(edges,n,st,visited,v);
    ans.push_back(v);
    v.clear();
    for(int i=0; i<n; i++) {
        if(visited[i] == 0) {
            returnAllConnected(edges,n,i,ans,visited);
            break;
        }
    }
}

int main() {
    int n,e;
    cin>>n>>e;
    int** edges = new int*[n];
    for(int i=0; i<n; i++) {
        edges[i] = new int[n];
        for(int j=0; j<n; j++) {
            edges[i][j] = 0;
        }
    }
    int s,d,w;
    for(int i=0; i<e; i++) {
        cin>>s>>d>>w;
        edges[s][d] = w;
        edges[d][s] = w;
    }
    
    int* visited = new int[n];
    for(int i=0; i<n; i++) {
        visited[i] = 0;
    }
    
    vector<vector<int>> ans;
    returnAllConnected(edges,n,0,ans,visited);
    
    for(int i=0; i<ans.size(); i++) {
        for(int j=0; j<ans[i].size(); j++) {
            cout<<ans[i][j]<<" "; 
        }
        cout<<endl;
    }
    
    for(int i=0; i<n; i++) {
        delete[] edges[i];
    }
    delete[] edges;
    delete[] visited;
    return 0;
}

问题表现 #

当前代码实际输出为每个顶点单独占一行，预期输出应为每个连通分量的顶点为一行，预期输出如下：

0 1
2 3
4 5 6

使用的测试输入：

7 4
0 1
2 3
4 5
5 6

错误原因排查 #

• 核心错误出在边输入读取逻辑：你的测试输入每行仅包含边的起点、终点两个整数，但代码中读取边时用了cin>>s>>d>>w，多读取了一个不存在的权重参数，导致输入流完全错位，邻接矩阵中边的赋值全部出错，DFS遍历时找不到相邻节点，因此每个节点都被识别为独立的连通分量。
• 次要优化点：你提取的是无权图的连通分量，不需要读取权重，直接将邻接矩阵对应位置赋值为1即可。

修复方案 #

将main函数中读取边的代码段：

int s,d,w;
for(int i=0; i<e; i++) {
    cin>>s>>d>>w;
    edges[s][d] = w;
    edges[d][s] = w;
}

修改为：

int s,d;
for(int i=0; i<e; i++) {
    cin>>s>>d;
    edges[s][d] = 1;
    edges[d][s] = 1;
}

修改后运行即可得到预期输出。

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