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

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}