如何快速识别并合并重叠集合？保留字典键优先级

问题概述 #

需要处理存储集合的字典，核心需求如下：

• 合并所有存在交集的集合，最终得到完全无交集的离散集合
• 必须保留字典键的优先级顺序：最终结果只保留每个连通分量中最早出现的键
• 现有方案处理数十万级数据时性能不足，优先考虑原生Python或pandas/numpy实现，第三方包需评估引入成本

示例说明 #

初始字典 #

d = {'b': {'b', 'f', 'a'},
     'x': {'x'},
     's': {'s'},
     'a': {'a', 'f', 'e'},
     'e': {'e'},
     'f': {'f'},
     'z': {'x', 'z'},
     'g': {'g'}}

合并中间状态（所有相交集合统一为同一连通分量） #

{
    'b': {'a', 'b', 'e', 'f'},
    'x': {'x', 'z'},
    's': {'s'},
    'a': {'a', 'b', 'e', 'f'},
    'e': {'a', 'b', 'e', 'f'},
    'f': {'a', 'b', 'e', 'f'},
    'z': {'x', 'z'},
    'g': {'g'}
}

最终结果（保留每个连通分量的首个出现键） #

{'b': {'a', 'b', 'e', 'f'}, 'x': {'x', 'z'}, 's': {'s'}, 'g': {'g'}}

高效实现方案：并查集（Union-Find） #

并查集是处理连通分量问题的最优数据结构，时间复杂度接近线性，适合大规模数据处理。核心思路：

1. 为每个元素建立父节点映射，通过路径压缩优化查找和合并操作
2. 遍历字典中的所有集合，将集合内的元素合并到同一连通分量
3. 建立根节点到对应元素集合的反向映射
4. 按原字典的键顺序筛选，保留每个连通分量的首个出现键

代码实现 #

def merge_intersecting_sets(input_dict):
    # 初始化并查集父节点映射
    parent = {}

    def find(u):
        # 路径压缩：优化查找效率
        while parent[u] != u:
            parent[u] = parent[parent[u]]
            u = parent[u]
        return u

    def union(u, v):
        # 合并两个元素所在的连通分量
        u_root = find(u)
        v_root = find(v)
        if u_root != v_root:
            parent[v_root] = u_root

    # 第一步：为所有元素初始化父节点，并合并每个集合内的元素
    for s in input_dict.values():
        elements = list(s)
        if not elements:
            continue
        # 取集合第一个元素作为基准，合并所有元素
        base = elements[0]
        if base not in parent:
            parent[base] = base
        for elem in elements[1:]:
            if elem not in parent:
                parent[elem] = elem
            union(base, elem)

    # 第二步：建立根节点到对应元素集合的映射
    root_to_elements = {}
    for elem in parent:
        root = find(elem)
        if root not in root_to_elements:
            root_to_elements[root] = set()
        root_to_elements[root].add(elem)

    # 第三步：按原字典顺序筛选，保留每个连通分量的首个键
    seen_roots = set()
    result = {}
    for key, s in input_dict.items():
        if not s:
            result[key] = set()
            continue
        # 取集合任意元素查找根节点
        elem = next(iter(s))
        root = find(elem)
        if root not in seen_roots:
            seen_roots.add(root)
            result[key] = root_to_elements[root]

    return result

# 测试示例
d = {'b': {'b', 'f', 'a'},
     'x': {'x'},
     's': {'s'},
     'a': {'a', 'f', 'e'},
     'e': {'e'},
     'f': {'f'},
     'z': {'x', 'z'},
     'g': {'g'}}

print(merge_intersecting_sets(d))

性能说明 #

• 并查集的find和union操作经路径压缩优化后，时间复杂度接近O(nα(n))，其中α是阿克曼函数的反函数，增长极慢，几乎可视为常数
• 该实现的性能远优于传统逐一遍历比对方案，可轻松处理数十万级数据集

可选：pandas辅助实现（适合结构化数据） #

如果输入字典的集合元素是结构化数据，可借助pandas快速构建元素映射：

import pandas as pd

def merge_with_pandas(input_dict):
    # 将字典转换为元素-键的映射表
    data = []
    for key, s in input_dict.items():
        for elem in s:
            data.append({'elem': elem, 'key': key})
    df = pd.DataFrame(data)

    # 初始化并查集
    parent_map = {elem: elem for elem in df['elem'].unique()}

    def find(u):
        while parent_map[u] != u:
            parent_map[u] = parent_map[parent_map[u]]
            u = parent_map[u]
        return u

    def union(u, v):
        u_root = find(u)
        v_root = find(v)
        if u_root != v_root:
            parent_map[v_root] = u_root

    # 合并每个键对应的元素
    for key in input_dict:
        elems = input_dict[key]
        if len(elems) <= 1:
            continue
        base = next(iter(elems))
        for elem in elems:
            union(base, elem)

    # 映射根节点到元素集合
    df['root'] = df['elem'].apply(find)
    root_groups = df.groupby('root')['elem'].apply(set).to_dict()

    # 按原顺序筛选首个键
    seen_roots = set()
    result = {}
    for key in input_dict:
        elems = input_dict[key]
        if not elems:
            result[key] = set()
            continue
        root = find(next(iter(elems)))
        if root not in seen_roots:
            seen_roots.add(root)
            result[key] = root_groups[root]
    return result

最终输出 #

运行示例代码后，将得到符合要求的结果：

{'b': {'a', 'b', 'e', 'f'}, 'x': {'x', 'z'}, 's': {'s'}, 'g': {'g'}}

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