数据结构教程第6章图2013.ppt

要找出关键路径，必须找出关键活动, 即不按期完成就会影响整个工程完成的活动。 关键路径 首先计算以下与关键活动有关的量： ⑴ 事件的最早发生时间Ve[k] ⑵ 事件的最迟发生时间Vl[k] ⑶ 活动的最早开始时间Ae[i] ⑷ 活动的最晚开始时间Al[i] 最后计算各个活动的时间余量 Al[k] - Ae[k]，时间余量为0者即为关键活动。 6.7 用边表示活动的网络(AOE网络) 集 合 V-S 集 合 S vk v vi Dijkstra算法的基本思想 6.5 最短路径 A B A E D C 10 50 30 10 100 20 60 S={A} A→B:(A, B)10 A→C:(A, C)∞ A→D: (A, D)30 A→E: (A, E)100 Dijkstra算法 6.5 最短路径 A B A E D C 10 50 30 10 100 20 60 S={A, B} A→B:(A, B)10 A→C:(A, B, C)60 A→D: (A, D)30 A→E: (A, E)100 B Dijkstra算法 6.5 最短路径 A B A E D C 10 50 30 10 100 20 60 S={A, B, D} A→B:(A, B)10 A→C:(A, D, C)50 A→D: (A, D)30 A→E: (A, D, E)90 B D Dijkstra算法 6.5 最短路径 A B A E D C 10 50 30 10 100 20 60 S={A, B, D, C} A→B:(A, B)10 A→C:(A, D, C)50 A→D: (A, D)30 A→E: (A, D, C, E)60 B D C Dijkstra算法 6.5 最短路径 A B A E D C 10 50 30 10 100 20 60 Dijkstra算法 S={A, B, D, C, E} A→B:(A, B)10 A→C:(A, D, C)50 A→D: (A, D)30 A→E: (A, D, C, E)60 B D C E 6.5 最短路径 图的存储结构：带权的邻接矩阵存储结构 数组dist[n]：每个分量dist[i]表示当前所找到的从始点v到终点vi的最短路径的长度。初态为：若从v到vi有弧，则dist[i]为弧上权值；否则置dist[i]为∞。 数组path[n]：path[i]是一个字符串，表示当前所找到的从始点v到终点vi的最短路径。初态为：若从v到vi有弧，则path[i]为vvi；否则置path[i]空串。 数组s[n]：存放源点和已经生成的终点，其初态为只有一个源点v。 设计数据结构 : 6.5 最短路径 1. 初始化数组dist、path和s； 2. while (s中的元素个数n) 2.1 在dist[n]中求最小值，其下标为k； 2.2 输出dist[k]和path[k]； 2.3 修改数组dist和path； 2.4 将顶点vk添加到数组s中； Dijkstra算法——伪代码 6.5 最短路径 6.6 用顶点表示活动的网络(AOV网络) AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网。 AOV网 什么是工程？工程有什么共性？ AOV网中出现回路意味着什么？ AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网。 AOV网 2.AOV网中不能出现回路 。 AOV网特点： 1.AOV网中的弧表示活动之间存在的某种制约关系。 什么是工程？工程有什么共性？ 6.6 用顶点表示活动的网络(AOV网络) 编号 课程名称 先修课 C1 高等数学 无 C2 计算机导论 无 C3 离散数学 C1 C4 程序设计 C1, C2 C5 数据结构 C3，C4 C6 计算机原理 C2，C4 C7 数据库原理 C4，C5，C6 C1 C2 C3 C4 C6 C5 C7 AOV网 6.6 用顶点表示活动的网络(AOV网络) 拓扑序列：设G=(V，E)是一个具有n个顶点的有向图，V中的顶点序列v1, v2, …, vn称为一个拓扑序列，当且仅当满足下列条件：若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。 拓扑排序：对一个有向图构造拓扑序列的过程称为拓扑排序 。 拓扑排序 拓扑序列使得AOV网中所有应存在的前驱和后继关系都能得到满足。 6.6 用顶点表示活动的