依次計算圖中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} 

在實現具有旋轉和頂點排序的優化版本時，您可以使用相同的想法。