如何在二维平面中找到连接一组坐标的最小生成树？

Question

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

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

Answer 1

这是类的概念将证明有用的地方。

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

例子： -

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. 

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