# Prim's Algorithms (Minimum Spanning Tree)

## 解法

1. 隨機選點開始
2. 比較生成樹已連接的所有邊，取最小的（如最小邊有重複，隨機選擇即可），且不能形成環，直到所有邊都已經訪問完成為止

## 優先隊列 （最小堆）

Prim's Algorithms 可以使用最小堆來加快尋找最小生成樹的進程，利用最小堆來對邊的權重做排序，每次從最小堆中取出節點（取出的節點即為最小權重），如果沒有訪問過該節點的話，加入到最小生成樹中，且把節點所有尚未訪問節點加入到最小堆中，持續這一過程直到所有節點都被訪問，即完成此圖的最小生成樹

## 參考資料

[3.5 Prims and Kruskal algorithms - Greedy Method](https://www.youtube.com/watch?v=4ZlRH0eK-qQ)
[Prims minimum spanning tree (Geeks for Geeks)](https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/)