最小生成树最小生成树是图论的算法之一用于解决带有权重且无环的最小连通问题。我们要计算连通所有节点的最小值如果定义连通无向图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 的一个划分如果某一条边uv的一个端点位于集合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的任意一个切割又设uv是横框切割S,V-S的一条轻量级边那么边uv对于集合A是安全的。也就是说找到某个尊重集合A的切割中的轻量级边将该轻量级边加入到集合A中集合A仍然是安全的。Kruskal算法和Prim算法都是对找到安全边的细化。对于Kruskal算法集合A是一个森林节点就是给定图的节点。对于Prim算法结合A则是一颗树每次加入到A中的安全边永远是连接A和A之外某个节点的边中权重最小的边。可以发现Kruskal和Prim算法都是贪心算法。接下来将对两个算法详细介绍。Kruskal算法Kruskal找到安全边的方法是在所有连接森林中两颗不同树的边里面找到权重最小的那一条边 u v uvuv。假设C1和C2为边uv所连接的两棵树由于边uv一定是连接C1和某棵树的轻量级边由定理1可以推出边uv是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)ans0mst_edges[]forw,u,vinedges:# 如果 u 和 v 是不连通的那么权重最小的切割w对于find(u)是安全的iffind(u)!find(v):union(u,v)answ mst_edges.append((u,v,w))returnansKruskal算法流程示意图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开始ans0mst_edges[]whilemin_heapandlen(mst_edges)n-1:# 每次弹出的边都是当前权重最小的边并且以节点 0 作为起始节点w,u,vheapq.heappop(min_heap)ifvisited[v]:continuevisited[v]Trueansw# 如果 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_edgesPrim算法流程示意图相关题目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解法distlambdax,y:abs(points[x][0]-points[y][0])abs(points[x][1]-points[y][1])nlen(points)edges[]mst_edges[]graph[[]for_inrange(n)]foriinrange(n):forjinrange(i1,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)]ans0whilemin_heapandlen(mst_edges)n-1:w,u,vheapq.heappop(min_heap)ifvisited[v]:continuevisited[v]Trueanswifu!-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
