文档详情

图和广义表.ppt

发布:2017-06-16约1.85万字共110页下载文档
文本预览下载声明
* B D A C 反之,对于下列有向图 不能求得它的拓扑有序序列。 因为图中存在一个回路 { B, C, D } * 如何进行拓扑排序? 一、从有向图中选取一个没有前驱 的顶点,并输出之; 重复上述两步,直至图空,或者图不空但找不到无前驱的顶点为止。 二、从有向图中删去此顶点以及所 有以它为尾的弧; * a b c g h d f e a b h c d g f e 在算法中需要用定量的描述替代定性的概念 没有前驱的顶点 ?? 入度为零的顶点 删除顶点及以它为尾的弧 ?? 弧头顶点的入度减1 * 算法描述: 取入度为零的顶点v; while (v0) { printf(v); ++m; w = FirstAdj(v); while (w0) { inDegree[w]--; w = nextAdj(v,w); } 取下一个入度为零的顶点v; } if (mn) printf(“图中有回路”); * 7.7 关键路径 假设以有向网表示一个施工流图,弧上的权值表示完成该项子工程所需时间。 v1 v2 v3 v4 v5 v6 v7 v8 v9 6 4 5 2 1 1 8 7 2 4 4 源点 汇点 工程完成时间:从有向图的源点到汇点的最长路径。 AOE网(Activity On Edge):以边表示活动的网络。简称为活动边网络。 * “关键工程”即图的“关键活动”,指的是:该弧上的权值增加 将使有向图上的最长路径的长度增加。如图中的v1,v2, v2,v5, v5,v8, v8,v9。 v1 v2 v3 v4 v5 v6 v7 v8 v9 6 4 5 2 1 1 8 7 2 4 4 源点 汇点 6 1 7 4 问:哪些子工程项是“关键工程”? 即:哪些子工程项将影响整个工程的完成期限? * 如何求关键活动? “事件(顶点)” 的 最早发生时间 ve(j) ve(j) = 从源点到顶点j的最长路径长度; “事件(顶点)” 的 最迟发生时间 vl(k) vl(k) = 从顶点k到汇点的最短路径长度。 v1 v2 v3 v4 v5 v6 v7 v8 v9 6 4 5 2 1 1 8 7 2 4 4 源点 汇点 * 事件(顶点)发生时间的计算公式: ve(源点) = 0;(从源点开始向后递推) ve(j) = max{ve(i) + w(i, j)} vl(汇点) = ve(汇点); (从汇点开始向前递推) vl(i) = min{vl(j) – w(i, j)} v1 v2 v3 v4 v5 v6 v7 v8 v9 6 4 5 2 1 1 8 7 2 4 4 源点 汇点 设活动ak用弧i,j表示,其持续时间记为: w(i,j) i j ak * 假设第k条弧为 i, j。 则对第 k项活动而言: “活动(弧)”的 最早开始时间 ee(k) ee(k) = ve(i); “活动(弧)”的 最迟开始时间 el(k) el(k) = vl(j) – w(i,j); v1 v2 v3 v4 v5 v6 v7 v8 v9 6 4 5 2 1 1 8 7 2 4 4 源点 汇点 如果某条弧ak的el(k)和ee(k) i, j相等,则为关键活动;对于非关键活动,el(k)-ee(k) 即为该工程项的期限余量。 * 求关键路径步骤: 求ve(i) 求vl(j) 求ee(k) = ve(i) 求el(k) = vl(j)-w(i,j) 计算el(i)-ee(i) v1 v2 v3 v4 v5 v6 v7 v8 v9 a1=6 a2=4 a3=5 a6=2 a4=1 a5=1 a7=8 a8=7 a10=2 a11=4 a9=4 V1 V2 V3 V4 V5 V6 V7 V8 V9 顶点 Ve Vl 0 6 4 5 7 7 15 14 18 0 6 6 8 7 10 16 14 18 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 活动 ee el el-ee ? ? ? ? ? ? 0 0 0 0 2 2 6 6 0 4 6 2 5 8 3 7 8 1 7 7 0 7 10 3 15 16 0 14 14 0 0 3 3 * 本章学习要点 *  1. 熟悉图的各种存储结构及其构造算法,了解实际问题的求解效率与采用何种存储结构和算法有密切联系。  2. 熟练掌握图的两种搜索路径的遍历:遍历的逻辑定义、深度优先搜索和广度优先搜索的算法
显示全部
相似文档