依次计算图中k个顶点的所有派系

Question

是否存在一个连续算法计算全部 k-cliques在无向图中？

对于k-cliques，我的意思是：无向图中所有由边连接的顶点集的数目。

下面是在哪里可以找到更详细的描述。 https://en.wikipedia.org/wiki/Clique_(graph_theory)

Answer 1

您可以使用Bron–Kerbosch algorithm列出图中的所有派系。考虑其siplest实现（维基百科伪代码）：

BronKerbosch1(R, P, X): 
    if P and X are both empty: 
     report R as a maximal clique 
    for each vertex v in P: 
     BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v)) 
     P := P \ {v} 
     X := X ⋃ {v} 

在每次递归调用，设定R包含拉帮结派，同时通过图中的所有派系迭代。因此，只要其大小为k，您就可以修改算法以打印该派系并切割递归，因为任何递归调用只会产生较大的派系。

BronKerbosch1(R, P, X, k): 
    if |R| = k: 
     report R as a k-clique 
    else 
     for each vertex v in P: 
      BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v)) 
      P := P \ {v} 
      X := X ⋃ {v} 

在实现具有旋转和顶点排序的优化版本时，您可以使用相同的想法。