普里姆算法

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

普里姆算法的基本思想是從圖中的一個頂點開始，逐步添加邊和頂點，直到所有頂點都被包含在內。算法在添加每條邊時，總是選擇權值最小的邊，確保最終構建的是最小生成樹。具體步驟如下：

初始化：選擇圖中的一個頂點作為起始點，將其加入集合U中，同時創建一個空集合TE用於存儲最小生成樹的邊。

疊代過程：

在所有U中的頂點與V-U（即非U中的頂點）之間的邊中，選擇權值最小的邊。

將這條邊的另一個頂點（不在U中的頂點）加入到U中，並將這條邊加入到TE中。

結束條件：重複上述過程，直到U中的頂點數等於圖的頂點總數，此時TE中包含了最小生成樹的邊。

普里姆算法的優點是在稠密圖中表現較好，因為它通過避免存儲所有可能的邊來減少記憶體使用。然而，在稀疏圖中，由於需要存儲所有頂點的鄰接信息，其性能可能不如其他算法。

普里姆算法的實現可以通過維護兩個數組來實現：lowcost數組用於存儲從起始頂點到其他頂點的最小權值，adjvex數組用於存儲與最小權值邊相對的頂點。通過這種方式，算法可以高效地找到並加入最小生成樹的邊。

綜上所述，普里姆算法是一種高效、適用於稠密圖的最小生成樹查找算法，其核心思想是通過不斷添加權值最小的邊來構建最小生成樹。