如何在无重复节点的前提下，找出最大化大团节点数的团集合

核心需求 #

找出无重复节点的团集合，且优先让尽可能多的节点被纳入大团（即优先选择规模大的团，再用剩余节点构建后续团）

示例输入 #

Item 1
2,3,4,5,6

Item 2
1,3

Item 3
1,2,7

Item 4
1,5,6

Item 5
1,4,6,9,12

Item 6
1,4,5,3

Item 7
3

期望输出 #

• 大团：[1,4,5,6]
• 剩余节点组成的团：[2,3] 或 [3,7]（二选一即可，节点不能重复）

现有实现及问题 #

当前使用NetworkX获取所有极大团的代码如下：

G=nx.Graph()
G.add_edges_from(pairs)
max_cliques = list(nx.find_cliques(G))

但nx.find_cliques()会返回所有极大团（无法再添加任何节点的团），这些团之间存在大量重复节点，无法直接得到无重复节点且优先大团的目标集合。

解决方案思路 #

要实现需求，需在所有极大团的基础上做筛选取舍：

1. 将所有极大团按规模从大到小排序，优先处理节点数多的团
2. 维护一个已使用节点的集合，遍历排序后的团：
   • 若当前团的所有节点都未被使用，则将该团加入结果集合，并标记这些节点为已使用
   • 若团中有部分节点已被使用，则跳过该团
3. 遍历结束后，结果集合即为满足要求的无重复节点、优先大团的团集合

以示例为例：

• 所有极大团包括[1,4,5,6]、[1,2,3]、[3,7]、[5,9]、[5,12]等
• 按规模排序后，[1,4,5,6]（4个节点）是最大的，先选中它，标记节点1、4、5、6为已使用
• 剩余未使用节点为2、3、7、9、12，次大团[1,2,3]因节点1已被使用被跳过；后续[3,7]或[2,3]的节点均未被使用，二选一即可；9和12只能单独成团（示例期望输出未包含，因需求优先大团，剩余单个节点可按需处理）

代码实现示例 #

import networkx as nx

# 构建示例图的边集合
pairs = [
    (1,2), (1,3), (1,4), (1,5), (1,6),
    (2,3),
    (3,7),
    (4,5), (4,6),
    (5,6), (5,9), (5,12),
    (6,3)
]

G = nx.Graph()
G.add_edges_from(pairs)

# 获取所有极大团并按规模降序排序
max_cliques = list(nx.find_cliques(G))
max_cliques_sorted = sorted(max_cliques, key=lambda x: len(x), reverse=True)

used_nodes = set()
result = []

for clique in max_cliques_sorted:
    clique_nodes = set(clique)
    # 如果当前团和已使用节点无交集
    if clique_nodes.isdisjoint(used_nodes):
        result.append(clique)
        used_nodes.update(clique_nodes)

print("满足要求的团集合：")
for c in result:
    print(c)

运行上述代码，输出会包含[1,4,5,6]，以及[3,7]或[2,3]（取决于极大团排序后的遍历顺序，两者均为合法结果）

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