《图_拓扑排序关键路径最短路径.docx》由会员分享，可在线阅读，更多相关《图_拓扑排序关键路径最短路径.docx（17页珍藏版）》请在三一文库上搜索。
1、1 拓扑排序1问题；假设以有向图表示一个工程的施工图或 程序的数据流图，则图中不允许出现回 路.(有向无环图)检查有向图中是否存在回路的方法 之一，是对有向图进行拓扑排序。2何谓拓扑排序” ?(1)按照有向ffl箱出的次殍关系，将图 中顶点 J*成一址性序列。(2)对于祈向中没有眼定次序关系的顼堪, 則可以人为加上任想的次序关系。例如：对于下列有向图可求得拓扑有序序列：ABCD 或 ACBD反之，对于下列有向图BADC不能求得它的拓扑有序序列。定义:AOV网：弧表示活动的优先顺序, 顶点表示活动的网络AOV网中，不应该出现回路3如何对AOV网进行拓扑排序?(I)从有向图中选取一个没有前驱的顶点
2、, 并输出之；(2)从有向图中删去此顶点以及所有以它 为尾的弧；重复上述两步，直至图空，或者图不空但 找不到无前驱的顶点为止.abhcdgfe在算法中需要替代定性的概念没有前驱的顶点N入度为零的顶点删除顶点及以它为尾的弧二弧头顶点的入度减1为避免每次都要搜索入度为零的顶点，在算 法中设置一个“栈,以保存“入度为零”的顶 占八、0 2、关键路径问题；假设以有向网表示一个施工流图，弧 上的权值表示完成该项子工程所需时间. 问：哪些子工程项将影响整个工程的完成 期限的.关键工程定义AOE网；弧表示活动，顶点表示事 件，权表示活动的持续事件.特点，有源点和汇点，正常一无环整个工程完成的时间为: 的最长
3、路径。从AOE的源点到汇点如何求关键活动?“事件(顶点尸的最早发生时间M(j) ve(j)=从源点到顶点j的最长路径长度;“事件(顶点尸的最迟发生时间v/(k) vl(k)=从顶点k到汇点的最长路径长度。事件发生时间的计算公式: ve（源点）=0;ve(j) = Maxve(i) + dut()表示以j为弧头的弧vl(汇点)=ve(汇点)； vl二 Mml(j) dut()vij表示以i为弧尾的弧假设第i条弧为vj, k 则对第i项活动言“活动(弧尸的最早开始时间e(i) e(i) = ve(j)；“活动(弧尸的 最迟开始时间1(1)/(i) = vl(k)-dut();e(i)= Id)的活
4、动就是关键活动abCdefghkve064577151418V10668710161418abacadbecedfegehfti匡khk权6451128774 2414e()0064577 1151023668871() 16J1471显然,算法的实现要点:求ve的顺序应该是按拓扌卜有序的次序;求V1的顺序应该是按拓扑逆序的次序;拓扑逆序序列即为拡扑有序序列的逆序列,应该在拓扑排序的过程中， 另设一个栈”记下拓扑有序序列逆序列.3、两点之间的最短路径问题-求从某个源点到其余各点的 最短路径每一对顶点之间的最短路径求从源点到其余各点的最短路径 的算法的基本思想：依最短路任的长度递增的次厚求傅1、
5、Dijkstra算法思想设置两个结点的集合S和T,集合S中存放已找到 最短路径的结点，集合T中存放当前还未找到最短 略径的结点. 初始状态时，集合S中只包含源点，设为0,然 后不斯从集合T中选择到源点旳略轻长度最短的结 点U加入到集合S中，集合S中每加入一个新的结点U 都要修改从源点vO到集合T中剩余结点的当前最短 路径长度值.集合T中各结点的新的当前最短路径长度值，为 原来的最短路径长度值与从源点过结点u到达该结 点的路径长度中的较小者.此过程不断重复，直到 集合T中的结点全部加入到集合S中为止.X015ocococ30X0410x830018ococ0例：利用Dijkstra算法求如下所示
6、图 中从顶点A到其余各顶点的最短路径的过程。2.每一对顶点之间的最短路径(1 )采用Dijkstra算法实现算法思想：每次以不同的结点作为源点，调 用狄克斯特拉算法求出从该源点到其余结点的 最短路径。需重复调用n次Dijksira算法。(2)弗洛伊德算法的基本思想是:从 Vi ay Vj的所命在的路任中.址出一*长 度聂短的可以用如下递推公式描述；I-(ilUl=costSUlDhi|j=minD 汕川 jhDiiK4l何kj(归li91)其中，COSifilUl中存放着序号为啲结点到序号为j的结点之 间的权值；I户IHLH(归1011)麦示从结点讷到结点可的路径 上所经过的结点序号不大于1的短路径长度第8章小结U短郴严5算法iFloyd算法向图的应用 1邻接矩阵 邻接表 十字链表 邻接多i表存借结构4】f浹度优先* 適历广度优先技索图的连通分量（利用DFS）B的生咸村最小生成树/ Pm算法I Kruskal 算法下次内容 91静态査找表