Prim’s Algorithm

另一種找到最小生成樹(Minimum Spanning Tree)的方法。

＊個人認為跟Kruskal’s Algorithm最不一樣的地方是，Prim’s 需要先有一個起始點，而Kruskal’s 是直接找最小邊(Edge)。

Prim’s Algorithm的步驟：

1. 隨機取一個點(Vertex)作為初始開始的起點。

2. 之後找尋此起點周圍最小的「邊(Edge)」，且取的邊不能形成Cycle(loop)。

3. 繼續延續連接後的點。

4. 重複步驟2，直到最後已經找不到邊可以取。

為了更詳細的說明，這邊也放了許多圖片，請大家耐心觀看。

下面圖片有很多圈圈，這邊做個簡單的說明。

綠色圈圈：可能的邊

黃色圈圈：最小的邊

紅色圈圈：新延伸到的點(Vertex)

圖例：

這邊的概念也是蠻容易了解的，之後有時間再把程式碼放上來。

希望有上述的解釋，大家也可以更快的理解Prim’s Algorithm的運作原理。我們下次再見～～