algorithm - 寻找完全连接的组件？

Question

我不确定我在这里使用的术语是否正确，但是对于完全连接的组件，我的意思是在组件中的每对顶点之间都有一个(无向)边，并且在不破坏它的情况下不能包含其他顶点属性(property)。

虽然有很多算法可以在图中找到强连通分量(例如 Tarjan 算法)，但是否有一种算法可以找到这种“完全连通分量”？

Answer 1

您正在寻找的是图中所有最大派系的列表。它也被称为集团问题。一般无向图不存在已知的多项式时间解。

Most versions of the clique problem are hard. The clique decision problem is NP-complete (one of Karp's 21 NP-complete problems). The problem of finding the maximum clique is both fixed-parameter intractable and hard to approximate. And, listing all maximal cliques may require exponential time as there exist graphs with exponentially many maximal cliques. Therefore, much of the theory about the clique problem is devoted to identifying special types of graph that admit more efficient algorithms, or to establishing the computational difficulty of the general problem in various models of computation.

- https://en.wikipedia.org/wiki/Clique_problem

我也在看同样的问题。

https://en.wikipedia.org/wiki/Bron-Kerbosch_algorithm事实证明这是一种列出它的算法，但是它并不快。如果你的图是稀疏的，你可能想使用算法的顶点排序版本:

For sparse graphs, tighter bounds are possible. In particular the vertex-ordering version of the Bron–Kerbosch algorithm can be made to run in time O(dn3d/3), where d is the degeneracy of the graph, a measure of its sparseness. There exist d-degenerate graphs for which the total number of maximal cliques is (n − d)3d/3, so this bound is close to tight.[6]