《数据结构》课程教学资源（教案设计）09 关键路径

编号：010 课程 章节 课程讲 数据结构 第六章图 45分钟 名称 名称 6.5有向无环图及其应用 授学时 学习要求 知识点 熟练 课堂 识记理解 掌握 应用 分析 综合 教学 拓扑排序 √ √ 目的 关键路径 态度积极主动学习 能力利用深关键路径的计算方法解决实际工程问题。 教学内容（教学过程设计） 教学安排 6.5有向无环图及其应用 10分钟 提出问题：什么是工程？引出AOV网的建模作用 给出AOV网的定义，通过一个例子说明AOV网的性质 给出拓扑序列和拓扑排序的定义，说明拓扑排序的结果 根据拓扑排序的定义得出拓扑排序的基本思想，运行一个实例，展示拓 5分钟 扑排序算法的求解过程 考察拓扑排序的求解过程，设计数据结构，写出拓扑排序算法的C语言 20分钟 代码 给出AOE网的定义，通过一个例子说明AOE网的性质 5分钟 结合实例给出关键路径和关键活动的概念 分析关键路径的构成，给出关键路径的求解思想 运行一个实例，展示关键路径的求解过程（关键是4个参量，注意强调 4个参量的求解顺序及含义 总结关键路径的求解过理 学提示 ,拓扑排序算法修改了图的邻接表存储，并采用栈作为辅助数据结构，引 导学生掌握从算法的时间性能出发，设计合适的存储结构的方法 关键路径的含义与直觉不同，一般学生都认为关键路径是从始点到终点 的最短路径长度。在讲授中注意结合一具较小的实例理解其 注意将AOV网和AOE网进行比较，将求拓扑序列与求关键路径结合起 来，即在求关键路径的同时判断是否存在拓扑序列 求关键路径涉及到的4个参量较难理解

编号：010 课程 名称 数据结构 章节 名称 第六章 图 6.5 有向无环图及其应用 课程讲 授学时 45 分钟 课堂 教学 目的 知 识 点 学 习 要 求 识记 理解 熟练 掌握 应用 分析 综合 拓扑排序 √ √ √ √ 关键路径 √ √ √ √ 态度 积极主动学习 能力 ➢ 利用深关键路径的计算方法解决实际工程问题。 教学内容（教学过程设计） 教学安排 6.5 有向无环图及其应用 ↓ 提出问题：什么是工程？引出 AOV 网的建模作用 给出 AOV 网的定义，通过一个例子说明 AOV 网的性质 给出拓扑序列和拓扑排序的定义，说明拓扑排序的结果 根据拓扑排序的定义得出拓扑排序的基本思想，运行一个实例，展示拓 扑排序算法的求解过程 考察拓扑排序的求解过程，设计数据结构，写出拓扑排序算法的 C 语言 代码 ↓ 给出 AOE 网的定义，通过一个例子说明 AOE 网的性质 结合实例给出关键路径和关键活动的概念 分析关键路径的构成，给出关键路径的求解思想 运行一个实例，展示关键路径的求解过程（关键是 4 个参量）。注意强调 4 个参量的求解顺序及含义 总结关键路径的求解过程 ↓ 教学提示： ➢ 拓扑排序算法修改了图的邻接表存储，并采用栈作为辅助数据结构，引 导学生掌握从算法的时间性能出发，设计合适的存储结构的方法 ➢ 关键路径的含义与直觉不同，一般学生都认为关键路径是从始点到终点 的最短路径长度。在讲授中注意结合一具较小的实例理解其 ➢ 注意将 AOV 网和 AOE 网进行比较，将求拓扑序列与求关键路径结合起 来，即在求关键路径的同时判断是否存在拓扑序列 ➢ 求关键路径涉及到的 4 个参量较难理解 10 分钟 5 分钟 20 分钟 5 分钟

重点 拓扑排序算法。 重点 难点： 关键路径算法。 难点 教学策略： 对策 在授课过程中采用多媒体教学，首先还原问题的本来面目一 提出问题，引导学生 积极参与 一尝试解决问题，在讨论的基础上给出结论一 —讲授教学内容、解决 问题，最后采用课件进行算法的动态演示，加大课堂信息量，提高教学效率。 教学 教学方法：导入，配合图形、实例讲解，提问、讨论 方法 教学手段：PPT课件，板书，动画演示 与 手段 作业： (1)有向网如图6.30所示，试用迪杰斯特拉算法求出从J顶点a到其他各顶点 间的最短路径，完成表6.9. (2)对图所示的AOE-网： ①求这个工程最早可能在什么 10 时间结束； 2 ②求每个活动的最早开始时间 19 6 作业 及 和最迟开始时间； 15 课外 ③确定些活动是关键活动 荐 资源 课后导读： y 图的基本术语在本科生的教材中大同小异，更深入的介绍请参见《图论简明教 程》(Frd Buckley著李慧霸译清华大学出版社) 深度优先遍历图的性质和广度优先遍历图的性质请参见《数据结构与算法》 (齐德昱清华大学出版社) 拓扑排序算法的其它讨论参见《数据结构与算法》（许卓群清华大学出版社】 “某路径为关键路径的充分必要条件是其上的活动均为关键活动的证明请参 见《数据结构与算法》（齐德昱清华大学出版社）】 教学 后记

重点 与 难点 对策 重点： 拓扑排序算法。 难点： 关键路径算法。 教学策略： 在授课过程中采用多媒体教学，首先还原问题的本来面目——提出问题，引导学生 积极参与——尝试解决问题，在讨论的基础上给出结论——讲授教学内容、解决 问题，最后采用课件进行算法的动态演示，加大课堂信息量，提高教学效率。 教学 方法 与 手段 教学方法：导入，配合图形、实例讲解，提问、讨论 教学手段：PPT 课件，板书，动画演示 作业 及 课外 推荐 资源 作业： （1）有向网如图 6.30 所示，试用迪杰斯特拉算法求出从顶点 a 到其他各顶点 间的最短路径，完成表 6.9。 （2）试对图所示的 AOE-网： ① 求这个工程最早可能在什么 时间结束； ② 求每个活动的最早开始时间 和最迟开始时间； ③ 确定哪些活动是关键活动 课后导读： ➢ 图的基本术语在本科生的教材中大同小异，更深入的介绍请参见《图论简明教 程》（Frd Buckley 著 李慧霸译 清华大学出版社） ➢ 深度优先遍历图的性质和广度优先遍历图的性质请参见《数据结构与算法》 （齐德昱 清华大学出版社） ➢ 拓扑排序算法的其它讨论参见《数据结构与算法》（许卓群 清华大学出版社） ➢ “某路径为关键路径的充分必要条件是其上的活动均为关键活动”的证明请参 见《数据结构与算法》（齐德昱 清华大学出版社） 教 学 后记