algorithm - 如何找到所有点之间的最短连接？

Question

有二维数组，上面标有点 - 就像第一张图片一样。我要做的是找到该地图上所有点之间的连接（这样你就可以从任何点旅行到所有其他点）。所有边的长度之和必须可能最小。

输入：

(0, 0) (5, 5) (5, 1) (4, 4) (1, 5) (2, 4) (2, 1) // 1st,2nd,3rd city ...

输出：

1-7, 7-3, 7-6, 6-5, 6-4, 4-2

Answer 1

将输入的点集视为完全连接的图，将一对点之间的距离作为边权重。然后找到图的最小生成树。

Kruskal 的算法特别简单：

• 从输出图中没有边开始。
• 按权重顺序遍历输入图的每条边，最小的在前。
  • 如果这两个顶点还不是输出图中同一棵树的一部分，则将边添加到输出图中。

如果速度是一个问题，您可以使用各种技术来使其非常快。