• 最小生成樹MST，有兩種算法進行求解，分別是Kruskal算法和Prim算法
• Kruskal算法從邊出發，適合用于稀疏圖
• Prim算法從頂點出發，適合用于稠密圖：基本思想是從一個起始頂點開始，逐步擴展生成樹，每次選擇一條連接已選頂點和未選頂點的最小權重邊，直到所有頂點都被包含在生成樹中。

Prim算法的基本步驟：

• 初始化：選擇一個起始頂點，將其加入生成樹中。
• 選擇最小邊：在所有連接生成樹中頂點和未加入生成樹的頂點的邊中，選擇權重最小的邊。
• 擴展生成樹：將這條邊及其連接的未加入頂點加入生成樹。
• 重復：重復步驟2和步驟3，直到所有頂點都加入生成樹。

與求解最短路徑的Dijkstra算法的求解思路是有異曲同工之妙的

• Prim 算法的樸素模版，時間復雜度$O(n^2)$

# 該模版可以求解最小生成樹的權值ans = 0# done[i]表示節點i到最小生成樹的最小距離是否確定done = [False]*n # 注意，現在并沒有設置done[0]=Truedis = [float('inf')]*ndis[0] = 0# 構建最小生成樹for i in range(n):m = float('inf')# 還沒在樹中，并且到達樹的距離最小的節點for j in range(n):if not done[j] and (node < 0 or dis[j] < dis[node]):node = jdone[node] = True# 累加情況ans += dis[node]# 更新node的鄰居的情況for neigh in range(n):if not done[neigh] and edge[node][neigh] < dis[neigh]:dis[neigh] = edge[node][neigh]return ans

• Kruakal算法是從邊出發，一直合并不與當前節點形成環的邊，時間復雜度$O(eloge)$,e是邊數
• Kruskal算法模版

        # 先按照距離排序edge.sort(key=lambda x:x[0])# 使用并查集parent = list(range(n))def find(index):if parent[index] != index:parent[index] = find(parent[index])return parent[index]def union(index1,index2):parent[find(index1)] = find(index2)ans = 0count = 0 # 計數器# 對邊進行遍歷for d,x,y in edge:fx,fy = find(x),find(y)# 當屬于同一個祖先就不要，不然會形成環if fx == fy:continueans += d# 更新計數器count+=1union(x,y)# 如何合并了n-1的邊，就結束if count == n-1:breakreturn ans

題目

1584.連接所有點的最小費用

1584.連接所有點的最小費用

思路分析：最小生成樹的模版題目

• 使用Prim算法模版題

class Solution:def minCostConnectPoints(self, points: List[List[int]]) -> int:# 有兩種實現方式，分別是Kruskal算法和Prim 算法# Kruskal算法從邊出發，適合用于稀疏圖，prim算法從點出發，適合用于稠密圖n = len(points)# 先構建鄰接表edge = [[float('inf')]*n for _ in range(n)]for i in range(n):x1,y1 = points[i]for j in range(i+1,n):x2,y2 = points[j]d = abs(x1-x2)+abs(y1-y2)edge[i][j] = d edge[j][i] = d # 該模版可以求解最小生成樹的權值ans = 0# done[i]表示節點i到最小生成樹的最小距離是否確定done = [False]*n # 注意，現在并沒有設置done[0]=Truedis = [float('inf')]*ndis[0] = 0# 構建最小生成樹for i in range(n):m = float('inf')# 還沒在樹中，并且到達樹的距離最小的節點for j in range(n):if not done[j] and (node < 0 or dis[j] < dis[node]):node = jdone[node] = True# 累加情況ans += dis[node]# 更新node的鄰居的情況for neigh in range(n):if not done[neigh] and edge[node][neigh] < dis[neigh]:dis[neigh] = edge[node][neigh]return ans

• 使用Kruskal算法模版

class Solution:def minCostConnectPoints(self, points: List[List[int]]) -> int:# 有兩種實現方式，分別是Kruskal算法和Prim 算法# Kruskal算法從邊出發，適合用于稀疏圖，prim算法從點出發，適合用于稠密圖# 使用Kruskal，從邊出發n = len(points)edge = []# 將全部的邊都加入這個edgefor i in range(n):x1,y1 = points[i]for j in range(i+1,n):x2,y2 = points[j]d = abs(x1-x2)+abs(y1-y2)edge.append((d,i,j))# 先按照距離排序edge.sort(key=lambda x:x[0])# 使用并查集parent = list(range(n))def find(index):if parent[index] != index:parent[index] = find(parent[index])return parent[index]def union(index1,index2):parent[find(index1)] = find(index2)ans = 0count = 0 # 計數器for d,x,y in edge:fx,fy = find(x),find(y)if fx == fy:continueans += dcount+=1union(x,y)if count == n-1:breakreturn ans