§7.4.2最小生成树(Minimum Spanning Tree) ■MST性质一大多数算法都利用了此性质 ■设G是连通图，G的生成树不唯一 设G=(N,E)是一连通图，U是V的真子集，若 (u,v)是所有连接U和V-U的边中权最小的边 ■MST:权最小的生成树，树的权是各边上 轻边)，则一定存在G的一棵最小生成树包括此 的权值之和 边 ·应用 P:设G的任何一棵最小生成树均不包括u,V: ◆n个城市之间的通信网，可构建n(n-1)/2条线路 ◆n个城市连通至少要n-1条线路，G的生成树是 1个可行的方案 最小生成树是最经济的可行方案 构造MST: 1、Prim算法 就是找轻边扩充到当前生成的树打=(U,TE)中 ■特点 ◆U一红点集、红边桌，的成 。当前形成的集合T=(U,TE)始终是一棵树 VU一白点集、白边集 。T中的顶点和边均为红色 ◆戴边集一连接红点和白点的边 ◆轻边一权量轻的素边，或最短紫边（若权为长度）（山，V) ■基本思想（贪心法） ◆设V(G={0,1,n-1} 算法的每一步均是在连接红、白点集的紫 边中选一轻边扩充到T(贪心)，T从任意 一点r开始(r为根)，直至U=V为止。 MST性质保证了贪心选择策略的正确性。 . 1、Prim算法 1、 Prim算法 ■如何找轻边？ ■如何维护候选轻边集？ 冬可能的款边集 当把轻边(，v)扩充至T中时， 设红点集U=k,白点集V-U=n-k,则可能的紫边 数为：knk小： v由白点变为红点，紫边(u,v)变为红边： 在此戴边集中选择轻边效率太低。 对每个剩余白点j,边(，j)由白变紫，此 ◆构造候选轻边巢 新紫边的长度可能小于白点原来所关联的最短 构造较小的紫边集，但保证轻边在其中。 紫边。 因为，Vy∈自点集，从y到各红点的紫边中，只 须调整候选轻边集，用更短的新紫边(V,) 有最短的那一条才可能是轻边，所以只须保留所有 一k个白点所关联的最短薰边作为轻边候选集即可。 取代原来关联于的最短紫边。 显然，轻边是该候选集中权量轻的边。 可以针对红点集来构造候选轻边集吗？ 1
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)； T’ u v u’ v’ u v u’ v’ T U U V-U V-U 3 构造MST： 就是找轻边扩充到当前生成的树T＝（U，TE）中 U－红点集、红边集，构成T V-U－白点集、白边集 紫边集－连接红点和白点的边 轻边－权最轻的紫边，或最短紫边(若权为长度):（u1，v1） u1 v1 U V-U 5 50 15 u 23 2 u3 v2 v3 4 1、Prim算法 特点 当前形成的集合T＝（U，TE）始终是一棵树 T中的顶点和边均为红色 基本思想（贪心法） 设V(G)={0,1,…,n-1} 算法的每一步均是在连接红、白点集的紫 边中选一轻边扩充到T（贪心），T从任意 一点r开始（r为根），直至U＝V为止。 MST性质保证了贪心选择策略的正确性。 5 1、Prim算法 如何找轻边？ 可能的紫边集 设红点集|U|=k, 白点集|V-U|=n-k，则可能的紫边 数为：k(n-k)。 在此紫边集中选择轻边效率太低。 构造候选轻边集 构造较小的紫边集，但保证轻边在其中。 因为，∀v∈白点集，从v到各红点的紫边中，只 有最短的那一条才可能是轻边，所以只须保留所有n －k个白点所关联的最短紫边作为轻边候选集即可。 显然，轻边是该候选集中权最轻的边。 可以针对红点集来构造候选轻边集吗？ 6 1、Prim算法 如何维护候选轻边集？ 当把轻边（u，v）扩充至T中时， v由白点变为红点，紫边（u，v）变为红边； ∵对每个剩余白点j，边（v，j）由白变紫，此 新紫边的长度可能小于白点j原来所关联的最短 紫边。 ∴须调整候选轻边集，用更短的新紫边（v，j） 取代原来关联于j的最短紫边
1、Prim算法 1、Prim算法 ■算法梗橛 ■实例 PrimMST(G,T,)(求以r为根的MST InitCandidateSet(...); 物翰化，夏始的候选轻边集，量T=(任，◆) for(k=0:k<n-1;k++){棠T的n-1条制边 (u,v卢SelectLightEdge(:遮轻边，可能不廉 TE=TEU{(u,v)); 特uy涂红加入时中，自点v加入红点衡 ModifyCandidateSet(...); 根据断红点调童操选轻边 算法终止时U=V,T=V,TE) 1、Prim算法 1、Prim算法 ■算法求精一初始化 ■存储结构 将根涂红加入红点集U,TE=中。 #define Infinity INT_MAX表示最大整数 鸡金锡高经站题药餍耀蕊接 #define n 100 typedef int AdjMatrix[njn;I邻接矩阵 因为树边为空，故将T0.-2全部用来存放候选轻边集。 typedef struct{边 void InitCandidateSet (AdjMatrix G,MST T,int r){ int i,k=0; int fromvex,tovex;起点、，点 for(=O:i长n;i计+)依次形成白点初翰的量短营边存放在士中 int len;/边长度，权值 if (i=r){ MST[n-1]; Tk.fromvex-=r;蒙边起点为红点 Tk.tovex-=i:案边赞点为白点 设邻接矩阵初值：不存在的边其权值为Infinity Tk+.len=Gr;赏边长度，钗值 1、Prim算法 1、Prim算法 算法求精一选轻边 ■算法求精一调整候选轻边集 在当前楼进是贽透，也；蒡到智腔换远 设轻边(uy)涂红后加入到制边中，Tk-2是待调整 集更好？) 的候选轻边集，则须根据新社点整Tk.-2。 void ModifyCandidateSet AdjMatrix G,MST T,int k,int v){ void SelectLightSet MST T,int k){ inti,d;h是新红点 r路读选集拉轻边 f0r(=k;i<n-1;i计+){速历摸选第 d=G小yT.tovex;T四的蜂点是白点，d是斯紫边的长盘 if (T[il.len min mi=T.len:赏边起点为红点 if(d<T问.len){u小千白点move原关联最姬紫边长度 minpos=-i:记豪当前最短黛动的位■ Til.len=d; } T问.fromvex=-V;新紫边取代T,toe原来的绿短素边 if(min=Infinity)error(“G不连通")； return minpos;:/径边为T[minpos } 2
2 7 1、Prim算法 算法梗概 PrimMST(G,T,r) { //求以r为根的MST InitCandidateSet(…); //初始化，置初始的候选轻边集，置T＝（{r },φ） for (k=0; k<n-1; k++) { //求T的n-1条树边 (u,v)=SelectLightEdge(…); //选轻边，可能不唯一 TE＝TE∪{(u,v)}; //将(u,v)涂红加入树中，白点v加入红点集 ModifyCandidateSet(…); //根据新红点v调整候选轻边集 } } 算法终止时U＝V，T=(V,TE) 8 1、Prim算法 实例 0 2 3 4 5 1 6 5 1 7 3 2 4 5 5 6 0 2 3 4 5 1 6 5 1 ∞ ∞ 0 2 3 4 5 1 5 5 1 4 5 0 2 3 4 5 1 5 2 1 4 5 0 2 3 4 5 1 5 2 1 4 5 0 2 3 4 5 1 5 2 1 4 3 9 1、Prim算法 存储结构 ＃define Infinity INT_MAX //表示最大整数 ＃define n 100 typedef int AdjMatrix[n][n]; //邻接矩阵 typedef struct { //树边 int fromvex, tovex; //起点、终点 int len; //边长度，权值 } MST[n-1]; 设邻接矩阵初值：不存在的边其权值为Infinity 10 1、Prim算法 算法求精－初始化 将根r涂红加入红点集U，TE＝φ。 对每个白点i (0≤i ≤n-1, i≠r ), i所关联的最短紫边（r,i） 的长度为G[r][i], 这n-1条最短紫边构成了初始的候选轻边 集。 因为树边为空，故将T[0..n-2]全部用来存放候选轻边集。 void InitCandidateSet (AdjMatrix G, MST T, int r) { int i, k=0; for (i=0; i<n; i++) //依次形成白点i初始的最短紫边存放在T[k]中 if ( i != r ) { T[k].fromvex=r; //紫边起点为红点 T[k].tovex=i; //紫边终点为白点 T[k++].len=G[r][i]; //紫边长度，权值 } } ; 11 1、Prim算法 算法求精－选轻边 在当前候选轻边集 T[k..n-2] 中，选长度最短的紫边。 (Note:T[0..k-1]是红边集，T也是树，为什么针对白点构造候选 集更好？) void SelectLightSet ( MST T, int k) { int i, minpos, min=Infinity; for (i=k; i<n-1; i++) //遍历候选集找轻边 if ( T[i].len < min ) { min=T[i].len; //紫边起点为红点 minpos=i; //记录当前最短紫边的位置 } if (min==Infinity ) error( “G不连通”）; return minpos; //轻边为T[minpos] } ; 12 1、Prim算法 算法求精－调整候选轻边集 设轻边（u,v）涂红后加入到树边中，T[k..n-2]是待调整 的候选轻边集，则须根据新红点v调整T[k..n-2] 。 void ModifyCandidateSet ( AdjMatrix G, MST T, int k, int v) { int i, d; //v是新红点 for (i=k; i<n-1; i++) { //遍历候选集 d=G[v][T[i].tovex]; //T[i]的终点是白点，d是新紫边的长度 if ( d<T[i].len ) {//d小于白点T[i].tovex原关联最短紫边长度 T[i].len=d; T[i].fromvex=v; //新紫边取代T[i].tovex原来的最短紫边 } } } ;
1、Prim算法 1、Prim算法 ■算法求精一最终算法 void PrimMST(AdjMatrix G,MST T,int r){ ■时间分析 int k,m,v; 初始化：O(n) InitCandidateSet(G,T,r);彻蛤候选集To.,n2 在k循环中： for(k=0;k<n-1;k+){求n-1条衡边中的k条 Select中循环次数为n-k-1∥在Tk.n-2选轻边Tm m=SelectLightEdge(T,k); Modify中循环次数为n-k-2 ∥在Tk.n-2习选轻边Tm间 Tk+1-2]是新候选集，报据斯红点v词整候选轻边、 T[m]→T[k灯；轻边和紫边T的交换，将其扩充至树中 因此： y=T[K].tovex;交换后红边集为TO.的，v是斯红点 时间为0，与边无关，适合稠密图。 ModifyCandidateSet(G,T,k+1,v); 厅k+1-2习是新候选第，根据新红点候选轻边编 2、Kruskal算法 2、Kruskal算法（续） ■特点：当前形成的集合T除最终结果外，始终是森林，无环。 ■算法： 例子：略 ■时间： KruskalMST(G){ T=,):包含n个顶点，不含边的森林： ◆对边排序O(elge) ◆for循环中： 依权的增序对E(G)中边排序，设结果在E0.e-1小： 检测每条边的两个顶点是否在同一连通分量（制）上 for(=0;i长e;it+)( 取E中第条边(u,店 只要采用合适的败据结构，检测时间为O(g) if(u和v分黑森林T中两棵不同的树)then 因此，此时间亦为o(elge)。 $总计： T=TU((u,v):否则产生回路，放弃此边 f(T已是一棵树)then return T: O(elge) M/endfor ■结论：时间性能主要取决于边数，适合稀琉图。 1、相关概念 ■集合与关系 §7.5拓扑排序 ◆信吉是公意记到为成的集合（《eAy 有向无环图DAG(Directed :必的减美泽 个完关系，他酒了教合A中行两 Acyclic Graph)的应用 个完意之间的关系，若区，yR,则称x和y有关系R,亦可记为xRy, 香和没有关系R,记为xRy。 ◆算合A上的关系R是自反的（反身的），若对x∈A,都有xRx, ◆算合A上的关系R是对物的，着xRy,则yRx,其中，x,y∈A ◆算合A上的关系R是反对察的，若xRy,yRx,则必有x=y其中xy∈A。 ◆桌合A上的关系R是传遭的，若xRy,yRZ,则XR.其中x,y2∈A 数之向的相够关暴，具有自反性，对称性，传递性，反对称性 败之闻的小于关暴，具有传递性，反对称性： 数之间的小于等于关系，具有自反性，传递性，反对称性： 3
3 13 1、Prim算法 算法求精－最终算法 void PrimMST(AdjMatrix G, MST T, int r) { int k,m,v; InitCandidateSet(G, T, r);//初始候选集T[0..n-2] for (k=0; k<n-1; k++) { //求n-1条树边中的kth条 m＝SelectLightEdge(T,k); // 在T[k..n-2]选轻边T[m] T[m]↔T[k];//轻边和紫边T[k]交换，将其扩充至树中 v＝T[k].tovex; //交换后红边集为T[0..k],v是新红点 ModifyCandidateSet(G,T,k+1,v); //T[k+1..n-2]是新候选集，根据新红点v调整候选轻边集 } } 14 1、Prim算法 时间分析 初始化：O(n) 在k循环中： Select中循环次数为n-k-1 // 在T[k..n-2]选轻边T[m] Modify中循环次数为n-k-2 //T[k+1..n-2]是新候选集，根据新红点v调整候选轻边集 因此： 时间为O(n2)，与边无关，适合稠密图。 15 2、Kruskal算法 特点：当前形成的集合T除最终结果外，始终是森林，无环。 算法： KruskalMST(G){ T=(V, φ)；//包含n个顶点，不含边的森林； 依权的增序对E(G)中边排序，设结果在E[0..e-1]; for (i=0; i<e; i++) { 取E中第i条边(u,v); if （u和v分属森林T中两棵不同的树） then T＝T∪{（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、相关概念 集合与关系 笛卡儿积：设A、B是两个集合，所有序偶(x,y)构成的集合（x∈A, y ∈B ），称为A，B的笛卡儿积，记为A×B。 二元关系：集合A×B的一个子集R，称为集合A与B上的一个二元关系， 简称关系。若B＝A，则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,则必有x＝y.其中x,y ∈A。 集合A上的关系R是传递的，若xRy，yRz，则xRz。其中x,y,z ∈A。 例子： 数之间的相等关系，具有自反性，对称性，传递性，反对称性； 数之间的小于关系，具有传递性，反对称性； 数之间的小于等于关系，具有自反性，传递性，反对称性； R
1、相关概念 1、相关概念 ■偏序（部分序） ■拓扑排序 设R是集合A上的一个关系，若R具有自反性，反对称性和 传递性，则称R是A上的偏序关系，A是序集（对子R), 将一个dag图G=(V,E)中的所有顶点排成一个线性序 列，使得对G中任意一对顶点u和v,若∈E,则在线性序 偏序关系一般记为≤，若将关系看作是比较，则偏序关系 列中u在v之前。这种给顶点定序的操作称为拓扑排序。 是指集合中仅有部分元素是可以比较的。 ◆拓补（有序）序列：上述顶点的战性序列将为拓扑序列。曹一到 ■全序（线性序） ◆几侧意义：将G中顶点坡拓扑序列的次序样成一行，则G中所有的有向边 的指向均为从在到右 设R是集合A上的一个偏序关系，若对 ◆例子： Vx,y∈A,必有xRy或yRx, 则称R是A上的全序关系，A是全序集（对于R)。 数集合上的大小关系是全序关系 全序关系是指第合中全体成圆之间均可比较。 1、相关概念 2、求拓扑序列？ 拓扑排序 (①)无前婴的顶点优先 ◆拓扑排序成功的充要条件：无环。 ◆算法愿狐：输出当前入度为0的顶点。 ◆例仔 NonPreFirstTopSort (G){ while(G中有入度为0的顶点)do( 从G中选1个入度为0的顶点v输出之： 从G中■及其出边，出边终点的入度减1： if(输出的顶点数p->next/图的出边 indegree[p->adjvex]t+;将i的情点j入度加i,片p>adjvex r然iit()Push(S,入度为0的项点入 4
4 19 1、相关概念 偏序（部分序） 设R是集合A上的一个关系，若R具有自反性，反对称性和 传递性，则称R是A上的偏序关系，A是偏序集（对于R）。 偏序关系R一般记为≤，若将关系看作是比较，则偏序关系 是指集合中仅有部分元素是可以比较的。 全序（线性序） 设R是集合A上的一个偏序关系，若对 ∀x,y ∈A，必有xRy或yRx， 则称R是A上的全序关系，A是全序集（对于R）。 数集合上的大小关系是全序关系 全序关系是指集合中全体成员之间均可比较。 20 1、相关概念 拓扑排序 将一个dag图G＝（V，E）中的所有顶点排成一个线性序 列，使得对G中任意一对顶点u和v，若 ∈E，则在线性序 列中u在v之前。这种给顶点定序的操作称为拓扑排序。 拓扑（有序）序列：上述顶点的线性序列称为拓扑序列。唯一吗？ 几何意义：将G中顶点按拓扑序列的次序排成一行，则G中所有的有向边 的指向均为从在到右 例子： v2 v v1 3 v4 v3 v1 v2 v4 21 1、相关概念 拓扑排序 拓扑排序成功的充要条件：无环。 例子： 应用背景 有向图G可表示事件之间的先后关系，顶点表示事件， 边表示事件之间的依赖关系： ∈E(G)表示u先于v发生，u完成后才能开始v。 若G表示施工图、生产流程图、学习计划安排，则在只能串行 工作时，拓扑序列是一种可行的方案或计划。 v4 v3 v2 v1 v v1 3 v2 v4 22 2、求拓扑序列？ (1) 无前驱的顶点优先 算法思想：输出当前入度为0的顶点。 NonPreFirstTopSort（G）{ while( G中有入度为0的顶点 ) do { 从G中选1个入度为0的顶点v输出之； 从G中删v及其出边，出边终点的入度减1； } if ( 输出的顶点数 p->next)//扫描i的出边表 indegree[p->adjvex]++; //将的终点j入度加1，j=p->adjvex InitStack(&S); for (i=0; i<G.n; i++) if ( !indegree[i] ) Push(&S,i);//入度为0的顶点入栈
2、求拓扑序列？ 2、求拓扑序列？ while(IStackEmpty(&S)K钱非空时.里中仍有入度为0的顶点 (②)无后继的顶点优先 =Pop(&S外：雕无前驱的顶点 ◆韩法惠想，轴出当前出度为0的顶点。 printf%cr",G.adjlist0.vertex对：输出顶点 count-+;输出顶点计整 NonSuccFirstTopSort(G)(查塘G的弹凄 for(p=G,adjlist坝，irstedge;p;p=p->nexr归指顶点i的出边囊 while(G中有出度为0的顶点)do( 户p>adjvex;你是的铸点 从G中选1个出度为0的顶点输出之： indegree们-1所的入度减1，相当于测出边<P 从G中V及其入边，入边起点的出度减1： f(indegreel们)Push&S,店所的入虚为0测进钱 f(输出的顶点数<V(G)I)then Eror("G有环，排序失败”方 if count<G.n printf("InG is not a DAGIn"); ◆输出编果：逆拓扑序列 时同：初始化O(n+e ◆算法实现，略 排序成功时量大：每个顶点入出钱各1次，每个边表节点被恤查1次0衍+) 2、求拓扑序列？ (③)利用dr遍历算法 ◆原理：因为当从莱顶点v出发的s撞康完成时，v的所有后蟑必定均已访 照 ◆算法：， DFSTopSort(G,i,T)(在DFSTraverse中调用此算法，T是钱 visited门=TRUE;访问i for(所有的嘟捷点)即<i,EE(G) if(visited0的)】 DFSTopSort(Gj,T): Push(8T,)∥从出发的搜案已完成，输出i ◆特点：与NonSuccFirstTopSort算法类似：香G南再，则本幢重常工 5
5 25 2、求拓扑序列？ while( !StackEmpty(&S) ){//栈非空时,图中仍有入度为0的顶点 i=Pop(&S); //删除无前驱的顶点i printf(“%c\t”,G.adjlist[i].vertex); //输出顶点i count++; //输出顶点计数 for (p=G.adjlist[i].firstedge; p; p==p->next){ //扫描顶点i的出边表 j=p->adjvex; //j是的终点 indegree[j]--； //j的入度减1，相当于删出边 if ( ! indegree[j] ) Push(&S, j); //j的入度为0则进栈 } } if ( count ∈E(G) if ( !visited[j] ) DFSTopSort(G,j,T)； Push（&T, i）//从i出发的搜索已完成，输出i } 特点：与NonSuccFirstTopSort算法类似；若G有环，则不能正常工作
