Python中递归查找列表/df内键对关联关系并分组的实现方案

问题本质与方案选择 #

你要实现的是无向图连通分量划分，将所有通过关联关系可连通的节点归为同一分组。500万条量级的数据不推荐用递归实现，递归深度过大会触发栈溢出，优先选择并查集（Disjoint Set Union, DSU） 算法，时间复杂度接近线性，处理千万级数据也能在秒级完成。

完整实现代码 #

from collections import defaultdict

# 并查集核心实现
class DSU:
    def __init__(self):
        self.parent = dict()
    
    def find(self, x):
        if x not in self.parent:
            self.parent[x] = x
        # 路径压缩优化，大幅提升后续查询速度
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            self.parent[ry] = rx

# 你的示例输入数据
df_list = [[5213728 ,7381649],
           [2538095 ,5213728],
           [5213728 ,8163900],
           [3453455 ,3434644]
           ]

# 合并所有关联节点对
dsu = DSU()
for a, b in df_list:
    dsu.union(a, b)

# 按根节点分组，生成最终结果
groups = defaultdict(list)
for node in dsu.parent:
    root = dsu.find(node)
    groups[root].append(node)

result = {idx+1: group for idx, group in enumerate(groups.values())}
print(result)

输出结果 #

完全符合你要求的格式：

{1: [5213728, 7381649, 2538095, 8163900], 2: [3453455, 3434644]}

pandas大表适配方案 #

如果你是从pandas DataFrame读取数据，不需要提前构造masterlist，直接遍历两列做合并即可：

import pandas as pd
df = pd.DataFrame(df_list, columns=['MATCHED_KEY','SKEY'])

dsu = DSU()
# 直接遍历关联对，500万行遍历耗时极低
for a, b in zip(df['MATCHED_KEY'], df['SKEY']):
    dsu.union(a, b)

# 后续分组逻辑和上面完全一致

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