Bron-Kerbosch 算法介绍

本文由 ChatGPT 翻译。原文。

在计算机科学中，Bron-Kerbosch算法是一种用于在无向图中寻找所有极大团的枚举算法。也就是说，它列出了所有满足以下两个条件的顶点子集：这些子集中的每对顶点都通过一条边连接，且在保持完全连通性的前提下，任何一个子集都无法再添加顶点。该算法由荷兰科学家Coenraad Bron和Joep Kerbosch设计，并于1973年发表。

尽管理论上有其他算法在仅有少数极大独立集的输入上运行时间更优，但在实际应用中，Bron-Kerbosch算法及其后续改进通常被认为比其他算法更高效。它广泛应用于图算法的各个领域，如计算化学中。

Akkoyunlu（1973年）提出的一个同时期算法，虽然表述方式不同，但可以被视为与Bron-Kerbosch算法相同，因为它生成了相同的搜索树。

无枢轴版本

Bron-Kerbosch算法的基本形式是一个递归回溯算法，用于搜索给定图G中的所有极大团。更一般地，它处理三个不相交的顶点集合R、P和X，找到包含所有R中的顶点、部分P中的顶点、且不包含任何X中的顶点的极大团。在算法的每次调用中，P和X是不相交的集合，它们的并集包含所有与R中每个顶点相连的顶点。换句话说，P ∪ X是所有与R中的每个顶点相连的顶点集合。当P和X都为空时，不能再向R中添加顶点，R就是一个极大团，算法输出R。

递归调用的初始状态是R和X为空集，P为图的顶点集。在每次递归调用中，算法依次考虑P中的每个顶点；如果没有这样的顶点，它要么报告R为一个极大团（如果X为空），要么回溯。对于从P中选出的每个顶点v，算法会进行递归调用，在该调用中，v被添加到R中，同时P和X被限制为v的邻居集N(v)，以找到并报告所有包含v的R的团扩展。然后，v从P移动到X中，以排除它在后续团中的考虑，并继续处理P中的下一个顶点。

伪代码如下：

算法 BronKerbosch1(R, P, X) 
    如果P和X都为空 
        报告R为极大团
    对于P中的每个顶点v
        BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
        P := P \ {v}
        X := X ⋃ {v}

有枢轴版本

上述算法的基本形式在具有大量非极大团的图中效率低下：它为每个团（不论是否为极大团）都进行递归调用。为了节省时间，并允许算法在不包含极大团的搜索分支中更快回溯，Bron和Kerbosch引入了一种变体算法，涉及一个从P中（或更一般地，如后来研究者发现，从P ⋃ X中）选择的“枢轴顶点”u。然后，u的邻居不会被递归测试。任何通过测试u的邻居而找到的极大团，也会在测试u或其非邻居之一时被找到，因为这些非邻居之一至少总会是该极大团的一部分。否则，只有u的邻居会是该极大团的一部分，从而可以通过将u添加到团中来扩展团，这与该团为极大团相矛盾。因此，在每次递归调用中，只有u及其非邻居需要作为顶点v的候选项，并将其添加到R中进行测试。伪代码如下：

算法 BronKerbosch2(R, P, X) 
    如果P和X都为空 
        报告R为极大团
    选择P ⋃ X中的枢轴顶点u
    对于P \ N(u)中的每个顶点v
        BronKerbosch2(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
        P := P \ {v}
        X := X ⋃ {v}

如果选择枢轴时尽量减少算法所做的递归调用次数，与无枢轴版本相比，运行时间上的节省可能显著。

带顶点排序的版本

另一种优化Bron-Kerbosch算法基本形式的方法是在最外层递归时不使用枢轴，而是通过仔细选择递归调用的顺序来最小化每次递归调用中候选顶点集P的大小。

图G的退化度是使得G的每个子图都有一个度数不超过d的顶点的最小值d。每个图都有一个退化顺序，即按顺序排列的顶点，使得每个顶点在该顺序中比它靠后的顶点邻居数不超过d。可以通过反复选择剩余顶点中度数最小的顶点，在线性时间内找到一个退化顺序。如果Bron-Kerbosch算法在循环处理顶点v时按照退化顺序进行，那么每次调用中的候选顶点集P（v的后续邻居）大小最多为d，而排除顶点集X将由v的所有较早邻居组成，可能远大于d。在递归调用的顶层以下，仍可以使用带枢轴的版本。伪代码如下：

算法 BronKerbosch3(G) 
    P = V(G)
    R = X = 空集
    对于G的一个退化顺序中的每个顶点v
        BronKerbosch2({v}, P ⋂ N(v), X ⋂ N(v))
        P := P \ {v}
        X := X ⋃ {v}

这一算法变体可以被证明对退化度较小的图是高效的，实验表明它在大规模稀疏社交网络和其他现实世界的图中也表现良好。