数据结构第七章第四节.ppt

7.4.3 最小生成树,Minimum Cost Spanning Tree-MST,构造MST的原则：,必须使用网络中的边来构造最小生成树；必须使用且仅使用n-1条边来连接网络中的n个顶点；不能使用产生回路的边；,u,MST性质：,假设N=(V,E)是一个连通网，U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u属于U,v属于V-U,则必存在一棵包含边(u,v)的最小生成树,v,T,T,(u,v),(u,v),U,V-U,最小两栖边,MST性质：,假设N=(V,E)是一个连通网，U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u属于U,v属于V-U,则必存在一棵包含边(u,v)的最小生成树,普里姆(Prim)算法 克鲁斯卡尔(Kruskal)算法,两种算法：,假设N=(V,E)是连通网，TE是N上最小生成树边集合。(1)U=u0(u0属于V),TE=(2)在所有u，vV的边(u,v)E 中找一条代 价最小的边(u0,v0)并入集合TE,同时v0并入U,(3)如果V,转(2),普里姆(Prim)算法,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,普里姆(Prim)算法,V1,V2,V4,V3,V5,V6,6,5,1,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,普里姆(Prim)算法,V1,V2,V4,V3,V5,V6,5,1,6,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,普里姆(Prim)算法,V1,V2,V4,V3,V5,V6,5,1,5,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,普里姆(Prim)算法,V1,V2,V4,V3,V5,V6,5,1,5,6,4,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,普里姆(Prim)算法,V1,V2,V4,V3,V5,V6,5,1,5,6,4,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,普里姆(Prim)算法,V1,V2,V4,V3,V5,V6,1,5,6,4,2,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,普里姆(Prim)算法,V1,V2,V4,V3,V5,V6,1,5,6,4,2,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,普里姆(Prim)算法,V1,V2,V4,V3,V5,V6,1,5,6,4,2,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,普里姆(Prim)算法,V1,V2,V4,V3,V5,V6,1,5,4,2,3,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,普里姆(Prim)算法,V1,V2,V4,V3,V5,V6,1,5,4,2,3,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,普里姆(Prim)算法,V1,V2,V4,V3,V5,V6,1,5,4,2,3,/记录从顶点集 U 到 V-U 的代价最小的边辅助数组struct VerTexType adjvex;VRType lowcost;closedgeMAX_VERTEX_NUM;,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,closedgei-1.lowcost=Mincost(uj,vi),viV-U,closedgei-1.adjvex=uj,U=v1,v3,V-U=v2,v4,v5,v6,ujU,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,V1,V2,V4,V3,V5,V6,6,5,1,i,closedge,V2,V3,V4,V5,V6,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,V1,V2,V4,V3,V5,V6,6,5,1,i,closedge,V2,V3,V4,V5,V6,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,i,closedge,V2,V3,V4,V5,V6,V1,V2,V4,V3,V5,V6,6,5,1,0,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,i,closedge,V2,V3,V4,V5,V6,V1,V2,V4,V3,V5,V6,5,5,1,0,5,v3,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,i,closedge,V2,V3,V4,V5,V6,V1,V2,V4,V3,V5,V6,5,5,1,0,5,v3,6,4,6,v3,4,v3,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,i,closedge,V2,V3,V4,V5,V6,0,5,v3,6,v3,4,v3,V1,V2,V4,V3,V5,V6,5,5,1,6,4,0,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,i,closedge,V2,V3,V4,V5,V6,0,5,v3,6,v3,4,v3,0,V1,V2,V4,V3,V5,V6,5,1,6,4,2,v6,2,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,i,closedge,V2,V3,V4,V5,V6,0,5,v3,6,v3,4,v3,0,V1,V2,V4,V3,V5,V6,5,1,6,4,2,v6,2,0,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,i,closedge,V2,V3,V4,V5,V6,0,5,v3,6,v3,4,v3,0,V1,V2,V4,V3,V5,V6,5,1,6,4,6,2,0,v6,0,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,i,closedge,V2,V3,V4,V5,V6,0,5,v3,6,v3,4,v3,0,V1,V2,V4,V3,V5,V6,5,1,4,2,v6,2,3,0,3,v6,0,v2,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,i,closedge,V2,V3,V4,V5,V6,0,5,v3,6,v3,4,v3,0,V1,V2,V4,V3,V5,V6,5,1,4,2,v6,2,3,0,3,v6,0,v2,0,struct VerTexType adjvex;VRType lowcost;closedgeMAX_VERTEX_NUM;,V1 6,V1 1,V1 5,V1,V2,V3,V4,V5,V6,2,V1,V3,V2,V4,V5,V6,0,V3 5,V1 5,5,V3 6,V3 4,V1,V3,V6,V2,V4,V5,0,0,V3 5,V6 2,V3 6,3,V1,V3,V6,V4,V2,V5,0,0,0,V3 5,V3 6,1,V1,V3,V6,V4,V2,V5,0,0,0,0,V2 3,4,V1,V3,V6,V4,V2,V5,0,0,0,0,0,void MiniSpanTree_PRIM(MGraph G,VertexType u)k=LocateVex(G,u);for(j=0;jG.vexnum;+j)/辅助数组初始化 if(j!=k)closedgej=u,G.arcskj.adj;closedgek.lowcost=0;/初始，U=u for(i=1;iG.vexnum;+i)/选择其余G.vexnum-1个顶点 k=minimum(closedge);/求出T的下一个结点：第k顶点 printf(closedgek.adjvex,G.vexsk);/输出生成树的边 closedgek.lowcost=0;/第k顶点并入U集 for(j=0;jG.vexnum;+j)if(G.arcskj closegej.lowcost)/新顶点并入U后，重新选择最小边 closedgej=G.vexsk,G.arcskj.adj;/MiniSpanTree_PRIM,克鲁斯卡尔(Kruskal)算法,假设N=(V,E)是连通网。(1)初始状态 T=V,(2)在E中选择代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入T中(3)重复(2),直到T中所有顶点都在同一连通分量上,克努斯卡尔算法,V1,V2,V4,V3,V5,V6,10,5,1,8,7,11,14,3,4,2,V1,V2,V4,V3,V5,V6,10,5,1,8,7,11,14,3,4,2,克努斯卡尔算法,克努斯卡尔算法,V1,V2,V4,V3,V5,V6,10,5,1,8,7,11,14,3,4,2,克努斯卡尔算法,V1,V2,V3,V5,10,1,7,11,14,3,5,V4,V6,8,4,2,克努斯卡尔算法,V1,V2,V4,V3,V5,V6,10,5,1,8,7,11,14,3,4,2,克努斯卡尔算法,V1,V2,V4,V3,V5,V6,10,5,1,8,7,11,14,3,4,2,克努斯卡尔算法,V1,V2,V4,V3,V5,V6,10,5,1,8,7,11,14,3,4,2,克努斯卡尔算法,V1,V2,V4,V3,V5,V6,10,5,1,8,7,11,14,3,4,2,克努斯卡尔算法,V2,V4,V3,10,5,1,8,7,11,14,3,4,2,V1,V5,V6,克努斯卡尔算法,V1,V2,V4,V3,V5,V6,10,5,1,8,7,11,14,3,4,2,void MiniSpanTree_Kruskal(MGraph G,Edge mst)int i,k;Edge amaxE;HeapSort(a,0,E-1);/对图的所有边进行堆排序(非递减次序)Initial_mfset(G-V);/对图的顶点构造并查集，并初始化 for(i=0,k=0;iE/将边添加到生成树的边集合中/if/for,两种算法的比较,算法名,普里姆算法,克鲁斯卡尔算法,时间复杂度,适用范围,O(n2),O(eloge),稠密图,稀疏图,小结,1.最小生成树的概念及MST性质,2.普里姆算法的思路及应用场合3.克鲁斯卡尔算法的思路及应用场合,