普林演算法 (Prim's algorithm)


Prim's algorithm 是以增加節點的觀念做為出發點。

首先以某一節點當作出發點,在與其相連且尚未被選取的節點裡,選擇權重最小的邊, 將新的節點加入。如此重覆加入新節點,直到增加了n - 1條邊為止。(假設有 n 個節點)


  1. 起始。


  2. 假設從 a 開始,相鄰節點的邊有三條 (8, 12, 13),最小的邊為 8。


  3. 我們選擇加入權重為 8 的邊,將節點 c 加進來。
    相鄰節點的邊有四條 (2, 12, 13, 21),最小的邊為 2。


  4. 我們選擇加入權重為 2 的邊,將節點 f 加進來。
    相鄰節點的邊有四條 (7, 12, 13, 21),最小的邊為 7。


  5. 我們選擇加入權重為 7 的邊,將節點 b 加進來。
    相鄰節點的邊有兩條 (13, 32),最小的邊為 13。


  6. 我們選擇加入權重為 13 的邊,將節點 d 加進來。
    相鄰節點的邊有兩條 (9, 32),最小的邊為 9。


  7. 我們選擇加入權重為 9 的邊,將節點 g 加進來。
    相鄰節點的邊有一條 (32),最小的邊為 32。


  8. 我們選擇加入權重為 32 的邊,將節點 e 加進來。


    由於這個graph有7個節點,我們已經新增了6條邊,所以Prim's algorithm完成。
    被選出來的邊為:8, 2, 7, 13, 9, 32。