Python：大规模好友关系图的连通分量分组优化问题

你需要解决的是无向图的连通分量划分问题：把所有直接或间接互为好友的用户归为同一组。针对6000万级别的数据规模，原方法的内存和效率都存在瓶颈，而且提取唯一集合时因为set不可哈希报错，下面给出最优解决方案和问题修复思路。

最优方案：并查集（Union-Find） #

并查集是专门处理这类连通性问题的高效算法，时间复杂度接近线性，内存占用低，非常适合大规模数据。

并查集实现代码 #

class UnionFind:
    def __init__(self, elements):
        self.parent = {elem: elem for elem in elements}
        self.rank = {elem: 0 for elem in elements}
    
    def find(self, x):
        # 路径压缩，加速后续查找
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        # 按秩合并，避免树结构退化
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return
        if self.rank[x_root] < self.rank[y_root]:
            self.parent[x_root] = y_root
        else:
            self.parent[y_root] = x_root
            if self.rank[x_root] == self.rank[y_root]:
                self.rank[x_root] += 1

# 示例好友字典
friends = {
    'aaron': {'john'},
    'bob': {'john'},
    'amy': {'gael', 'joe'},
    'gael': {'amy'},
    'joe': {'amy', 'patrick'},
    'john': {'aaron', 'bob'},
    'patrick': {'joe'}
}

# 收集所有用户节点
all_users = set(friends.keys())
for friends_set in friends.values():
    all_users.update(friends_set)

# 初始化并查集
uf = UnionFind(all_users)

# 遍历所有好友关系，执行合并操作
for user, friend_list in friends.items():
    for friend in friend_list:
        uf.union(user, friend)

# 按根节点分组生成结果
groups = {}
for user in all_users:
    root = uf.find(user)
    groups.setdefault(root, set()).add(user)

# 转换为集合的集合格式
result = set(frozenset(group) for group in groups.values())
print(result)

大规模数据适配优化 #

• 动态添加节点：不需要提前收集所有用户，遍历好友字典时若节点未在并查集中，直接初始化即可
• 整数ID优化：如果用户用整数ID标识，可改用列表存储parent和rank，大幅降低内存开销
• 分批处理：数据量过大时，可分批次加载好友关系到内存中执行合并，避免内存溢出

原方法的问题与修复 #

报错原因 #

set是可变类型，不具备哈希性，无法直接添加到另一个set中。要解决这个问题，可将set转为不可变的frozenset，它支持哈希操作。

修复后的代码（仅适合小规模数据） #

# 原合并逻辑执行后
groups = set()
for n in friends:
    groups.add(frozenset(friends[n]))

print(groups)

但该方法完全不适用于6000万级数据：

• 集合update操作会产生大量内存拷贝，内存占用呈指数级增长
• 嵌套遍历的时间复杂度极高，处理大规模数据会出现严重超时

总结 #

针对千万级别的数据规模，并查集是唯一可行的高效方案，它通过路径压缩和按秩合并保证了近乎线性的时间复杂度，内存占用也远低于直接合并集合的方法。

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