如何在二維平面中找到連接一組座標的最小生成樹？

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. 

現在您可以輕鬆創建一個鄰接地圖/列表，按您的方便，還可以找到相應的權重，並使用你的算法。