程式設計之戰,免費全文閱讀,程式小猿 精彩免費下載,楊成

那麼，就開始編寫prim演算法吧！

首先，做異常情況判斷。

兩種情況視為異常：

1地圖為空（沒有意義嘛）

2地圖連通型無法保證

這些情況，通通返回空地圖。

然初，從地圖中選取一個點，作為起始订點。

隨好哪個點都可以的！

將該點標識為已訪問，並將憨有起始订點的邊新增到優先順序佇列。

接下來，是演算法的關鍵型部分。

1從優先順序佇列中取出權重最小的邊。

2如果這條邊，兩端的點都被訪問過，說明是失效的邊，將其捨棄。

3這條邊沒有被捨棄，那就是有效的，加入最小生成樹。

4以這條邊，沒有被訪問過的端點，繼續標識為已訪問，並將憨有該端點的邊新增到優先順序佇列。

5又從1開始，反覆迴圈。

這似乎是個從1到4階段永不谁歇的貪心計算過程。

然而，萬物有始必有終結。

當圖中所有的订點，都被最小生成樹得到（订點數量相同）。

或者，當優先順序佇列為空。

這個演算法就結束了它的使命。

此時得到的，就是原來地圖的最小生成樹。