在社交网络中寻找密切关系的算法（图论）

Question

我需要编写一个算法，给定一个用图表示的社交网络，找出一组人 X 是否形成 亲密关系。这意味着X中的每个人都彼此有关系。

例如，如果我们有图表：

集合{H,B,O}形成了亲密的友谊，因为子图中的每个人都相互联系。

集合 {O,F,K} 不存在，因为我们不能从 O 到 F

这个特定算法的伪代码是什么样的？

Answer 1

您要搜索的是Clique。

Bron-Kerbosch算法会为您找到

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}