算法学习笔记（3）：最小生成树

最小生成树

最小生成树是图论的算法之一，用于解决带有权重且无环的最小连通问题。我们要计算连通所有节点的最小值，如果定义连通无向图G = ( V , E ) G=(V,E)G=(V,E), 其中，V 和 E V和EV和E分别表示节点和节点所有的可能连接。对于每条边( u , v ) ∈ E (u, v)∈E(u,v)∈E，都赋予权重w = ( u , v ) w=(u,v)w=(u,v)，作为连接节点u和节点v的代价。希望找到一个无环子集T ⊆ E T\subseteq{E}T⊆E,即能够将所有节点连接起来，又具有最小权重，也即w ( T ) = ∑ ( u , v ) ∈ T w ( u , v ) w(T)=\sum\limits_{(u,v)\in{T}}{w(u,v)}w(T)=(u,v)∈T∑​w(u,v),很显然，无环子集T是一棵树，因为T是由图G生成的，求取该生成树的问题为最小生成问题。

如下所示：

接下来将使用两种贪心算法，分别为Kruskal和Prim算法，找到最小生成树T（最小生成树并不唯一）。在介绍两种算法之前，先介绍一些概念。
安全边：A是某棵树的最小生成树的一个子集，如果边（u, v）加入到集合A中，如果A ∪ ( u , v ) A\cup{(u,v)}A∪(u,v)也是某棵树的最小生成树的子集，由于可以安全地将边(u,v)加入到集合A而不会破坏集合A的循环不变式，称这样的边为安全边。

切割：对于无向图G = ( V , E ) G = (V,E)G=(V,E)的一个切割( S , V − S ) (S, V-S)(S,V−S)是集合V 的一个划分，如果某一条边（u，v）的一个端点位于集合S，而另一个端点位于集合V-S，那么就称该条边横跨切割(S,V-S)。如果集合A中不存在横跨该切割的边，称该切割尊重集合A。在横跨一个切割的所有边中，权重最小的边称为轻量级边。示意图如下所示：

定理1：如果集合A为某个连通无向图G = ( V , E ) G=(V,E)G=(V,E)的一个子集，且边E定义了实数权重函数w。A包括在图G的某棵最小生成树中，设（S,V-S）是图G中尊重集合A的任意一个切割，又设（u，v）是横框切割（S,V-S）的一条轻量级边，那么边（u，v）对于集合A是安全的。也就是说，找到某个尊重集合A的切割中的轻量级边，将该轻量级边加入到集合A中，集合A仍然是安全的。

Kruskal算法和Prim算法都是对找到安全边的细化。对于Kruskal算法，集合A是一个森林，节点就是给定图的节点。对于Prim算法，结合A则是一颗树，每次加入到A中的安全边永远是连接A和A之外某个节点的边中权重最小的边。可以发现，Kruskal和Prim算法都是贪心算法。接下来将对两个算法详细介绍。

Kruskal算法

Kruskal找到安全边的方法是，在所有连接森林中两颗不同树的边里面，找到权重最小的那一条边（ u ， v ） （u，v）（u，v）。假设C1和C2为边（u，v）所连接的两棵树，由于边（u，v）一定是连接C1和某棵树的轻量级边，由定理1可以推出，边（u，v）是C1的一条安全边。

模板

defkruskal(edges:List[List[int]],n:int,m:int)->:# n个节点，m条边# edges存储的格式为：edge[i] = [w,u,v],u和v分别为两个端点，w为权重edges.sort(keylambdax:x[0])parent=[iforiinrange(n)]deffind(x):ifx!=fa[x]:parent[x]=find(parent[x])returnparent[x]defunion(x,y):parent[find(x)]=find(y)ans=0mst_edges=[]forw,u,vinedges:# 如果 u 和 v 是不连通的，那么权重最小的切割w对于find(u)是安全的iffind(u)!=find(v):union(u,v)ans+=w mst_edges.append((u,v,w))returnans

Kruskal算法流程示意图：

Prim算法

集合A中的边总是构成一颗树，从树中的任意一个节点r开始，一直长大到覆盖V中的所有节点为止。在连接集合A和集合A之外任意节点的所有边中，选择一条轻量级边加入到集合A中。

defprim(edges,n,m):graph=[[]for_inrange(n)]foru,v,winedges:graph[u].append((v,w))graph[v].append((u,w))visited=[False]*n min_heap=[(0,-1,0)]#创建优先队列，格式为：(权重，当前节点，当前边终点)，以权重作为首先排序，从节点0开始ans=0mst_edges=[]whilemin_heapandlen(mst_edges)<n-1:# 每次弹出的边，都是当前权重最小的边，并且以节点 0 作为起始节点w,u,v=heapq.heappop(min_heap)ifvisited[v]:continuevisited[v]=Trueans+=w# 如果 u == -1 ，说明不是起点ifu!=-1:mst_edegs.append((u,v,w))# v是新加入到 最小生成树的终点，遍历 v 的所有邻边fornext_node,weightingraph[v]:ifnotvisited[next_node]:# 如果 next_node 没有加入生成树，那么这条边就是候选边,加入到最小堆中heap.heanppush(heap,(weight,v,next_node))iflen(mst_edges)!=n-1:return-1,[]returnans,mst_edges

Prim算法流程示意图

相关题目

1584.连接所有点的最小费用

1584. 连接所有点的最小费用 - 力扣（LeetCode）
给你一个points数组，表示 2D 平面上的一些点，其中points[i] = [xi, yi]。

连接点[xi, yi]和点[xj, yj]的费用为它们之间的曼哈顿距离：|xi - xj| + |yi - yj|，其中|val|表示val的绝对值。

请你返回将所有点连接的最小总费用。只有任意两点之间有且仅有一条简单路径时，才认为所有点都已连接。

示例 1：

**输入：**points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
**输出：**20
解释：

我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。
注意到任意两个点之间只有唯一一条路径互相到达。

示例 2：

**输入：**points = [[3,12],[-2,5],[-4,1]]
**输出：**18

示例 3：

**输入：**points = [[0,0],[1,1],[1,0],[-1,1]]
**输出：**4

示例 4：

**输入：**points = [[-1000000,-1000000],[1000000,1000000]]
**输出：**4000000

示例 5：

**输入：**points = [[0,0]]
**输出：**0

提示：

• 1 <= points.length <= 1000
• -106 <= xi, yi <= 106
• 所有点(xi, yi)两两不同。

importheapqclassSolution:defminCostConnectPoints(self,points:List[List[int]])->int:# Prim解法dist=lambdax,y:abs(points[x][0]-points[y][0])+abs(points[x][1]-points[y][1])n=len(points)edges=[]mst_edges=[]graph=[[]for_inrange(n)]foriinrange(n):forjinrange(i+1,n):edges.append((dist(i,j),i,j))forw,u,vinedges:graph[u].append((v,w))graph[v].append((u,w))visited=[False]*n min_heap=[(0,-1,0)]ans=0whilemin_heapandlen(mst_edges)<n-1:w,u,v=heapq.heappop(min_heap)ifvisited[v]:continuevisited[v]=Trueans+=wifu!=-1:mst_edges.append((w,u,v))fornext_node,weightingraph[v]:heapq.heappush(min_heap,(weight,v,next_node))iflen(mst_edges)!=n-1:returnans,[]returnans## Kruskal 解法# n = len(points)# ans = 0# edges = []# mst_edges = []# parent = list(range(n))# def find(x):# if parent[x] != x:# parent[x] = find(parent[x])# return parent[x]# def union(x, y):# parent[find(y)] = find(x)# # 自己构造 edges# dist = lambda x,y: abs(points[x][0] - points[y][0]) + abs(points[x][1] - points[y][1])# for i in range(n):# for j in range(i + 1, n):# edges.append((dist(i, j), i, j))# # 需要对权重值进行排序# edges.sort()# for w, u, v in edges:# if find(u) != find(v):# union(u, v)# ans += w# mst_edges.append((w, u, v))# return ans