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

Question

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

例如，如果我们有图表：

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

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

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

标签： algorithmdata-structuresgraph-theory

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}