如何查找连接 2D 平面中一组坐标的最小生成树

Question

我已经用python编写了Prim的算法，但这需要带有节点和边的加权图作为输入，这不是我所拥有的。

如何将给定的坐标转换为图形，以便程序可以接受输入，并获得有意义的答案？

Answer 1

这就是类的概念应该被证明有用的地方。

创建一个坐标类，并将节点和边存储为该类的实例。 将__sub__方法添加到坐标类，以便获取两个坐标之间的权重（距离或您想要的权重）。

例：-

class Coordinate:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def __sub__(self, other):
        return (self.x - other.x)**2 + (self.y - other.y)**2
        # No need to square root to compare distances.

现在，您可以根据自己的方便轻松创建邻接地图/列表，还可以找到相应的权重并使用您的算法。