如何用NetworkX查找有向图的半连通（单向连通）分量？

NetworkX确实没有内置函数直接返回单向连通分量（极大单向连通子图），但针对你提到的**无环图（DAG）**场景，可以通过以下方式实现需求，得到你示例中的结果：

核心思路 #

在DAG中，极大单向连通子图等价于最长简单路径（无法再延长的路径），因为这类路径中的任意两个节点都满足单向可达（前面的节点能到达后面的节点），且无法添加其他节点保持单向连通性。孤立节点本身就是长度为1的极大路径。

代码实现 #

import networkx as nx

def find_maximal_semiconnected_paths(G):
    # 收集孤立节点（无入边也无出边）
    isolated_nodes = [node for node in G.nodes() if G.degree(node) == 0]
    maximal_components = [[node] for node in isolated_nodes]
    
    # 标记已被包含在极大路径中的节点
    covered = set(isolated_nodes)
    
    # 按拓扑序遍历节点（确保路径起点在前）
    topo_order = list(nx.topological_sort(G))
    
    for start_node in topo_order:
        if start_node in covered:
            continue
        
        # 找到以当前节点为起点的所有最长路径
        longest_paths = []
        max_path_length = 0
        for path in nx.all_simple_paths(G, source=start_node):
            path_len = len(path)
            if path_len > max_path_length:
                max_path_length = path_len
                longest_paths = [path]
            elif path_len == max_path_length:
                longest_paths.append(path)
        
        # 去重相同节点序列的路径
        unique_paths = []
        seen_paths = set()
        for path in longest_paths:
            path_tuple = tuple(path)
            if path_tuple not in seen_paths:
                seen_paths.add(path_tuple)
                unique_paths.append(path)
        
        # 添加结果并标记节点为已覆盖
        for path in unique_paths:
            maximal_components.append(path)
            covered.update(path)
    
    return maximal_components

# 构造你的示例图
G = nx.DiGraph()
G.add_edges_from([('A', 'B'), ('B', 'C'), ('A', 'E'), ('E', 'F')])
G.add_nodes_from(['X', 'Y'])

# 获取结果
components = find_maximal_semiconnected_paths(G)
print(components)

输出结果 #

运行上述代码后，会得到：

[['X'], ['Y'], ['A', 'B', 'C'], ['A', 'E', 'F']]

完全符合你需要的格式，且保留了节点的先后顺序（拓扑序）。

说明 #

1. 拓扑序遍历：确保我们从路径的起点开始处理，避免重复处理已经被包含在更长路径中的节点。
2. 最长路径筛选：只保留无法延长的路径，这些路径就是极大单向连通子图。
3. 去重处理：避免因多条路径对应同一节点序列而产生重复结果。
4. 孤立节点处理：直接将无连接的节点作为单独分量。

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