有向图连通性判定疑问：.NET C#中不连通图的划分逻辑

问题本质：连通性定义的差异 #

你遇到的划分分歧，核心在于有向图中"连通分量"有两种完全不同的定义标准，不同的代码逻辑对应不同的标准：

• 弱连通分量（WCC）：忽略边的方向，将图视为无向图。只要节点之间存在路径（不管方向），就属于同一分量。这和你的视觉判断一致，所以(A,B,C,D)、(E,F)会被划分为两个分量。
• 单向可达遍历：部分代码只做正向出边遍历——从一个节点出发，只沿着它指向的边（出边）遍历可达节点，完全不处理指向它的边（入边）。这种逻辑下：
  • 从A出发能遍历到B、C，但无法反向遍历到D（因为D→B，但没有边从B指向D）；
  • 从D出发只能遍历到B，但如果代码是按"未访问节点启动遍历"的逻辑，当处理D时，B已经被标记为已访问，所以D会被单独划分为一个分量；
    最终就会得到(A,B,C)、(D)、(E,F)的结果。

技术实现方案 #

1. 弱连通分量划分（匹配视觉预期） #

要实现符合你视觉判断的划分，需要把有向图当作无向图处理，同时遍历入边和出边。具体步骤：

• 构建双向邻接表：对每个节点，同时存储它的出边（指向的节点）和入边（指向它的节点）；
• 用DFS或BFS遍历所有节点，对每个未访问节点，遍历其所有相邻节点（不管入/出边），标记为同一分量。

以下是C#实现代码片段：

// 构建双向邻接表：每个节点的相邻节点包含入边和出边的关联节点
var bidirectionalAdj = new Dictionary<string, List<string>>
{
    {"A", new List<string> { "B", "C" }},
    {"B", new List<string> { "A", "D" }},
    {"C", new List<string> { "A" }},
    {"D", new List<string> { "B" }},
    {"E", new List<string> { "F" }},
    {"F", new List<string> { "E" }}
};

var visited = new HashSet<string>();
var components = new List<List<string>>();

foreach (var node in bidirectionalAdj.Keys)
{
    if (!visited.Contains(node))
    {
        var queue = new Queue<string>();
        queue.Enqueue(node);
        visited.Add(node);
        var currentComponent = new List<string> { node };

        while (queue.Count > 0)
        {
            var current = queue.Dequeue();
            foreach (var neighbor in bidirectionalAdj[current])
            {
                if (!visited.Contains(neighbor))
                {
                    visited.Add(neighbor);
                    currentComponent.Add(neighbor);
                    queue.Enqueue(neighbor);
                }
            }
        }

        components.Add(currentComponent);
    }
}

// 输出结果：[A,B,C,D]、[E,F]
foreach (var comp in components)
{
    Console.WriteLine($"分量：{string.Join(", ", comp)}");
}

2. 强连通分量划分（业务需要双向可达场景） #

如果你的业务逻辑要求节点之间必须双向可达（比如检测环状依赖、权限闭环），则需要使用强连通分量算法（如Tarjan算法、Kosaraju算法）。在你的示例图中，所有节点都无法双向可达，所以每个节点会被划分为单独的强连通分量，这显然不是你当前场景需要的。

3. 规避错误的单向遍历逻辑 #

你遇到的错误划分，本质是代码逻辑不适合划分独立图结构——这种单向出边遍历只适合计算"从某个起点出发的可达节点集合"，而非划分整个图的独立连通部分。

选择依据 #

• 若需要视觉上的"同一图"划分（仅关注节点是否连通，不关心边的方向），优先使用弱连通分量；
• 若业务要求节点之间必须双向可达，使用强连通分量；
• 仅在计算特定节点的可达范围时，才使用单向出边遍历。

内容的提问来源于stack exchange，提问作者Wild-Programmer