《数据结构mst》ppt课件

《《数据结构mst》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§7.4.2最小生成树（MinimumSpanningTree）设G是连通图，G的生成树不唯一MST：权最小的生成树，树的权是各边上的权值之和应用n个城市之间的通信网，可构建n(n-1)/2条线路n个城市连通至少要n-1条线路，G的生成树是1个可行的方案最小生成树是最经济的可行方案1MST性质－大多数算法都利用了此性质设G＝(V，E)是一连通图，U是V的真子集，若（u，v）是所有连接U和V-U的边中权最小的边（轻边），则一定存在G的一棵最小生成树包括此边。Pf：设G的任何一棵最小生成树均不包括(u，v)；T’uvv

2、’u’uvv’u’TUUV-UV-U2构造MST：就是找轻边扩充到当前生成的树T＝（U，TE）中U－红点集、红边集，构成TV－白点集、白边集紫边集－连接红点和白点的边轻边－权最轻的紫边，或最短紫边(若权为长度):（u1，v1）u1v1UV-U5501523u2u3v2v331、Prim算法特点当前的形成的集合T＝（U，TE）始终是一棵树T中的顶点和边均为红色基本思想（贪心法）设V(G)={0,1,…,n-1}算法的每一步均是在连接红、白点集的紫边中选一轻边扩充到T（贪心），T从任意一点r开始（r为根），直至U＝V为

3、止。MST性质保证了贪心选择策略的正确性。41、Prim算法如何找轻边？可能的紫边集设红点集

4、U

5、=k,白点集

6、V-U

7、=n-k，则可能的紫边数为：k(n-k)。在此紫边集中选择轻边效率太低。构造候选轻边集构造较小的紫边集，但保证轻边在其中。因为，∀v∈白点集，从v到各红点的紫边中，只有最短的那一条才可能是轻边，所以只须保留所有n－k个白点所关联的最短紫边作为轻边候选集即可。显然，轻边是该候选集中权最轻的边。可以针对红点集来构造候选轻边集吗？51、Prim算法如何维护候选轻边集？当把轻边（u，v）扩充至T中时，v由

8、白点变为红点，紫边（u，v）变为红边；∵对每个剩余白点j，边（v，j）由白变紫，此新紫边的长度可能小于白点j原来所关联的最短紫边。∴须调整候选轻边集，用更短的新紫边（v，j）取代原来关联于j的最短紫边。61、Prim算法算法梗概PrimMST(G,T,r){//求以r为根的MSTInitCandidateSet(…);//初始化，置初始的候选轻边集，置T＝（{r},φ）for(k=0;k

9、u,v)};//将(u,v)涂红加入树中，白点v加入红点集ModifyCandidateSet(…);//根据新红点v调整候选轻边集}}算法终止时U＝V，T=(V,TE)71、Prim算法实例0235416517234556023541651∞∞0235415514502354152145023541521450235415214381、Prim算法存储结构＃defineInfinityINT_MAX//表示最大整数＃definen100typedefintAdjMatrix[n][n];//邻接矩阵typedef

10、struct{//树边intfromvex,tovex;//起点、终点intlen;//边长度，权值}MST[n-1];设邻接矩阵初值：不存在的边其权值为Infinity91、Prim算法算法求精－初始化将根r涂红加入红点集U，TE＝φ。对每个白点i(0≤i≤n-1,i≠r),i所关联的最短紫边（r,i）的长度为G[r][i],这n-1条最短紫边构成了初始的候选轻边集。因为树边为空，故将T[0..n-2]全部用来存放候选轻边集。voidInitCandidateSet(AdjMatrixG,MSTT,intr){i

11、nti,k=0;for(i=0;i

12、pos,min=Infinity;for(i=k;i