最大团搜索算法
前置知识：团
引入
在计算机科学中，团问题指的是在给定的图中找到团（顶点的子集，都彼此相邻，也称为完全子图）的计算问题．
团的问题在现实生活中也有体现．例如我们考虑一个社交网络，其中图的点代表用户，图的边代表其所连接的两个用户互相认识．那么我们找到了一个团，也就找到了一群互相认识的人．
我们如果想要找到这个社交网络中最大的一群互相认识的人，那么就需要用到最大团搜索算法．
我们已经介绍了 极大团 的概念，最大团指的是点数量最多的极大团．
解释
想法是利用递归和回溯，用一个列表存储点，每次加入点进来都检查这些点是否仍在一个团中．如果加入进来这个点后就无法还是一个团了，就回溯到满足条件的位置，重新加入别的点．
采用回溯策略的原因是，我们并不知道某个顶点 𝑣v
最终 是否是最大团中的成员．如果递归算法选择 𝑣v 作为最大团的成员时，并没有找到最大团，那么应该回溯，并查找最大团中没有 𝑣v 的解．
过程
Bron–Kerbosch 算法对于这种想法进行了优化实现．它的基础形式是通过给定三个集合：𝑅R、𝑃P、𝑋X 来递归地进行搜索．步骤如下：
- 初始化集合 𝑅,𝑋R,X 分别为空，集合 𝑃P 是图中所有点的集合．
- 每次从集合 𝑃P 中取顶点 𝑣v，当集合中没有顶点时，有两种情况：
- 集合 𝑅R 是最大团，此时集合 𝑋X 为空
- 无最大团，此时回溯
- 对于每一个从集合 𝑃P 中取得的顶点 𝑣v，有如下处理：
- 将顶点 𝑣v 加到集合 𝑅R 中，之后递归集合 𝑅,𝑃,𝑋R,P,X
- 从集合 𝑃P 中删除顶点 𝑣v，并将顶点 𝑣v 添加到集合 𝑋X 中
- 若集合 𝑃,𝑋P,X 都为空，则集合 𝑅R 即为最大团
此方法也可继续优化．为了节省时间让算法更快的回溯，可以通过设定关键点（pivot vertex）来进行搜索．另一种优化思路是在开始时把所有点排序，枚举时按照下标顺序，防止重复．
实现
伪代码
---|---
### C++ 实现
实现代码
---|---
例题
题目大意：给出 𝑛n 个人，其中有 𝑚m 对朋友，求最大团数量．
思路：模版题，要用 Bron–Kerbosch 算法
伪代码：
---|---
为了节省时间和让算法更快的回溯，我们可以通过设定关键点（pivot vertex）𝑣v 进行优化．
我们知道在上述的算法中必然有许多重复计算之前计算过的极大团，然后回溯的过程．
以前文提到的 𝑅R、𝑃P、𝑋X 三个集合为例：
我们考虑如下问题，取集合 𝑃 ∪𝑋P∪X 中的一个点 𝑢u，要与 𝑅R 集合构成极大团，那么取的点必然是 𝑃 ∩𝑁(𝑢)P∩N(u) 中一个点（𝑁(𝑢)N(u) 代表与 𝑢u 相邻的点）．
如果取完 𝑢u 之后我们再取与 𝑢u 相邻的点 𝑣v 也能加入到极大团，那么我们只取 𝑢u 就好了．这样做可以减少之后对 𝑣v 的重复计算．我们之后只需要取与 𝑢u 不相邻的点．
加入优化后的 C++ 代码实现：
实现代码
---|---
习题
参考资料
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Persdre, Tiphereth-A, Great-designer, HeRaNO, iamtwz, Marcythm, Menci, shuzhouliu 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用