Python如何基于共享元素与连通关系对列表数对分组

问题本质 #

这个需求属于无向图的极大团枚举场景：

• 输入的数对列表对应无向图的无向边，数对中的值对应图的节点
• 要求的「完全连通分组」即为图的极大团：分组内任意两个值都存在直接对应的数对（即图中两点有直接边），且无法再加入其他值保持组内全连通的性质，支持同一个值归属多个分组（匹配示例中5、7同时出现在两个分组的重叠特性）。

算法选择 #

采用带主元（Pivot）优化的Bron-Kerbosch回溯算法实现，相比暴力枚举可以通过剪枝跳过大量无效遍历，是目前枚举极大团的主流高效方案，常规规模数据集下性能表现优异。

实现步骤 #

1. 将输入数对转换为邻接集合结构，保证两点连通性判断、集合交集/差集操作的时间效率
2. 运行带Pivot优化的Bron-Kerbosch算法回溯遍历，收集所有极大团
3. 对每个团内元素排序，最终按分组长度降序排列，得到和示例格式一致的结果

代码实现 #

from collections import defaultdict

def cluster_complete_connected_pairs(pair_list):
    # 构建邻接集合与节点全集
    adj = defaultdict(set)
    all_nodes = set()
    for u, v in pair_list:
        adj[u].add(v)
        adj[v].add(u)
        all_nodes.add(u)
        all_nodes.add(v)
    
    cliques = []

    # 带Pivot优化的Bron-Kerbosch回溯逻辑
    def bronk(r, p, x):
        # P和X都为空时，R是极大团
        if not p and not x:
            cliques.append(sorted(r))
            return
        # 选取主元节点，减少递归分支
        pivot_node = next(iter(p.union(x)))
        # 遍历P中不在主元邻居内的节点
        for node in list(p - adj[pivot_node]):
            bronk(
                r.union({node}),
                p.intersection(adj[node]),
                x.intersection(adj[node])
            )
            p.remove(node)
            x.add(node)

    bronk(set(), all_nodes, set())
    # 按分组长度降序排列，匹配示例输出顺序
    cliques.sort(key=lambda x: (-len(x), x))
    return cliques

# 测试用例
L = [[9,3],[3,7],[7,5], [5,3], [9,5], [9,7], [2,5], [7,2], [2,8]]
G = cluster_complete_connected_pairs(L)
print(G)
# 输出: [[3, 5, 7, 9], [2, 5, 7], [2, 8]]，和期望结果完全一致

性能说明 #

• 邻接关系基于集合实现，单元素查询、交集、差集操作均为常数时间复杂度
• Pivot优化可以跳过大量不可能生成极大团的递归分支，稀疏图场景下性能提升尤为明显
• 如果需要处理节点规模过万的超大型图，可以额外叠加退化顺序（Degeneracy Ordering）优化，进一步降低时间复杂度。

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