普利姆算法

普利姆算法（Prim算法）是一種在加權連通圖中查找最小生成樹的算法。該算法於1930年由捷克數學家沃伊捷赫·亞爾尼克發現，並在1957年由美國計算機科學家羅伯特·普里姆獨立發現。因此，普里姆算法有時也被稱為DJP算法、亞爾尼克算法或普里姆-亞爾尼克算法。

普利姆算法的基本思想是貪心策略，其過程可以概括為：

初始化：選擇圖中的一個頂點作為起始點，並將其加入到已訪問的頂點集合U中。同時，將起始點與所有其他頂點的邊作為候選邊集合。

疊代過程：

從候選邊集合中找到權值最小的邊(u, v)，其中u屬於已訪問頂點集合U，v屬於未訪問頂點集合V-U。

將頂點v加入到U中，並將邊(u, v)加入到最小生成樹的邊集合中。

更新候選邊集合，移除已經訪問過的頂點的邊。

重複上述步驟，直到所有頂點都被訪問過。

結束：最終得到的就是圖的最小生成樹。

普利姆算法的時間複雜度為O(ElogV)，其中E是邊的數量，V是頂點的數量。這是因為算法需要遍歷所有的邊，並對每條邊進行權值比較。在實際套用中，如果邊的數量遠大於頂點的數量，普利姆算法的效率會更高。