如何用NetworkX实现图为不相交路径并集的条件判断？

核心判断逻辑 #

一个图是不相交路径的并集，必须满足两个关键条件：

• 所有节点的度数只能是 0、1 或 2（孤立节点度数为0，路径端点度数为1，路径中间节点度数为2）
• 图中不存在环（环的所有节点度数都是2，但环不属于路径范畴）

原代码的问题 #

你的现有实现存在几个致命问题：

• 遍历节点时直接删除边，破坏了原图结构，导致后续路径判断完全失效
• 节点收集和路径拼接逻辑混乱，仅尝试判断两条路径，无法覆盖多个不相交路径的场景
• 未处理孤立节点的情况，也没有排查环的存在

正确实现代码 #

import networkx as nx

def is_disjoint_paths_union(G):
    # 第一步：检查所有节点的度数是否合法
    for node in G.nodes():
        degree = G.degree(node)
        if degree not in {0, 1, 2}:
            return False
    
    # 第二步：遍历每个连通分量，逐一校验是否为路径或孤立节点
    for component in nx.connected_components(G):
        subgraph = G.subgraph(component)
        # 孤立节点直接通过校验
        if len(subgraph) == 1:
            continue
        # 路径必须有且仅有2个度数为1的端点
        degree_list = [subgraph.degree(node) for node in subgraph.nodes()]
        if degree_list.count(1) != 2:
            return False
        # 路径不能是环，所以要检查连通分量是否无环
        if nx.is_cyclic(subgraph):
            return False
    return True

代码说明 #

1. 度数前置检查：直接过滤掉度数不符合0/1/2的节点，快速排除不符合条件的图
2. 连通分量校验：对每个连通分量单独判断：
   • 孤立节点无需额外检查
   • 非孤立分量必须严格符合路径的端点特征（2个度数为1的节点）
   • 通过无环校验，避免把环误判为路径

测试示例 #

# 测试1：两个不相交路径组成的图
G1 = nx.Graph()
G1.add_path([1,2,3])
G1.add_path([4,5])
print(is_disjoint_paths_union(G1))  # 输出True

# 测试2：包含环的图
G2 = nx.Graph()
G2.add_cycle([1,2,3])
print(is_disjoint_paths_union(G2))  # 输出False

# 测试3：包含孤立节点和路径的图
G3 = nx.Graph()
G3.add_path([1,2])
G3.add_node(3)
print(is_disjoint_paths_union(G3))  # 输出True

# 测试4：存在度数为3节点的图
G4 = nx.Graph()
G4.add_edges_from([(1,2), (1,3), (1,4)])
print(is_disjoint_paths_union(G4))  # 输出False

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