如何从二维邻接矩阵中识别相互连接的节点分组（连通分量）

核心思路 #

你要实现的功能本质是无向图的连通分量提取，不需要自行处理边的重复问题，通过标记已访问节点的方式就能天然避免重复分组，常用的实现方案有深度优先搜索(DFS)、广度优先搜索(BFS)、并查集(DSU)三种，这里先给出最容易理解的DFS实现方案。

实现逻辑 #

1. 用一个布尔数组记录每个节点是否已经被划分到分组中，避免重复处理
2. 遍历所有节点，每遇到一个未访问的节点，就以此为起点遍历所有和它连通的节点，组成一个独立分组
3. 遍历过程中标记所有已访问的节点，保证每个节点只会属于一个分组

完整C#代码示例 #

using System.Collections.Generic;

public static class GraphGroupHelper
{
    // 输入为二值化后的邻接矩阵，输出为所有分组，每个分组存储对应节点的索引
    public static List<List<int>> GetConnectedGroups(double[,] adjMatrix)
    {
        int nodeCount = adjMatrix.GetLength(0);
        bool[] visited = new bool[nodeCount];
        List<List<int>> groups = new List<List<int>>();

        for (int i = 0; i < nodeCount; i++)
        {
            if (!visited[i])
            {
                List<int> currentGroup = new List<int>();
                Dfs(i, adjMatrix, visited, currentGroup);
                groups.Add(currentGroup);
            }
        }

        return groups;
    }

    // 深度优先遍历，收集所有连通节点
    private static void Dfs(int currentNode, double[,] adjMatrix, bool[] visited, List<int> currentGroup)
    {
        // 标记当前节点已访问，加入当前分组
        visited[currentNode] = true;
        currentGroup.Add(currentNode);

        int nodeCount = adjMatrix.GetLength(0);
        // 遍历所有节点，找到和当前节点连通且未访问的节点
        for (int j = 0; j < nodeCount; j++)
        {
            if (adjMatrix[currentNode, j] != 0 && !visited[j])
            {
                Dfs(j, adjMatrix, visited, currentGroup);
            }
        }
    }
}

代码使用说明 #

• 你只需要将已经二值化的邻接矩阵传入GetConnectedGroups方法，返回的列表中每个子列表就是一个独立分组，不会出现重复分组、反向分组的问题
• 比如你描述的示例场景，返回结果就是[[0,1,2,3,4], [5,6,7], [8,10], [9]]（假设节点索引按a1-a5、b1-b6顺序排列）
• 如果需要存储节点的其他信息，只需要将List<int>改成你需要的结构，通过索引去取对应原始数据即可

原有代码问题说明 #

你之前的实现只是记录了所有连通的边，没有处理连通关系的传递性（比如A连B、B连C的场景下，不会自动把A、B、C归为同一组），同时没有做去重标记，所以才会出现重复边、无法提取分组的问题。

大数据量优化方案（并查集） #

如果你的节点数量超过1000，推荐使用并查集实现，时间复杂度更低，实现思路如下：

1. 初始化每个节点的父节点为自身
2. 遍历邻接矩阵的上三角部分（i<j，避免重复处理边），如果两个节点连通就合并两个节点的集合
3. 所有边处理完成后，按父节点分组即可得到所有连通分量

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