CH7图讲解.ppt

分析 如何找e(i)=l(i)的关键活动？ 求关键路径步骤 求ve(i) 求vl(j) 求 e(i) 求 l(i) 计算l(i)-e(i) 7.7 两点之间的 最短路径问题 一、求从某个源点到其余各顶点的最短路径 例如: 5 14 8 21 3 a e d c b g f a b c d e g f 19 5 14 6 27 16 8 21 3 a e 12 d c b g f 7 6 Prim 算法：初始值为某个顶点(即1个连通分量)， 在一个连通分量上添加边和顶点。 Kruskal 算法：初始值为n个顶点(即n个连通分量)， 每次使连通分量的个数减一。 用一句话描述两种算法 作业：利用Prim算法、Kruskal算法构造最小生成树。 g d e a f c b h 2 1 1 1 2 2 2 1 2 3 4 g d e a f c b h 2 1 1 1 2 2 1 结果： 7.1 图的抽象数据类型定义 7.2 图的存储表示 7.3 图的遍历 7.4 最小生成树 7.7 两点之间的最短路径问题 7.5 拓扑排序 7.6 关键路径 A C B D E F 有向无环图 7.5 拓扑排序 如何判断一个图是否存在环(回路)? 对无向图--- 深度优先遍历。 对有向图--- 拓扑排序。 A C B D E F 无向有环图 有向无环图的应用 . 描述含用公共子式的表达式; . 软件专业的课程学习计划; . 工作流图或程序数据流图; . …… * - a + / b c d * - a + / b c d c + b ( a - (b+c) ) * ( b+c ) / d 课程编号 课程名称 C1 程序设计基础 C2 离散数学 C3 数据结构 C4 汇编语言 C5 语言的设计和分析 C6 计算机原理 课程编号 课程名称 C7 编译原理 C8 操作系统 C9 高等数学 C10 线性代数 C11 普通物理 C12 数值分析 (C1,C2,C3,C4,C5,C7,C9,C10,C11,C6,C12,C8) (C9,C10,C11,C6,C1,C12,C4,C2,C3,C5,C7,C8) C12 C1 C9 C7 C8 C4 C2 C3 C10 C11 C5 C6 AOV网(Activity On Vertex) 顶点表示活动, 弧表示优先关系 何谓“拓扑排序”？ 对有向图进行如下操作: 按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。 由此所得顶点的线性序列称之为拓扑有序序列。 例如：对于下列有向图 B D A C 可求得拓扑有序序列： A B C D 或 A C B D B D A C 对于下列有向图 不能求得它的拓扑有序序列。 因为图中存在一个回路 {B, C, D} 结论：如果有向图存在环，则不能够进行拓扑排序；反之，如果对一个有向图不能够进行拓扑排序，则一定存在环。 因此，通过拓扑排序可以判断一个有向图是否存在环。 如何进行拓扑排序？ 一、从有向图中选取一个没有前驱的顶点， 并输出之; 三、重复上述两步，可能得到两种结果： 1. 图空——拓扑排序成功! 2. 图不空,但找不到无前驱的顶点——有环! 二、从有向图中删去此顶点以及所有以它 为尾的弧; a b c g h d f e a b h c d g f e 没有前驱的顶点 删除顶点及以它为尾的弧 ?? 弧头顶点的入度减1 a b c g h d f e 需要设一个数组inDegree[w]，记录顶点的入度数 ?? 入度为零的顶点 初始化 inDegree[w]； while(取一个新的入度为零的顶点v){ printf(v); ++m; //对输出顶点计数 for( w=FirstAdj(v); w; w=nextAdj(v,w))