在无向图中是否存在用于计算所有k个团的序贯算法?
对于k-团,我的意思是:在无向图中,所有顶点都通过边相互连接的集合的数目。
这里有一个更详细的描述一个集团。https://en.wikipedia.org/wiki/Clique_(graph_theory)
最佳答案
您可以使用Bron–Kerbosch algorithm在图表中列出所有集团。考虑一下它的siplest实现(来自wikipedia的伪代码):
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
包含一个团,同时遍历图中的所有团。因此,您可以更改算法以在团大小小于cc>时打印团,并剪切递归,因为任何递归调用都只会生成更大的团。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}
在实现带有旋转和顶点排序的优化版本时,可以使用相同的思想。