在无向图中是否存在用于计算所有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}

在实现带有旋转和顶点排序的优化版本时,可以使用相同的思想。

07-24 09:38
查看更多