算法设计与分析 课件 6.6-贪心法应用-最小生成树

信息工程大学算法设计与分析贪心法—最小生成树国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版最小生成树(Minimum-costSpanningTree)：设G=(V,E)是无向连通带权图，即一个网络。如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。

生成树的性质：包含n个顶点；有且仅有(n-1)条边；任两点都是有路可达的。生成树上各边权的总和称为该生成树的耗费。耗费最小的生成树称为G的最小生成树。1234566515366425

最小生成树有广泛应用。比如建立城市间的通信网络、乡村间的道路连通等问题，最小生成树可以给出最优的建设方案。最小生成树问题的本质：求无向连通带权图的最小连通代价。判断题。对于一个无向连通带权图，最小生成树可能是不唯一的。A.不正确B.正确Prim算法和Kruskal算法都是用贪心思想构造的最小生成树。尽管它们的贪心策略不同，但都利用了最小生成树性质。

uv顶点集U顶点集V-UMST性质证明：（反证法）假设G的任何一棵最小生成树中都不包含边(u,v)。设T是G的一棵最小生成树，但不包含边(u,v)。由于T是树，且是连通的，因此必有一条从u到v的路径，且该路径上必有一条连接两个顶点集U和V-U的边(u',v')，其中u'属于U，v'属于V-U。将边(u,v)加入到T中，得到一个含边(u,v)的回路。当删除边(u',v')时，回路被消除。由此得到另一棵生成树T’，T’和T的区别仅在于用边(u,v)取代了T中的边(u’,v’)。因为(u,v)的权<=(u’,v’)的权，故T‘的权值<=T的权值。因此，T’也是G的最小生成树，并包含边（u,v），与假设矛盾。uu'vv'顶点集U顶点集V-U

1234566515366425123456112345614123456142123456154212345615342①②③④⑤⑥

需要的数据结构：标识顶点i是否属于集合S：使用数组s如何有效地找出满足条件i

S，j

V-S，且权值c[i][j]最小的边(i,j)？

对于V-S中每个顶点j，把S到j权值最小的点i存入parent[j]，权值c[i][j]存入dist[j]，当有新的点加入S时，更新parent[j]和dist[j]。1234566515366425迭代Sjp[2]d[2]p[3]d[3]p[4]d[4]p[5]d[5]p[6]d[6]初始{1}161115—∞—∞1{1,3}335111536342{1,3,6}635116236343{1,3,6,4}435116236344{1,3,6,4,2}235116223345{1,3,6,4,2,5}3511622334Prim算法执行过程中相关数组的变化情况（parent[j]简写为p[j]，dist[j]简写为d[j]）1234561(1)5(4)3(5)4(2)2(3)voidprim(){/*prim算法构建最小生成树*//*初始化*/s[1]=1;s[2~n]=0;forj=2ton ifc[1][j]!=INF{parent[j]=1;dist[j]=c[j][1]；}/*循环n-1次，依次加入点和边*/for(k=1;k<=n-1;k++){/*找出V-S中dist值最小的顶点j*/inttmin=INF;j=-1;fori=2ton if(s[i]==0)&&dist[i]<tmin){tmin=dist[i];j=i;}s[j]=1;/*将j添加到S中*//*依次判断和j相邻且在V-S中的点，判断该边权值是否更小，如果是，则修改parent和dist*/fori=2tonif(s[i]==0)&&dist[i]<c[j][i]){dist[i]=c[j][i];parent[i]=j;}}}时间复杂度：O(n2)最小生成树性质：只要是连接两个集合的权值最小的边，一定在某棵最小生成树中。Kruskal算法基本思想：1.

n个顶点看成n个孤立的连通分支，将所有的边按权值从小到大排序；

2.依次查看每一条边(i,j)，如果i和j分别来自不同的连通分支T1和T2时，就用边(i,j)将T1和T2连接成一个连通分支；3.重复步骤2，直到只剩下一个连通分支时为止。1234561212345611234561534212345612312345665153664251234561423①②③④⑤⑥Kruskal算法中的关键步骤：边按权值从小到大排序逐一判断边的两个邻接点是否在同一个连通分支中，如不是1）合并两个端点所在的分支2）把边加入最小生成树中用并查集高效