图连通分量识别代码运行结果不符预期，求问题排查

我一眼就看出问题出在你遍历图邻接关系的方式上！这直接导致了连通分量识别错误，让我一步步帮你拆解：

问题根源 #

你的dfs方法里用了这样的循环：

for(int w: g.getEdgeMatrix()[v]) {
    if(!marked[w]) {
        dfs(g, w);
    }
}

如果getEdgeMatrix()返回的是标准邻接矩阵（int[][]类型，matrix[v][w] = 1代表顶点v和w相连，0代表无边），那这个循环遍历的是v行的元素值（也就是0或1），而不是顶点的索引！

举个实际例子：顶点0的邻接行是[0,1,1,0,0]，循环变量w会依次取0、1、1、0、0——这意味着你只会处理顶点0和1，完全漏掉了顶点2！后续构造函数循环走到顶点2时，它还没被标记，就会开启新的连通分量，导致id[2] = 1，以此类推，最终得到错误的0,0,1,2,3。

修复方案 #

你需要修正邻接关系的遍历逻辑，正确识别哪些顶点和当前顶点相连：

方案1：修复邻接矩阵遍历逻辑 #

把dfs方法的循环改成遍历所有顶点索引，判断当前顶点与v是否有边：

public void dfs(Graph g, int v) {
    marked[v] = true;
    id[v] = count;
    int[][] adjMatrix = g.getEdgeMatrix();
    // 遍历所有顶点索引，检查是否与v相连
    for(int w = 0; w < adjMatrix.length; w++) {
        // 存在边且未标记的顶点才递归处理
        if(adjMatrix[v][w] == 1 && !marked[w]) {
            dfs(g, w);
        }
    }
}

方案2：改用邻接表存储（更高效） #

如果你的Graph类支持邻接表（推荐，遍历效率更高），可以新增getAdjacencyList()方法返回List<Integer>[]类型（每个元素是当前顶点的相邻顶点列表），这样原循环逻辑就能正常工作：

public void dfs(Graph g, int v) {
    marked[v] = true;
    id[v] = count;
    // 直接遍历v的所有相邻顶点
    for(int w: g.getAdjacencyList()[v]) {
        if(!marked[w]) {
            dfs(g, w);
        }
    }
}

修复后验证 #

修正后再次运行代码：

• 处理顶点0时，会递归访问1和2，三者的id都会被设为0
• 处理顶点3时，会递归访问4，二者的id都会被设为1
  最终输出就是你预期的0,0,0,1,1。

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