有没有一种有效的算法来找到“最大连通集”？

Question

给定描述节点对之间连接的布尔值的2D表，是否有一种有效的方法来查找所有节点连接到所有节点的最大节点子集？

6个节点的示例：

在这种情况下，“最大连通集”是{node1，node4，node5}。虽然node0连接到node2和node3，但node2和node3没有连接，所以不要形成“连接集”。

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

如果有帮助，我的目标是重现本文表I中的Mn值：Sarwate，D.V。和M.B. Pursley，“伪随机和相关序列的互相关特性”，Proc。 IEEE，Vol。 68，No。5，May，1980，pp.583-619。

我将在MATLAB中对此进行编码，但我也非常熟悉C / C ++。

编辑：这是我想要重现结果的表格：

• 第1列和第2列在这里并不重要（仅描述代码的长度）。
• 第3列是我所说的“节点数”。
• 如果您使用所有节点（无论它们是否“连接”），第4列都是错误的度量。
• 如果仅使用“最大连接组”，则第6列是（最小）错误。
• 第5列，Mn描述了最大连通集中的节点数。

Answer 1

你的问题等同于 - 实际上，它甚至可以被认为是对图论中最大团问题的重述。图论完全处理你所谈论的结构：连接在一起的节点，称为图形，以及表示它们的一种方法就是你所拥有的，称为邻接矩阵。

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

这个问题是“NP-complete”，它基本上是一类被广泛猜想但未被证明的问题，不能“有效地”解决：特别是，这意味着关于最强有力的猜想。这种具有合理性论据的观点，这些问题至少是指数耗时的。也就是说，至少在一般情况下，你基本上不能只是详尽地搜索你的整个图表。也就是说，对于一个这么小的桌子来说，即使对于家用计算机来说，对所有节点和连接的详尽搜索仍然是基本上即时的，但是在任何超过相对小规模的情况下，即使对于超级计算机也是不可行的。