如何找到所有点之间的最短连接？
如何找到所有点之间的最短连接？
提问于 2013-01-14 02:04:46
这是一个二维数组，上面标有点--就像第一张图片一样。我要做的是找到地图上所有点之间的连接(这样你就可以从任何点旅行到所有其他点)。所有边的长度之和必须尽可能最小。
输入：
(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回答 1
Stack Overflow用户
回答已采纳
发布于 2013-01-14 02:14:30
将输入点集合视为一个完全连接的图，将两个点之间的距离作为边权重。然后找出图的最小生成树。
Kruskal的算法特别简单：
- 从输出图形中没有边开始。
- 按照权重的顺序遍历输入图形的每条边，最小的在前面。如果两个折点还不是输出图中同一棵树的一部分，则向输出graph.
添加边
如果速度是个问题，您可以使用各种技术来快速完成此任务。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/14306474
复制相关文章
相似问题
腾讯云开发者
