Python如何同时分割多个非连续列表将图拆分为连通子图

我有两个存储图边信息的列表，相同索引位置的两个元素分别代表边的起点和终点：例如第0位元素表示节点0连接到节点1，第1位元素表示节点1连接到节点2，以此类推。
两个列表内容如下：

list1 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 46, 48, 49, 50, 51, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 47, 52, 47]

list2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 47, 49, 50, 51, 52, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 48, 53, 53]

上述边列表对应的不是单个连通网络，而是多个独立的连通子图：例如节点45和46之间不存在连接（list1中元素44连接list2中元素45，但list1中不存在元素45连接list2中元素46的边），因此需要在断点处切割列表，拆分出独立的子图。

我最初编写的拆分代码如下：

edge_index = [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 46, 48, 49, 50, 51, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 47, 52, 47], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 47, 49, 50, 51, 52, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 48, 53, 53]]

origins_split = edge_index[0]
dest_split = edge_index[1]

list_of_graph_nodes = []
list_of_origin_edges = []
list_of_dest_edges = []

graph_nodes = []
graph_nodes.append(origins_split[0])
graph_nodes.append(dest_split[0])

graph_edge_origin = []
graph_edge_origin.append(origins_split[0])

graph_edge_dest = []
graph_edge_dest.append(dest_split[0])

for o,d in zip(origins_split[1:],dest_split[1:]): #change
    if o in graph_nodes:
        graph_edge_origin.append(o)
        graph_edge_dest.append(d)
        if d not in graph_nodes:
            graph_nodes.append(d)

    elif d in graph_nodes:
        graph_edge_origin.append(o)
        graph_edge_dest.append(d)
        if o not in graph_nodes:
            graph_nodes.append(o)

    else:
        list_of_graph_nodes.append(graph_nodes)
        list_of_origin_edges.append(graph_edge_origin)
        list_of_dest_edges.append(graph_edge_dest)

        
        graph_nodes = []
        graph_edge_dest = []
        graph_edge_origin = []
        graph_nodes.append(o)
        graph_nodes.append(d)
        graph_edge_origin.append(o)
        graph_edge_dest.append(d)

print(list_of_graph_nodes)
print(list_of_origin_edges)
print(list_of_dest_edges)

预期输出为两个连通子图对应的节点列表、边起点列表、边终点列表，但实际运行时将本属于同一连通子图的46、47、48、52、53等节点错误拆分为多个独立小图，例如47、48被单独拆分，结果不符合预期。

原有代码的核心逻辑错误在于默认边是按连续顺序排列的，遇到当前边两个节点都不在已遍历的节点集合中时，就直接判定为新的连通子图。但实际边列表中属于同一个子图的边可能不连续排列：例如边(46,47)之后先出现了(48,49)到(82,83)的长序列边，之后才出现连接47和48的边(47,48)，原有代码遇到(48,49)时会错误判定为新子图，后续再遇到连接两个已拆分“子图”的边时也没有合并逻辑，最终导致同一连通子图被拆成多个碎片。

使用并查集（Disjoint Set Union, DSU）数据结构实现连通分量查找，这是无向图连通子图拆分的标准实现，不受边排列顺序影响，逻辑稳定可靠。
修复后的完整代码如下：

from collections import defaultdict

# 原始边数据
edge_index = [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 46, 48, 49, 50, 51, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 47, 52, 47], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 47, 49, 50, 51, 52, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 48, 53, 53]]
origins = edge_index[0]
dests = edge_index[1]

# 并查集实现
parent = {}
def find(u):
    if parent[u] != u:
        parent[u] = find(parent[u])
    return parent[u]
def union(u, v):
    root_u = find(u)
    root_v = find(v)
    if root_u != root_v:
        parent[root_v] = root_u

# 初始化所有节点，合并所有边的连通关系
for o, d in zip(origins, dests):
    if o not in parent:
        parent[o] = o
    if d not in parent:
        parent[d] = d
    union(o, d)

# 按连通分量根节点分组
components = defaultdict(lambda: {"nodes": set(), "edge_origins": [], "edge_dests": []})
for o, d in zip(origins, dests):
    root = find(o)
    components[root]["nodes"].add(o)
    components[root]["nodes"].add(d)
    components[root]["edge_origins"].append(o)
    components[root]["edge_dests"].append(d)

# 输出结果
list_of_graph_nodes = []
list_of_origin_edges = []
list_of_dest_edges = []
for comp in components.values():
    list_of_graph_nodes.append(list(comp["nodes"]))
    list_of_origin_edges.append(comp["edge_origins"])
    list_of_dest_edges.append(comp["edge_dests"])

# 打印验证
print("各连通子图节点列表：", list_of_graph_nodes)
print("各连通子图边起点列表：", list_of_origin_edges)
print("各连通子图边终点列表：", list_of_dest_edges)

代码运行后会正确拆分出2个连通子图：

• 第一个子图包含节点0-45，对应从0到45的连续链路
• 第二个子图包含节点46-83，覆盖了原本被错误拆分的46、47、48、52、53等所有节点，完全符合预期。

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