使无向图连通的算法

Question

很抱歉，如果已经有问题问这个，但我找不到与这个特定问题相关的任何内容。我有一组定义的节点，我想从中创建一个无向的、连接的图。我也有一组连接这些节点的边，但我不能保证这些边的集合会使图连接起来。我的情况示例如下所示。

仔细检查会发现，根据我的边，节点集实际上是三个图。我想做的是找到一种方法来确定可以添加到我的边列表中的边，以使其成为一个连通图。最好，我想添加尽可能少的边(即，我不想通过添加所有可能的边来解决问题)。雪上加霜的是，我不想添加与其他边交叉的边(每个节点都有一个定义的位置)。

Answer 1

可以高效地找到连接的组件(例如，如 u_seem_surprised 所述)。这会导致列出所有可能的连接链接。不幸的是，这个列表很长——任何一个组件中的任何节点都可以连接到任何其他节点，甚至连哪个组件最适合连接都不是很明显。要从这个长长的列表中找到满足您的非交叉要求的链接并不容易。

我怀疑对于这类混合问题没有任何已知的最优算法。相反，我建议您尝试一些自然启发法。

最好的启发式方法将取决于您的问题的特征(例如，组件少而节点多，或者相反)。但这里有一个我正在考虑的启发式方法的可能示例。

要找到连接任意两个相连组件的节点，我建议您首先尝试从组件 A 中离组件 B 的质心最近的节点。我认为这可以使用空间索引有效地完成。然后您可以尝试将该节点连接到组件 B 中最近的节点，再次使用索引。

检查两个链接是否交叉的算法非常简单。

要决定连接哪些组件，我想你可以尝试这样的事情:

创建一个新图，其中每个组件的质心都有一个节点。向新图形添加一个全网格，其链接长度等于质心之间的距离。在这个新图上找到这些质心之间的最小生成树。现在沿着最小生成树连接组件。

但是，此算法可以告诉您连接无法连接的组件(例如，想象一个由三个同心组件组成的图形 - 您将无法将外部连接到内部)。所以这只能是一个启发式的建议。

将一个组件始终连接到具有最近节点的另一个组件可能会更好。