极大团查找器

伪代码

Bron-Kerbosch 用三个集合来搜索：R 是目前已构建的团，P 是仍有可能扩充它的候选结点，X 是本层已经尝试过的结点。当且仅当 P 与 X 同时为空时，R 才是一个极大团。

BronKerbosch(R, P, X):
    若 P 与 X 都为空:
        把 R 报告为一个极大团
        返回

    对 P 中的每个结点 v:
        BronKerbosch(R + {v},
                     P 交 邻居(v),
                     X 交 邻居(v))
        P = P - {v}
        X = X + {v}

// 带枢轴：从 P 并 X 中选一个枢轴 u，
// 只对 P 中「不是 u 的邻居」的那些 v 进行分支

X 正是人们最容易省掉的部分，而少了它，算法就会把并非极大的团也报告出来。某个结点一旦在本层被探索过，就会移入 X，于是任何本可以包含它的团都会因不极大而被否决。随后的枢轴优化则大幅削减分支因子：每个极大团都必然包含枢轴或它的某个非邻居，因此对其余结点分支纯属浪费。

分步示例演算

枚举一个含六条边的图的全部极大团，该图由两个相互重叠的三角形和一条悬挂边构成。

示例图: 无向边 A-B、A-C、B-C、B-D、C-D 和 D-E。

1. 开始. R 为空，P 含全部五个结点，X 为空。先对 A 分支。
2. 对 A 分支. R 变为 {A}。P 收缩为 A 的邻居，即 B 与 C。依次对 B、再对 C 分支，构建出 {A, B}，再构建出 {A, B, C}。此时 P 与 X 都为空，因为 D 与 A 不相邻，于是 {A, B, C} 被报告为极大团。
3. 对 B 分支，此时 A 已在 X 中. R 变为 {B}。由于 A 已移入 X，P 收缩为 C 与 D。继续扩充得到 {B, C}，再得到 {B, C, D}，因为 C 与 D 相邻。此处 P 与 X 均为空，因此 {B, C, D} 是极大团。
4. 为什么 {B, C} 不会被报告. 当 R 为 {B, C} 时，D 仍留在 P 中，空集判定不成立，因此不会报告任何团。这正是那项判定的全部意义：{B, C} 是一个团，但不是极大团，因为它同时被 {A, B, C} 与 {B, C, D} 所包含。
5. 那条悬挂边. 在 A、B、C 都已耗尽的情况下一路分支到 D，只剩 E 这一个候选，于是得到 {D, E}。E 再无其他邻居，因此尽管它只有两个结点，也是极大团。

极大团为 {A, B, C}、{B, C, D} 和 {D, E}。最大团（即规模最大的那种）大小为 3，而且有两个。请注意「极大」与「最大」并不相同：{D, E} 是极大团，因为没有任何结点能扩充它，但它离最大差得很远。另外也请注意 B 与 C 各自出现在两个极大团中，这很正常，也解释了为何极大团的数量可能远超结点数。

复杂度及其来源

时间: O(3^(V/3)) · 空间: O(V^2)

这个界来自 Moon-Moser 定理：含 V 个结点的图至多有 3 的 V/3 次方个极大团，而且这个界是紧的，由 V/3 个三角形构成的完全多部图即可达到。既然算法至少要把每个极大团都输出一遍，任何枚举算法在最坏情况下都不可能更快，而带枢轴的 Bron-Kerbosch 恰好达到了这个界。这一点值得内化：算法本身是最优的，但问题本身就是指数级的。仅仅找出最大的那个团就已是 NP 困难，甚至把它近似到任何合理的因子之内也很困难。在实践中，枢轴加上退化度排序能让数万结点规模的真实稀疏图变得可处理，因为稀疏图的极大团数量远少于最坏情况。

何时使用最大团，何时不宜

先想清楚你要的是全部极大团还是仅仅最大的那一个，因为这是两个不同的问题，用的工具也不同。

常见陷阱

• 把集合 X 省掉. 没有 X，算法会报告出所有的团而不只是极大团，于是 {B, C} 会与 {A, B, C} 一同出现。输出会急剧膨胀而且是错的。X 的作用正是记住某个分支已经被覆盖过。
• 把「极大」与「最大」混为一谈. 极大团是无法再扩充的团；最大团是整个图中规模最大的团。例子中的 {D, E} 是极大团、规模为 2，而最大规模是 3。笼统地说「求极大团」是有歧义的，通常指的是最大的那个。
• 在稠密图上不用枢轴. 不带枢轴的纯 Bron-Kerbosch 会多探索极其庞大的分支。在稠密图上，枢轴不是可有可无的优化，而是「能不能跑完」的分水岭。
• 指望它有多项式表现. 极大团的数量可能是结点数的指数级，因此没有任何实现技巧能让一般情形变快。如果图既稠密又庞大，请设定上限枚举，或者重新表述你的问题。
• 把自环或方向当作有意义的信息. 团是针对简单无向图定义的。有向边必须先做对称化处理，并且要决定单向边是否算作相邻，因为这个选择会改变答案。

常见问题

什么是极大团？

团是指一组两两相邻的结点。当无法再加入任何结点而仍保持这一性质时，这个团就是极大团。它不同于最大团，后者是整个图中规模最大的团：每个最大团都是极大团，但一个很小的极大团可以与远大于它的团并存。

Bron-Kerbosch 算法是怎样工作的？

它在三个集合上递归：R 是目前已构建的团，P 是仍能扩充它的候选结点，X 是本层已探索过的结点。每一步把一个候选结点从 P 移入 R，并把 P 与 X 都限制到该结点的邻居上。当 P 与 X 同时为空时，R 就是一个极大团。选取枢轴并只对其非邻居分支，能剪掉搜索中的绝大部分。

极大团与最大团有什么区别？

极大意味着局部不可扩充：你无法再往里加任何结点。最大意味着全局规模最大：图中没有任何团含有更多结点。一个图可能有许多规模各异的极大团，而把它们全部找出来与找出最大的那一个是两个不同的问题。

找出所有极大团的时间复杂度是多少？

最坏情况为 O(3 的 V/3 次方)，而且这是最优的。根据 Moon-Moser 定理，一个图可以含有这么多极大团，因此任何要把它们全部列出的算法至少需要这么长时间。在稀疏图上，退化度排序能给出好得多的实际界。

团有什么用途？

用于社交网络中的社区发现、生物信息学中寻找共表达的基因群、在排程与推荐中识别彼此兼容的元素集合、检测所有成员相互交易的欺诈团伙，以及各类匹配问题，其中一个团代表一组完全自洽的选择。