介紹
該算法由捷克數學家VojtěchJarník[1]於1930年開發，後來由計算機科學家Robert C. Prim於1957年和Edsger W. Dijkstra於1959年重新發表並重新發表。因此，它有時也被稱為DJP算法，Jarník算法，Prim-Jarník算法，或Prim-Dijkstra算法。
針對這個問題的其他眾所周知的算法包括Kruskal算法和Borůvka算法。這些算法在可能下線的圖中找到最小生成林;相比之下，Prim算法的最基本形式只能在連通圖中找到最小生成樹。但是，對於圖的每個連線組件單獨運行Prim算法，它也可以用於查找最小生成林。就漸近時間複雜度而言，這三種算法對稀疏圖同樣快，但比其他更複雜的算法慢。但是，對於足夠密集的圖形，Prim的算法可以線上性時間內運行，滿足或改善其他算法的時間範圍。
描述
該算法可以非正式地描述為執行以下步驟：
1、初始化具有單個頂點的樹，從圖中任意選擇。
2、通過一條邊生長樹：將樹連線到樹中尚未到達的頂點的邊，找到最小權重邊，並將其傳遞給樹。
3、重複步驟2（直到所有頂點都在樹中）。
更詳細地，它可以遵循下面的偽代碼來實現。
1、將圖的每個頂點v與數字C [v]（連線到v的最便宜的成本）和邊緣E [v]（提供最便宜的連線的邊緣）相關聯。要初始化這些值，請將C [v]的所有值設定為+∞（或任何大於最大邊緣權重的數字），並將每個E [v]設定為一個特殊的標誌值，表示沒有邊緣連線v到更早的頂點。
2、初始化空森林F和尚未包含在F中的頂點集Q（最初，所有頂點）。
3、重複以下步驟，直到Q為空：
a.從Q中查找並刪除具有最小可能值C [v]的頂點v
b.將v添加到F，如果E [v]不是特殊標誌值，也將E [v]添加到F
c.環繞邊緣vw連線v到其他頂點w。對於每個此類邊緣，如果w仍屬於Q且vw的權重小於C [w]，請執行以下 步驟：
將C [w]設定為邊緣vw的成本
將E [w]設定為指向邊緣vw。
4、返回F.
如上所述，算法的起始頂點將被任意選擇，因為算法主循環的第一次疊代將在Q中具有一組頂點，它們都具有相等的權重，並且算法將自動啟動一個新的樹。 F當它完成輸入圖的每個連通分量的生成樹時。可以通過將C [s]設定為小於C的其他值（例如，零）來修改算法以從任何特定頂點開始，並且可以將其修改為僅查找單個生成樹而不是整個生成森林（更接近於非正式描述）通過在遇到標記為沒有關聯邊的另一個頂點時停止。
算法的不同變化在如何實現集合Q方面彼此不同：作為簡單的鍊表或頂點陣列，或作為更複雜的優先權佇列數據結構。該選擇導致算法的時間複雜度的差異。通常，優先權佇列將以更低的成本更快地找到頂點v，但是當C [w]的值改變時將需要更昂貴的更新。
時間複雜度
Prim算法的時間複雜度取決於用於圖形的數據結構以及按權重排序邊緣，這可以使用優先權佇列來完成。下表顯示了典型的選擇：
| 最小邊緣權重數據結構 | 時間複雜度（總計） |
| 鄰接矩陣，搜尋 | O(|V|) |
| 二進制堆和鄰接列表 | O(|V| + |E| log |V|) |
| Fibonacci堆和鄰接列表 | O(|E| + |V| log |V|) |
Prim的簡單實現，使用鄰接矩陣或鄰接列表圖表示併線性搜尋權重數組以找到要添加的最小權重邊緣，需要O（| V | 2）運行時間。但是，通過使用堆來實現在算法的內循環中找到最小權重邊緣，可以進一步大大提高運行時間 。
第一個改進版本使用堆來存儲輸入圖的所有邊，按其權重排序。這導致O（| E | log | E |）最壞情況運行時間。但是存儲頂點而不是邊緣可以進一步改善它。堆應該按照最小邊權重對頂點進行排序，將它們連線到部分構造的最小生成樹（MST）中的任何頂點（如果不存在這樣的邊，則為無窮大）。每次選擇頂點v並將其添加到MST時，對部分MST外部的所有頂點執行減小鍵操作，使得v連線到w，將鍵設定為其先前值的最小值和邊緣成本（v，w）。
使用簡單的二進制堆數據結構，可以顯示Prim的算法在時間O（| E | log | V |）中運行，其中| E |是邊數和| V |是頂點的數量。使用更複雜的Fibonacci堆，可以將其降低到O（| E | + | V | log | V |），當圖形足夠密集時，它會漸近地更快。是|ω（| V |），| E |時的線性時間至少是| V | log | V |。對於密度更大的圖形（對於某些c> 1至少具有| V | c邊緣），通過使用d-ary堆代替Fibonacci堆，可以使Prim的算法更簡單地線上性時間內運行。
證明
設P是連通的加權圖。在Prim算法的每次疊代中，必須找到一條邊，將子圖中的頂點連線到子圖外的頂點。由於P是連通的，所以每個頂點都會有一條路徑。 Prim算法的輸出Y是樹，因為添加到樹Y的邊和頂點是連線的。令Y1為圖P的最小生成樹。如果Y1 = Y則Y是最小生成樹。否則，設e是構造不在樹Y1中的樹Y期間添加的第一條邊，而V是由邊e之前添加的邊連線的頂點集。然後，邊e的一個端點在集合V中，而另一個端點不在集合V中。由於樹Y1是圖P的生成樹，因此在樹Y1中存在連線兩個端點的路徑。當沿著路逕行進時，必須遇到將集合V中的頂點連線到不在集合V中的頂點的邊緣f。在邊緣e被添加到樹Y的疊代中，邊緣f也可以被添加並且如果它的重量小於e，它將被添加而不是邊e，並且由於沒有添加邊f，我們得出結論：
普林姆算法令樹Y2是通過從樹Y1移除邊緣f並將邊e添加到樹Y1而獲得的圖。 很容易證明樹Y2是連通的，具有與樹Y1相同的邊數，並且其邊緣的總權重不大於樹Y1的總重量，因此它也是圖P的最小生成樹並且它 在構造集合V期間，包含邊e和在它之前添加的所有邊。重複上述步驟，我們最終將得到圖P的最小生成樹，它與樹Y相同。這表示Y是最小生成樹。 最小生成樹允許子區域的第一子集擴展為更小的子集X，我們假設它是最小的。
