上的圖像

在Python實施Kruskal的算法的電網定義了使用存儲在兩個陣列邊緣的圖像：上的圖像

h[x][y]給出了從x,y到x+1,y
v[x][y]邊的權重給出了從x,y邊緣權重x,y+1

我正在嘗試實現Kruskal的算法。這很簡單 - 我可以找到implementations online並複製它們。問題在於處理邊緣。特別;排序他們很混亂。

是否有更好的方法來存儲這個採集的邊緣？我希望他們從每個像素到相鄰的像素。我將圖像存儲爲i [x] [y]，邊緣權重只是圖像值之間的差異。

2013-02-01 eha

有什麼不對存儲陣列原樣？你能否解釋一下你的缺點，以便我們可以嘗試找到解決這個問題的解決方案？ – templatetypedef

考慮使用networkx。 http://networkx.lanl.gov/_modules/networkx/algorithms/mst.html。但對於你的問題，你可以實現你的容器作爲元組（源，目標，成本）或類，字典，namedtuple ....然後按成本排序這些列表，並添加到你的聯合查找數據結構（確保使用路徑壓縮和按等級結合）一旦源，dest就沒有相同的代表 – locojay

你需要做的是創建一個所有邊的列表，然後對它們進行排序。要做到這一點，你需要定義一個類邊緣：

class Edge: 
    def x 
    def y 
    def direction 
    def weight

然後，解析h和v矩陣，建立了edges列表。最後，它應該有2 * N * M元素。邊緣的方向應該是'h'或'v'，具體取決於您解析的矩陣。

如果您沒有將h和v矩陣用於任何其他目的，您可以將它們全部刪除，因爲您可以直接從i矩陣計算邊的權重。

最後，對於算法的目的，您需要使用的重量爲準則，以列表進行排序：

edges.sort(key=weight)

來源

2013-02-01 23:32:59 Spatarel

回答

相關問題