最小生成樹使用Kruskal算法

Question

我使用Kruskal算法來完成確定後問題的最小生成樹的分配：

我有個城市，而這一切都必須連接。我可以通過在它們之間修建道路或建造一個機場來連接它們。當我在城市建造一個機場時，它會連接到所有其他有機場的城市。

我的疑問是，在未來的要求：

在不止一個最佳的解決方案的情況下，我必須選擇一個具有較少的機場。我如何以最有效的方式保證這一點？

Answer 1

在kruskal算法中，我們按照權重的非遞減順序對邊進行排序和選擇。

讓我們說我們使用數據結構（類似元組）來存儲邊緣爲<source vertex,destination vertex, weight of edge between them>。我們按照權重的非遞減順序對邊進行排序和選擇。

現在遇到多個最佳解決方案時，您更青睞機場較少的解決方案。因此，如果目標頂點（城市）有機場，請在數據結構中再添加一個字段（如boolean）。這應該看起來像<source vertex,destination vertex, weight of edge between them, has_destination_an_airport>。 has_destination_an_airport是true如果目的地頂點（城市）有一個機場，否則false。現在，當我們按照其權重的非遞減順序對邊進行排序時，如果權重相同，那麼優先考慮沒有機場的那個，即，如果可能，has_destination_an_airport是false。

綜上所述，正確執行comparator來進行排序的邊緣會做到神奇。

就時間和空間的漸近複雜性而言，它與克魯斯卡爾算法的相同。只有額外的空間才能記住目的地頂點是否有機場，這是微不足道的。