DSA 普里姆演算法
普里姆演算法由捷克數學家 Vojtěch Jarník 於 1930 年發明。
該演算法隨後由 Robert C. Prim 於 1957 年重新發現，並由 Edsger W. Dijkstra 於 1959 年重新發現。因此，該演算法有時也被稱為“Jarník 演算法”或“Prim-Jarník 演算法”。
普里姆演算法
普里姆演算法在一個連通的無向圖中尋找最小生成樹 (MST)。
普里姆演算法找到的 MST 是圖中所有頂點連線在一起的邊的集合，且邊的權重總和最小。
普里姆演算法透過首先將一個隨機頂點新增到 MST 來找到 MST。然後，演算法查詢當前 MST 中權重最低的頂點，並將其新增到 MST。普里姆演算法不斷重複此過程，直到所有節點都包含在 MST 中。
普里姆演算法是貪心演算法，它有一種簡單的方法來建立一個最小生成樹。
要使普里姆演算法正常工作，所有節點都必須是連通的。要查詢非連通圖的 MST，可以使用 Kruskal 演算法。下一頁將介紹 Kruskal 演算法。
工作原理
- 選擇一個隨機頂點作為起點，並將其包含為 MST 中的第一個頂點。
- 比較從 MST 發出的邊。選擇連線 MST 頂點和 MST 外部頂點的權重最低的邊。
- 將該邊和頂點新增到 MST。
- 重複步驟 2 和 3，直到所有頂點都屬於 MST。
注意：由於起始頂點是隨機選擇的，因此同一圖可能包含不同的 MST 邊，但 MST 的總邊權重仍然具有相同的最小值。
手動演練
讓我們手動執行普里姆演算法，以便在嘗試程式設計之前理解詳細的步驟。
普里姆演算法從隨機頂點開始生長最小生成樹 (MST)，但在此演示中，頂點 A 被選為起始頂點。
從頂點 A 開始，MST 沿著權重最低的邊生長。因此，頂點 A 和 D 現在屬於屬於最小生成樹的頂點組。
一個 parents 陣列是普里姆演算法生長 MST 邊方式的核心。
此時，parents 陣列看起來像這樣
parents = [-1, 0, -1, 0, 3, 3, -1, -1]
#vertices [ A, B, C, D, E, F, G, H]
起始頂點 A 沒有父節點，因此其值為 -1。D 的父節點是 A，這就是為什麼 D 的父節點值為 0（頂點 A 位於索引 0）。B 的父節點也是 A，D 是 E 和 F 的父節點。
parents 陣列幫助我們維護 MST 的樹結構（一個頂點只能有一個父節點）。
此外，為了避免迴圈並跟蹤當前在 MST 中的頂點，使用了 in_mst 陣列。
此時，in_mst 陣列看起來像這樣
in_mst = [ true, false, false, true, false, false, false, false]
#vertices [ A, B, C, D, E, F, G, H]
普里姆演算法的下一步是包含一個新頂點作為 MST 的一部分，並選擇最接近當前 MST 節點 A 和 D 的頂點。
由於 A-B 和 D-F 的權重都相同，最低邊權重為 4，因此可以選擇 B 或 F 作為下一個 MST 頂點。在此演示中，我們選擇 B 作為下一個 MST 頂點。
如您所見，到 E 的 MST 邊之前來自頂點 D，現在來自頂點 B，因為 B-E 的權重 6 低於 D-E 的權重 7。頂點 E 在 MST 樹結構中（以及在 parents 陣列中）只能有一個父節點，因此 B-E 和 D-E 不能同時成為到 E 的 MST 邊。
MST 的下一個頂點是 C，因為 B-C 邊的權重 3 是當前 MST 頂點之間的最短邊權重。
隨著頂點 C 被包含在 MST 中，會檢查 C 的出邊，以確定是否有權重更低的邊從該 MST 頂點連線到 MST 外部的頂點。C-E 邊的權重（3）低於之前的 B-E MST 邊（6），並且 C-H 邊以權重 2 被包含在 MST 中。
頂點 H 是下一個要包含在 MST 中的頂點，因為它具有最低的邊權重 6，並且頂點 H 在 parents 陣列中成為頂點 G 的父節點。
下一個要包含在 MST 中的頂點是 E 或 F，因為它們都有最低的邊權重：4。
在此演示中，我們選擇頂點 E 作為下一個要包含在 MST 中的頂點。
下一個和最後兩個要新增到 MST 的頂點是 F 和 G。D-F 是到 F 的 MST 邊，E-G 是到 G 的 MST 邊，因為這些邊是當前 MST 的最低權重邊。
執行下面的模擬，檢視普里姆演算法執行我們剛剛完成的手動步驟。
普里姆演算法實現
為了讓普里姆演算法找到最小生成樹 (MST)，我們建立一個 Graph 類。稍後我們將使用此 Graph 類中的方法來建立上面示例中的圖，並在其上執行普里姆演算法。
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = weight
self.adj_matrix[v][u] = weight # For undirected graph
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data第 3-5 行：起初，鄰接矩陣為空，表示圖中沒有邊。此外，頂點一開始沒有名稱。
第 7-10 行： add_edge 方法用於在無向圖中新增一條帶權重的邊。
第 12-14 行： add_vertex_data 方法用於為頂點命名，例如“A”或“B”。
現在圖的建立結構已經到位，我們可以在 Graph 類中實現普里姆演算法作為一種方法。
def prims_algorithm(self):
in_mst = [False] * self.size
key_values = [float('inf')] * self.size
parents = [-1] * self.size
key_values[0] = 0 # Starting vertex
print("Edge \tWeight")
for _ in range(self.size):
u = min((v for v in range(self.size) if not in_mst[v]), key=lambda v: key_values[v])
in_mst[u] = True
if parents[u] != -1: # Skip printing for the first vertex since it has no parent
print(f"{self.vertex_data[parents[u]]}-{self.vertex_data[u]} \t{self.adj_matrix[u][parents[u]]}")
for v in range(self.size):
if 0 < self.adj_matrix[u][v] < key_values[v] and not in_mst[v]:
key_values[v] = self.adj_matrix[u][v]
parents[v] = u第 17 行： in_mst 陣列儲存當前哪些頂點屬於 MST 的狀態。最初，沒有頂點是 MST 的一部分。
第 18 行： key_values 陣列儲存從 MST 頂點到 MST 外部每個頂點的當前最短距離。
第 19 行： MST 邊儲存在 parents 陣列中。每條 MST 邊透過儲存每個頂點的父索引來儲存。
第 21 行：為了簡單起見，並使此程式碼像上面的“手動執行”動畫/示例一樣執行，第一個頂點（索引 0 處的頂點 A）被設定為起始頂點。將索引更改為 4 將從頂點 E 執行普里姆演算法，這也同樣有效。
第 25 行：找到具有最低鍵值且尚未屬於 MST 的頂點的索引。檢視這些對 min 和 lambda 的解釋，以更好地理解這一 Python 程式碼行。
第 32-35 行：將一個新頂點新增到 MST 後（第 27 行），程式碼的這部分會檢查從這個新新增的 MST 頂點是否有可能降低到 MST 外部其他頂點的鍵值。如果存在這種情況，則相應地更新 key_values 和 parents 陣列。在動畫中，當一個新頂點被新增到 MST 併成為活動（當前）頂點時，這一點就很清楚了。
現在，讓我們建立上面“手動執行”中的圖，並在其上執行普里姆演算法。
示例
Python
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = weight
self.adj_matrix[v][u] = weight # For undirected graph
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def prims_algorithm(self):
in_mst = [False] * self.size
key_values = [float('inf')] * self.size
parents = [-1] * self.size
key_values[0] = 0 # Starting vertex
print("Edge \tWeight")
for _ in range(self.size):
u = min((v for v in range(self.size) if not in_mst[v]), key=lambda v: key_values[v])
in_mst[u] = True
if parents[u] != -1: # Skip printing for the first vertex since it has no parent
print(f"{self.vertex_data[parents[u]]}-{self.vertex_data[u]} \t{self.adj_matrix[u][parents[u]]}")
for v in range(self.size):
if 0 < self.adj_matrix[u][v] < key_values[v] and not in_mst[v]:
key_values[v] = self.adj_matrix[u][v]
parents[v] = u
g = Graph(8)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')
g.add_vertex_data(7, 'H')
g.add_edge(0, 1, 4) # A - B
g.add_edge(0, 3, 3) # A - D
g.add_edge(1, 2, 3) # B - C
g.add_edge(1, 3, 5) # B - D
g.add_edge(1, 4, 6) # B - E
g.add_edge(2, 4, 4) # C - E
g.add_edge(2, 7, 2) # C - H
g.add_edge(3, 4, 7) # D - E
g.add_edge(3, 5, 4) # D - F
g.add_edge(4, 5, 5) # E - F
g.add_edge(4, 6, 3) # E - G
g.add_edge(5, 6, 7) # F - G
g.add_edge(6, 7, 5) # G - H
print("Prim's Algorithm MST:")
g.prims_algorithm()第 32 行：透過將此行更改為 for _ in range(self.size - 1):，我們可以避免普里姆演算法的最後一個迴圈。這是因為當只有一個頂點尚未包含在 MST 中時，該頂點的父頂點已在 parents 陣列中正確設定，因此 MST 實際上在此點已經找到。
普里姆演算法的時間複雜度
有關時間複雜度的一般性解釋，請訪問此頁面。
設 \(V\) 為我們圖中頂點的數量，普里姆演算法的時間複雜度為
\[ O( V^2 ) \]
我們得到此時間複雜度的原因是普里姆演算法內部的巢狀迴圈（一個 for 迴圈包含另外兩個 for 迴圈）。
第一個 for 迴圈（第 24 行）遍歷圖中的所有頂點。其時間複雜度為 \(O(V)\)。
第二個 for 迴圈（第 25 行）遍歷圖中的所有相鄰頂點，以查詢具有最低鍵值且不在 MST 中的頂點，以便它可以是下一個包含在 MST 中的頂點。其時間複雜度為 \(O(V)\)。
在將一個新頂點包含在 MST 中後，第三個 for 迴圈（第 32 行）會檢查所有其他頂點，以檢視新新增的 MST 頂點是否有指向 MST 外部頂點的出邊，這些邊可能導致較低的鍵值和更新的父關係。此操作的時間複雜度也為 \(O(V)\)。
將時間複雜度組合起來，我們得到
\[ \begin{equation} \begin{aligned} O(V)\cdot (O(V)+O(V)) & = O(V)\cdot (2\cdot O(V)) \\ & = O(V\cdot 2\cdot V) \\ & = O(2\cdot V^2) \\\\ & = O(V^2) \end{aligned} \end{equation} \]
透過使用優先佇列資料結構來管理鍵值，而不是像這裡那樣使用陣列，普里姆演算法的時間複雜度可以降低到
\[ O( E \cdot \log{V}) \]
其中 \(E\) 是圖中的邊數，\(V\) 是頂點數。
使用優先佇列實現普里姆演算法對於稀疏圖是最佳的。當每個頂點只連線到其他少數幾個頂點時，該圖就是稀疏的。
