以最小总距离连接所有点的算法

Question

我有一组点和适用于每对点的距离函数。我想将所有点连接在一起，总距离最小。您知道我可以为此使用的现有算法吗？

每个点都可以链接到几个点，所以这不是通常的“推销员行程”问题:)

谢谢!

Answer 1

你想要的是一个Minimum spanning tree .

生成一个的两种最常见的算法是:

• Prim's algorithm
• Kruskal's algorithm