克魯斯卡爾與PRM
在計算機科學中，Prim和Kruskal的算法是一種貪婪的算法，它為連通加權無向圖尋找最小生成樹。生成樹是圖的子圖，使得圖的每個節點都由一條路徑連接起來，這條路徑就是樹。每棵生成樹都有一個權重，所有生成樹的最小可能權重/代價就是最小生成樹（MST）。
關於Prim算法的更多信息
該算法由捷克數學家Vojtěch Jarník於1930年開發，隨後由計算機科學家robertc.Prim於1957年獨立開發。1959年，埃德斯格爾·迪克斯特拉重新發現了它。該算法可分為三個關鍵步驟；
給定有n個結點的連通圖和每條邊各自的權重，
1從圖中選擇任意節點並將其添加到樹T（將是第一個節點）
2考慮連接到樹中節點的每條邊的權重並選擇最小值。在樹T的另一端添加邊和節點，並從圖中移除邊。（如果存在兩個或多個最小值，請選擇任意一個）
三。重複步驟2，直到n-1條邊添加到樹中。
在這種方法中，樹從一個任意節點開始，並在每個循環中從該節點開始擴展。因此，要使算**常工作，圖必須是連通圖。Prim算法的基本形式具有O（V2）的時間複雜度。
關於克魯斯卡爾算法的更多信息
約瑟夫·克魯斯卡爾（Joseph Kruskal）開發的算法出現在1956年的《美國數學學會會刊》上。克魯斯卡爾的算法也可以用三個簡單的步驟來表達。
給定有n個節點的圖和每條邊各自的權重，
1選擇整個圖中權重最小的弧，添加到樹中並從圖中刪除。
2對於其餘的邊，選擇權重最小的邊，以不形成循環的方式。將邊添加到樹並從圖形中刪除。（如果存在兩個或多個最小值，請選擇任意一個）
三。重複步驟2中的過程。
在該方法中，算法從最小加權邊開始，在每個週期繼續選擇每個邊。因此，在算法中，圖不需要連通。Kruskal算法的時間複雜度為O（logV）
克魯斯卡爾算法和普里姆算法有什麼區別？
•Prim的算法用一個節點初始化，而Kruskal的算法用一個邊初始化。
•Prim的算法從一個節點延伸到另一個節點，而Kruskal算法選擇邊的方式不是基於最後一步。
•在prim算法中，圖必須是連通圖，而Kruskal算法也可以對不連通圖起作用。
