algorithm - 是否有一种有效的算法来找到 "maximal connected set"？

Question

给定一个描述节点对之间连接的 bool 值的二维表，是否有一种有效的方法来找到最大的节点子集，其中所有节点都连接到所有节点？

具有 6 个节点的示例:

在这种情况下，“最大连通集”是{node1, node4, node5}。 node0虽然与node2和node3相连，但是node2和node3不相连，所以不构成“连通集”。

这是一个小例子，但我对原则上可以应用于非常大的表的通用算法很感兴趣。

如果有帮助，我的目标是重现本文表 I 中的 M_n 值:Sarwate、D.V. 和 M.B. Pursley，“伪随机和相关序列的互相关特性”，Proc。 IEEE，卷。 68，第 5 期，1980 年 5 月，第 583-619 页。

我将在 MATLAB 中对此进行编码，但我也相当流利地使用 C/C++。

编辑:这是我要从中重现结果的表格:

• 第一列和第二列在这里并不重要(只描述代码的长度)。
• 第 3 列是我所说的“节点数”。
• 如果您使用所有节点(无论他们是否“连接”)。
• 如果仅使用“最大连通集”，第 6 列是(最小)误差。
• 第 5 列，M_n 描述了最大连通集中的节点数。

Answer 1

您的问题等同于 - 事实上，它甚至可以被视为图论中的最大团问题的重述。图论恰好处理您正在谈论的结构:连接在一起的节点，称为图，表示它们的一种方法是上面的方法，称为邻接矩阵。

“最大团”正是您所描述的:图形节点的最大子集，每个节点都相互连接。

这个问题是“NP-complete”，基本上是一整类被广泛推测但未被证明的问题，无法“有效”解决:特别是，这意味着关于最强的以这种方式做出的猜想，具有合理性论据，这些问题至少呈指数级耗时。也就是说，至少在一般情况下，您基本上不能比仅详尽地搜索整个图表做得更好。也就是说，对于这么小的一张 table ，即使对于家用计算机来说，对所有节点和连接的详尽搜索基本上仍然是即时的，但如果超过相对较小的规模，即使对于 super 计算机来说也是不可行的。