图论 之 最小生成树

• 最小生成树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