《数据结构MST》ppt课件

1、7.4.2 最小生成树（ Minimum Spanning Tree）设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)；2TuvvuuvvuTUUV-UV-U构造MST： 就是找轻边扩充到当前生成的树T（U，

2、TE）中U红点集、红边集，构成TV白点集、白边集紫边集连接红点和白点的边轻边权最轻的紫边，或最短紫边(若权为长度):（u1，v1）3u1v1UV-U5501523u2u3v2v31、Prim算法特点当前的形成的集合T（U，TE）始终是一棵树T中的顶点和边均为红色基本思想（贪心法）设V(G)=0,1,n-1算法的每一步均是在连接红、白点集的紫边中选一轻边扩充到T（贪心），T从任意一点r开始（r为根），直至UV为止。MST性质保证了贪心选择策略的正确性。 41、Prim算法如何找轻边？可能的紫边集 设红点集|U|=k, 白点集|V-U|=n-k，则可能的紫边数为：k(n-k)。 在此紫边集中选择轻

3、边效率太低。构造候选轻边集 构造较小的紫边集，但保证轻边在其中。 因为，v白点集，从v到各红点的紫边中，只有最短的那一条才可能是轻边，所以只须保留所有nk个白点所关联的最短紫边作为轻边候选集即可。 显然，轻边是该候选集中权最轻的边。 可以针对红点集来构造候选轻边集吗？51、Prim算法如何维护候选轻边集？当把轻边（u，v）扩充至T中时，v由白点变为红点，紫边（u，v）变为红边；对每个剩余白点j，边（v，j）由白变紫，此新紫边的长度可能小于白点j原来所关联的最短紫边。须调整候选轻边集，用更短的新紫边（v，j）取代原来关联于j的最短紫边。 61、Prim算法算法梗概PrimMST(G,T,r) /

4、求以r为根的MST InitCandidateSet(); /初始化，置初始的候选轻边集，置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)71、Prim算法实例80235416517234556023541651023541551450235415214502354152145023541521431、Prim算法存储结构

5、define Infinity INT_MAX /表示最大整数define n 100typedef int AdjMatrixnn; /邻接矩阵typedef struct /树边 int fromvex, tovex; /起点、终点 int len; /边长度，权值 MSTn-1;设邻接矩阵初值：不存在的边其权值为Infinity91、Prim算法算法求精初始化将根r涂红加入红点集U，TE。对每个白点i (0i n-1, ir ), i所关联的最短紫边（r,i）的长度为Gri, 这n-1条最短紫边构成了初始的候选轻边集。因为树边为空，故将T0.n-2全部用来存放候选轻边集。void Ini

6、tCandidateSet (AdjMatrix G, MST T, int r) int i, k=0; for (i=0; in; i+) /依次形成白点i初始的最短紫边存放在Tk中 if ( i != r ) Tk.fromvex=r; /紫边起点为红点 Tk.tovex=i; /紫边终点为白点 Tk+.len=Gri; /紫边边长度，权值 ;101、Prim算法算法求精选轻边在当前候选轻边集Tk.n-2中，选长度最短的紫边。(Note:T0.k-1是红边集，T也是树，为什么针对白点构造候选集更好？)void SelectLightSet ( MST T, int k) int i, m

7、inpos, min=Infinity; for (i=k; in-1; i+) /遍历候选集找轻边 if ( Ti.len min ) min=Ti.len; /紫边起点为红点 minpos=i; /记录当前最短紫边的位置 if (min=Infinity ) error( “G不连通”）; return minpos; /轻边为Tminpos ;111、Prim算法算法求精调整候选轻边集设轻边（u,v）涂红后加入到树边中，Tk.n-2是待调整的候选轻边集，则须根据新红点v调整Tk.n-2 。void ModifyCandidateSet ( AdjMatrix G, MST T, int

8、k, int v) int i, d; /v是新红点 for (i=k; in-1; i+) /遍历候选集 d=GvTi.tovex; /Ti的终点是白点，d是新紫边的长度 if ( dTi.len ) /d小于白点Ti.tovex原关联最短紫边长度 Ti.len=d; Ti.fromvex=v; /新紫边取代Ti.tovex原来的最短紫边 ;121、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+)

9、 /求kth条n-1条树边 mSelectLightEdge(T,k); / 在Tk.n-2选轻边Tm TmTk;/轻边和紫边Tk交换，将其扩充至树中 vTk.tovex; /交换后红边集为T0.k,v是新红点 ModifyCandidateSet(G,T,k+1,v); /Tk+1.n-2是新候选集，根据新红点v调整候选轻边集 131、Prim算法时间分析初始化：O(n)在k循环中： Select中循环次数为n-k-1 / 在Tk.n-2选轻边Tm Modify中循环次数为n-k-2 /Tk+1.n-2是新候选集，根据新红点v调整候选轻边集 因此： 时间为O(n2)，与边无关，适合稠密图。1

10、42、Kruskal算法特点：当前形成的集合T除最终结果外，始终是森林，无环。算法： KruskalMST(G) T=(V, )；/包含n个顶点，不含边的森林； 依权的增序对E(G)中边排序，设结果在E0.e-1; for (i=0; ie; i+) 取E中第i条边(u,v); if （u和v分属森林T中两棵不同的树） then TT（u,v）; /否则产生回路，放弃此边 if （T已是一棵树）then return T； /endfor 152、Kruskal算法（续）例子：略时间：对边排序O(elge)for循环中： 检测每条边的两个顶点是否在同一连通分量（树）上 只要采用合适的数据结构，

11、检测时间为O(lge) 因此，此时间亦为O(elge)。总计： O(elge)结论：时间性能主要取决于边数，适合稀疏图。167.5 拓扑排序 有向无环图DAG（Directed Acyclic Graph）的应用171、相关概念集合与关系笛卡儿积：设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，记为xRy。集合A上的关系R是

12、自反的（反身的），若对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。例子： 数之间的相等关系，具有自反性，对称性，传递性，反对称性； 数之间的小于关系，具有传递性，反对称性； 数之间的小于等于关系，具有自反性，传递性，反对称性；181、相关概念偏序（部分序） 设R是集合A上的一个关系，若R具有自反性，反对称性和传递性，则称R是A上的偏序关系，A是偏序集（对于R）。 偏序关系R一般记为，若将关系看作是比较，则偏序

13、关系是指集合中仅有部分元素是可以比较的。全序（线性序） 设R是集合A上的一个偏序关系，若对 x,y A，必有xRy或yRx， 则称R是A上的全序关系，A是全序集（对于R）。 数集合上的大小关系是全序关系 全序关系是指集合中全体成员之间均可比较。191、相关概念拓扑排序 将一个dag图G（V，E）中的所有顶点排成一个线性序列，使得对G中任意一对顶点u和v，若 E，则在线性序列中u在v之前。这种给顶点定序的操作称为拓扑排序。拓扑（有序）序列：上述顶点的线性序列称为拓扑序列。唯一吗？几何意义：将G中顶点按拓扑序列的次序排成一行，则G中所有的有向边的指向均为从在到右例子：20v2v3v1v4v3v1v

14、2v41、相关概念拓扑排序拓扑排序成功的充要条件：无环。例子：应用背景 有向图G可表示事件之间的先后关系，顶点表示事件，边表示事件之间的依赖关系： E(G)表示u先于v发生，u完成后才能开始v。 若G表示施工图、生产流程图、学习计划安排，则在只能串行工作时，拓扑序列是一种可行的方案或计划。21v4v3v2v1v3v1v2v42、求拓扑序列？(1) 无前驱的顶点优先算法思想：输出当前入度为0的顶点。 NonPreFirstTopSort（G） while( G中有入度为0的顶点 ) do 从G中选1个入度为0的顶点v输出之； 从G中删v及其出边，出边终点的入度减1； if ( 输出的顶点数 |

15、V(G) | ) then Error ( “G有环，排序失败” ); 例子：算法实现：222、求拓扑序列？(2) 无后继的顶点优先算法思想：输出当前出度为0的顶点。 NonSuccFirstTopSort（G） /应选G的逆邻接表 while( G中有出度为0的顶点 ) do 从G中选1个出度为0的顶点v输出之； 从G中删v及其入边，入边起点的出度减1； if ( 输出的顶点数 | V(G) | ) then Error ( “G有环，排序失败” ); 输出结果：逆拓扑序列算法实现：232、求拓扑序列？(3) 利用dfs遍历算法原理：因为当从某顶点v出发的dfs搜索完成时，v的所有后继必定均已访问过（想象他们均已被删除），此时