如何找到朋友团体总数

-3

我想找到的朋友所有可能的组。找到这些分组的最佳算法是什么？例如，在这个图表中，可能的友谊组如下：1,2,3,4,12,13,23,123,14,143,124,1234

如果我使用蛮力算法（从每个顶点开始并执行这4次），它会产生大量重复。

您能否为您的图表数据提供格式？ – 2016-09-28 15:48:13

请注意，最有趣的问题是，如何找到引入最少错误数的线性算法（并定义错误计数函数） – 2016-09-28 15:54:29

@igael我宁愿将它存储为邻接表，因为在大多数图中图可能很稀疏案例。 –

根据Wikipedia这是NP-complete，所以你只能使用蛮力检测这些集合。该问题被称为Clique problem，是第一个确定的NP完全问题之一。

2016-09-28 12:06:22 xenteros

是的，它是NPH。我正在寻找更快的稀疏图算法。 –

http://arxiv.org/abs/1209.5818 – xenteros

谢谢我会检查它 –

回答