如何修改Bron-Kerbosch算法按团大小输出分组团列表或字典

原算法输出所有团的集合列表，现在需要按团的大小对结果进行分组，以下提供两种实现方式：

一、输出嵌套列表形式（按团大小升序排列） #

嵌套列表中，外层列表的每个元素对应一个团大小的组，内层列表包含该大小的所有团（团内节点按升序排列，保证输出一致性）。

# 定义示例邻接矩阵
adj_matrix = [
    [0, 1, 0, 0, 1, 0],
    [1, 0, 1, 0, 1, 0],
    [0, 1, 0, 1, 0, 0],
    [0, 0, 1, 0, 1, 1],
    [1, 1, 0, 1, 0, 0],
    [0, 0, 0, 1, 0, 0]
]

# 构建邻接表N
N = {
    i: set(num for num, j in enumerate(row) if j)
    for i, row in enumerate(adj_matrix)
}

def BronKerbosch1(P, R=None, X=None):
    P = set(P)
    R = set() if R is None else R
    X = set() if X is None else X
    if not P and not X:
        yield R
    while P:
        v = P.pop()
        yield from BronKerbosch1(
            P=P.intersection(N[v]), R=R.union([v]), X=X.intersection(N[v]))
        X.add(v)

# 获取所有团并转换为排序后的列表（消除集合无序性）
all_cliques = [sorted(clique) for clique in BronKerbosch1(N.keys())]

# 按团大小分组
clique_groups = {}
for clique in all_cliques:
    size = len(clique)
    if size not in clique_groups:
        clique_groups[size] = []
    clique_groups[size].append(clique)

# 转换为嵌套列表（按团大小升序排列）
nested_list = [clique_groups[size] for size in sorted(clique_groups.keys())]
print(nested_list)
# 输出: [[[1, 2], [2, 3], [3, 4], [3, 5]], [[0, 1, 4]]]

二、输出字典形式 #

字典的键为团大小的字符串（或整数），值为对应大小的所有团列表（团内节点按升序排列）。

# 沿用上述邻接矩阵、N和BronKerbosch1函数

# 获取所有团并转换为排序后的列表
all_cliques = [sorted(clique) for clique in BronKerbosch1(N.keys())]

# 构建按大小分组的字典
clique_dict = {}
for clique in all_cliques:
    size = len(clique)
    key = str(size)  # 若需要整数键，直接使用size即可
    if key not in clique_dict:
        clique_dict[key] = []
    clique_dict[key].append(clique)

print(clique_dict)
# 输出: {"2": [[1, 2], [2, 3], [3, 4], [3, 5]], "3": [[0, 1, 4]]}

说明 #

• 将集合形式的团转换为排序后的列表，是为了避免集合无序性导致的输出结果不稳定问题。
• 分组逻辑通过遍历所有团，根据团的长度将其归入对应分组，实现简单高效。

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