《最小生成树MinimumSpanningTree.ppt》由会员分享，可在线阅读，更多相关《最小生成树MinimumSpanningTree.ppt（27页珍藏版）》请在三一办公上搜索。
1、,1,7.4.2 最小生成树（Minimum Spanning Tree）,设G是连通图，G的生成树不唯一MST：权最小的生成树，树的权是各边上的权值之和应用n个城市之间的通信网，可构建n(n-1)/2条线路n个城市连通至少要n-1条线路，G的生成树是1个可行的方案最小生成树是最经济的可行方案,2,MST性质大多数算法都利用了此性质设G(V，E)是一连通图，U是V的真子集，若（u，v）是所有连接U和V-U的边中权最小的边（轻边），则一定存在G的一棵最小生成树包括此边。Pf：设G的任何一棵最小生成树均不包括(u，v)；,3,构造MST：就是找轻边扩充到当前生成的树T（U，TE）中U红点集、红边集
2、，构成TV-U白点集、白边集紫边集连接红点和白点的边轻边权最轻的紫边，或最短紫边(若权为长度):（u1，v1）,4,1、Prim算法,特点当前形成的集合T（U，TE）始终是一棵树T中的顶点和边均为红色基本思想（贪心法）设V(G)=0,1,n-1算法的每一步均是在连接红、白点集的紫边中选一轻边扩充到T（贪心），T从任意一点r开始（r为根），直至UV为止。MST性质保证了贪心选择策略的正确性。,5,1、Prim算法,如何找轻边？可能的紫边集 设红点集|U|=k,白点集|V-U|=n-k，则可能的紫边数为：k(n-k)。在此紫边集中选择轻边效率太低。构造候选轻边集 构造较小的紫边集，但保证轻边在其中
3、。因为，v白点集，从v到各红点的紫边中，只有最短的那一条才可能是轻边，所以只须保留所有nk个白点所关联的最短紫边作为轻边候选集即可。显然，轻边是该候选集中权最轻的边。可以针对红点集来构造候选轻边集吗？,6,1、Prim算法,如何维护候选轻边集？当把轻边（u，v）扩充至T中时，v由白点变为红点，紫边（u，v）变为红边；对每个剩余白点j，边（v，j）由白变紫，此新紫边的长度可能小于白点j原来所关联的最短紫边。须调整候选轻边集，用更短的新紫边（v，j）取代原来关联于j的最短紫边。,7,1、Prim算法,算法梗概PrimMST(G,T,r)/求以r为根的MST InitCandidateSet();/
4、初始化，置初始的候选轻边集，置T（r,）for(k=0;kn-1;k+)/求T的n-1条树边(u,v)=SelectLightEdge();/选轻边，可能不唯一 TETE(u,v);/将(u,v)涂红加入树中，白点v加入红点集 ModifyCandidateSet();/根据新红点v调整候选轻边集 算法终止时UV，T=(V,TE),8,1、Prim算法,实例,0,2,3,5,4,1,5,2,1,4,5,0,2,3,5,4,1,5,2,1,4,5,0,2,3,5,4,1,5,2,1,4,3,9,1、Prim算法,存储结构define Infinity INT_MAX/表示最大整数define n
5、 100typedef int AdjMatrixnn;/邻接矩阵typedef struct/树边 int fromvex,tovex;/起点、终点 int len;/边长度，权值 MSTn-1;设邻接矩阵初值：不存在的边其权值为Infinity,10,1、Prim算法,算法求精初始化将根r涂红加入红点集U，TE。对每个白点i(0i n-1,ir),i所关联的最短紫边（r,i）的长度为Gri,这n-1条最短紫边构成了初始的候选轻边集。因为树边为空，故将T0.n-2全部用来存放候选轻边集。void InitCandidateSet(AdjMatrix G,MST T,int r)int i,k
6、=0;for(i=0;in;i+)/依次形成白点i初始的最短紫边存放在Tk中 if(i!=r)Tk.fromvex=r;/紫边起点为红点 Tk.tovex=i;/紫边终点为白点 Tk+.len=Gri;/紫边长度，权值;,11,1、Prim算法,算法求精选轻边在当前候选轻边集Tk.n-2中，选长度最短的紫边。(Note:T0.k-1是红边集，T也是树，为什么针对白点构造候选集更好？)void SelectLightSet(MST T,int k)int i,minpos,min=Infinity;for(i=k;in-1;i+)/遍历候选集找轻边 if(Ti.len min)min=Ti.le
7、n;/紫边起点为红点 minpos=i;/记录当前最短紫边的位置 if(min=Infinity)error(“G不连通”）;return minpos;/轻边为Tminpos;,12,1、Prim算法,算法求精调整候选轻边集设轻边（u,v）涂红后加入到树边中，Tk.n-2是待调整的候选轻边集，则须根据新红点v调整Tk.n-2。void ModifyCandidateSet(AdjMatrix G,MST T,int k,int v)int i,d;/v是新红点 for(i=k;in-1;i+)/遍历候选集 d=GvTi.tovex;/Ti的终点是白点，d是新紫边的长度 if(dTi.len)
8、/d小于白点Ti.tovex原关联最短紫边长度 Ti.len=d;Ti.fromvex=v;/新紫边取代Ti.tovex原来的最短紫边;,13,1、Prim算法,算法求精最终算法void PrimMST(AdjMatrix G,MST T,int r)int k,m,v;InitCandidateSet(G,T,r);/初始候选集T0.n-2 for(k=0;kn-1;k+)/求n-1条树边中的kth条 mSelectLightEdge(T,k);/在Tk.n-2选轻边Tm TmTk;/轻边和紫边Tk交换，将其扩充至树中 vTk.tovex;/交换后红边集为T0.k,v是新红点 ModifyC
9、andidateSet(G,T,k+1,v);/Tk+1.n-2是新候选集，根据新红点v调整候选轻边集,14,1、Prim算法,时间分析初始化：O(n)在k循环中：Select中循环次数为n-k-1/在Tk.n-2选轻边Tm Modify中循环次数为n-k-2/Tk+1.n-2是新候选集，根据新红点v调整候选轻边集 因此：时间为O(n2)，与边无关，适合稠密图。,15,2、Kruskal算法,特点：当前形成的集合T除最终结果外，始终是森林，无环。算法：KruskalMST(G)T=(V,)；/包含n个顶点，不含边的森林；依权的增序对E(G)中边排序，设结果在E0.e-1;for(i=0;ie;
10、i+)取E中第i条边(u,v);if（u和v分属森林T中两棵不同的树）then TT（u,v）;/否则产生回路，放弃此边 if（T已是一棵树）then return T；/endfor,16,2、Kruskal算法（续）,例子：略时间：对边排序O(elge)for循环中：检测每条边的两个顶点是否在同一连通分量（树）上 只要采用合适的数据结构，检测时间为O(lge)因此，此时间亦为O(elge)。总计：O(elge)结论：时间性能主要取决于边数，适合稀疏图。,17,7.5 拓扑排序 有向无环图DAG（Directed Acyclic Graph）的应用,18,1、相关概念,集合与关系笛卡儿积：设
11、A、B是两个集合，所有序偶(x,y)构成的集合（xA,y B），称为A，B的笛卡儿积，记为AB。二元关系：集合AB的一个子集R，称为集合A与B上的一个二元关系，简称关系。若BA，则R称为A上的一个二元关系，他刻画了集合A中两个元素之间的关系。若(x，y)R，则称x和y有关系R，亦可记为xRy，否则x和y没有关系R，记为x y。集合A上的关系R是自反的（反身的），若对x A，都有xRx。集合A上的关系R是对称的，若xRy，则yRx。其中，x，y A。集合A上的关系R是反对称的，若xRy，yRx,则必有xy.其中x,y A。集合A上的关系R是传递的，若xRy，yRz，则xRz。其中x,y,z A。
12、例子：数之间的相等关系，具有自反性，对称性，传递性，反对称性；数之间的小于关系，具有传递性，反对称性；数之间的小于等于关系，具有自反性，传递性，反对称性；,19,1、相关概念,偏序（部分序）设R是集合A上的一个关系，若R具有自反性，反对称性和传递性，则称R是A上的偏序关系，A是偏序集（对于R）。偏序关系R一般记为，若将关系看作是比较，则偏序关系是指集合中仅有部分元素是可以比较的。全序（线性序）设R是集合A上的一个偏序关系，若对 x,y A，必有xRy或yRx，则称R是A上的全序关系，A是全序集（对于R）。数集合上的大小关系是全序关系 全序关系是指集合中全体成员之间均可比较。,20,1、相关概念
13、,拓扑排序 将一个dag图G（V，E）中的所有顶点排成一个线性序列，使得对G中任意一对顶点u和v，若 E，则在线性序列中u在v之前。这种给顶点定序的操作称为拓扑排序。拓扑（有序）序列：上述顶点的线性序列称为拓扑序列。唯一吗？几何意义：将G中顶点按拓扑序列的次序排成一行，则G中所有的有向边的指向均为从在到右例子：,v2,v3,v1,v4,v2,v4,21,1、相关概念,拓扑排序拓扑排序成功的充要条件：无环。例子：应用背景 有向图G可表示事件之间的先后关系，顶点表示事件，边表示事件之间的依赖关系：E(G)表示u先于v发生，u完成后才能开始v。若G表示施工图、生产流程图、学习计划安排，则在只能串行工
14、作时，拓扑序列是一种可行的方案或计划。,22,2、求拓扑序列？,(1)无前驱的顶点优先算法思想：输出当前入度为0的顶点。NonPreFirstTopSort（G）while(G中有入度为0的顶点)do 从G中选1个入度为0的顶点v输出之；从G中删v及其出边，出边终点的入度减1；if(输出的顶点数|V(G)|)then Error(“G有环，排序失败”);,23,2、求拓扑序列？,(1)无前驱的顶点优先例子：输出v1，v4，v3，v2，v5,24,2、求拓扑序列？,算法实现 增加一局部向量indegree0.n保存各顶点的当前入度 或者在邻接表的顶点表中增加入度域 用栈（或队列）来保存所有入度为
15、0的顶点，以免每次选入度为0的顶点 时扫描整个indegree向量,void NonPreFirstTopSort（ALGraph G）/以下vi简称为i int indegreeMaxVertexNum，i，j，count=0；SeqStack S;EdgeNode*p;for(i=0;ip-next)/扫描i的出边表 indegreep-adjvex+;/将的终点j入度加1，j=p-adjvex InitStack(/入度为0的顶点入栈,25,2、求拓扑序列？,while(!StackEmpty(时间：初始化O(n+e)排序成功时最大：每个顶点入出栈各1次，每个边表节点被检查1次O(n+e
16、),26,2、求拓扑序列？,(2)无后继的顶点优先算法思想：输出当前出度为0的顶点。NonSuccFirstTopSort（G）/应选G的逆邻接表 while(G中有出度为0的顶点)do 从G中选1个出度为0的顶点v输出之；从G中删v及其入边，入边起点的出度减1；if(输出的顶点数|V(G)|)then Error(“G有环，排序失败”);输出结果：逆拓扑序列算法实现：略,27,2、求拓扑序列？,(3)利用dfs遍历算法原理：因为当从某顶点v出发的dfs搜索完成时，v的所有后继必定均已访问过（想象他们均已被删除），此时v相当于是无后继的顶点，所以可在dfs算法返回前输出顶点v，即可得到DAG的逆拓扑序列。算法：DFSTopSort（G，i，T）/在DFSTraverse中调用此算法，T是栈 visitedi=TRUE;/访问i for(所有i的邻接点j）/即 E(G)if(!visitedj)DFSTopSort(G,j,T)；Push（&T,i）/从i出发的搜索已完成，输出i 特点：与NonSuccFirstTopSort算法类似；若G有环，则不能正常工作,
