NetworkX移除非指定集合边结果异常问题排查

现有一个近似树状的图结构，包含1个作为根节点的特殊节点、大量作为叶节点的终端节点，图中存在若干由前置函数生成的冗余小环，需要移除这些环得到标准树结构。
由于路径计算需要使用权重参数，没有其他适配权重的可行方案，因此未选用深度优先搜索，而是通过如下逻辑提取需要保留的边：

• 遍历所有终端节点，调用nx.dijkstra_path计算根节点到对应终端节点的带权最短路径
• 将路径经过的相邻节点转换为边元组存入集合，得到所有遍历过的边集合
  对应实现代码如下：

traversed_edges = set()
for terminal_node in terminal_nodes:
    dijkstra_res = nx.dijkstra_path(graph, root_node, terminal_node, weight="length")
    for n_idx in range(len(dijkstra_res)-1):
        traversed_edges.add((dijkstra_res[n_idx], dijkstra_res[n_idx+1]))

收集完需要保留的边后，最初尝试通过移除未遍历边的方式得到树结构，代码如下：

graph.remove_edges_from(graph.edges - traversed_edges)

该语句可正常执行无报错，但边删除结果看似随机，图结构完全错乱。需要说明的是，当前图中存在大量“伪节点”：这类节点仅用于连接两条边，实际场景中的每一条长连线都由大量首尾相连的短线段构成。
测试时发现一个反常现象：如果直接移除所有已遍历的边，剩余的边恰好是所有待删除的未遍历边，完全符合预期，对应代码如下：

graph.remove_edges_from(traversed_edges)

核心疑问：为何移除已遍历边可以正确得到所有待删除边，但移除边集合的补集反而会导致图结构错乱？

这个问题的根源是无向图边元组的节点顺序不匹配，和伪节点、Dijkstra计算逻辑均无关：

• NetworkX的无向图中，(u, v)和(v, u)是完全等价的同一条边，graph.edges返回边元组时，节点顺序由图内部存储逻辑决定，和添加边时的顺序、Dijkstra路径输出的节点顺序没有强制对齐规则。
• 收集traversed_edges时，边元组是严格按照Dijkstra返回的路径顺序存储的，比如路径为根→节点A→节点B时，存入集合的是(根, A)、(A, B)；但如果graph.edges中这两条边的内部存储顺序是(A, 根)、(B, A)，执行graph.edges - traversed_edges集合差运算时，Python会判定这两个元组不在traversed_edges集合中，将本该保留的边划入待删除集合，最终删除结果错乱。
• 直接调用graph.remove_edges_from(traversed_edges)时结果正确，是因为NetworkX的删边接口本身对无向图做了适配，无论传入的边元组节点顺序如何，都能正确匹配到对应的边执行删除，不会出现顺序不匹配的问题。

修复方案 #

收集保留边时，统一将边元组处理为固定顺序（例如按节点ID大小排序），执行集合运算前也将图中边转换为相同格式，保证匹配逻辑正确：

traversed_edges = set()
for terminal_node in terminal_nodes:
    dijkstra_res = nx.dijkstra_path(graph, root_node, terminal_node, weight="length")
    for n_idx in range(len(dijkstra_res)-1):
        u, v = dijkstra_res[n_idx], dijkstra_res[n_idx+1]
        # 无向图边统一存储为小节点在前、大节点在后的固定格式
        traversed_edges.add((min(u, v), max(u, v)))

# 遍历图中所有边，筛出不在保留集合内的边再执行删除
edges_to_remove = []
for u, v in graph.edges:
    if (min(u, v), max(u, v)) not in traversed_edges:
        edges_to_remove.append((u, v))
graph.remove_edges_from(edges_to_remove)

如果操作的是有向图则不会出现该问题：有向图中(u, v)和(v, u)本身是语义不同的两条边，节点顺序本身有实际意义，集合运算不会出现匹配错误。当前场景中的大量伪节点是长线段拆分出的折点，边的内部存储顺序无固定规律，直接使用路径输出的顺序元组做集合差运算，必然会出现匹配错误。

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