《数据结构》课程教学资源（教案设计）08 图的遍历

编号：009 课程 章节 课程讲 数据结构 第六章图 45分钟 名称 名称 6.3图的遍历 授学时 学习要求 课堂 知识点 熟练 识记理解 分析 掌握 应用 教学 综合 图的遍历 √ √ √ 目的 态度积极主动学习 能力>利用深度优先搜索、广度优先搜索解决简单的应用问题 教学内容（教学过程设计） 教学安排 复习#导入新课 5分钟 复习二叉树的滨历，理解访问的含义以及遍历的次序，导人新课-图的 遍历， 6.3图的遍历 20分钟 提出问题：图的這历要解决哪些关键问题 给出深度优先遍历的思想，通过实例分析深度优洗遍历过程中工作栈的 20分钟 状态变化，给出算法的C语言实现 给出广度优先遍历的思想，通过实例分析广度优先遍历过程中工作栈的 状态变化，给出算法的C语言实现 敕学提示： ,图的遍历是本章的重点和难点，本讲是从逻辑上（不涉及存储结构）讨 论如何进行遍历，注意深入剖析遍历的过程 重点： 图的两种遍历的思想及算法： 重点 难点 与 最小生成树算法 难点 教学策略： 对策 在授课过程中采用多媒体教学，首先还原问题的本来面目一 提出问题，引导学生 积极参与 一尝试解决问题，在讨论的基础上给出结论一一讲授教学内容、解决 问题，最后采用课件进行算法的动态演示，加大课堂信息量，提高教学效率

编号：009 课程 名称 数据结构 章节 名称 第六章 图 6.3 图的遍历 课程讲 授学时 45 分钟 课堂 教学 目的 知 识 点 学 习 要 求 识记 理解 熟练 掌握 应用 分析 综合 图的遍历 √ √ √ √ √ 态度 积极主动学习 能力 ➢ 利用深度优先搜索、广度优先搜索解决简单的应用问题 教学内容（教学过程设计） 教学安排 复习并导入新课 复习二叉树的遍历，理解访问的含义以及遍历的次序，导入新课-图的 遍历。 ↓ 6.3 图的遍历 提出问题：图的遍历要解决哪些关键问题 ↓ 给出深度优先遍历的思想，通过实例分析深度优先遍历过程中工作栈的 状态变化，给出算法的 C 语言实现 ↓ 给出广度优先遍历的思想，通过实例分析广度优先遍历过程中工作栈的 状态变化，给出算法的 C 语言实现 ↓ 教学提示： ➢ 图的遍历是本章的重点和难点，本讲是从逻辑上（不涉及存储结构）讨 论如何进行遍历，注意深入剖析遍历的过程 ➢ 5 分钟 20 分钟 20 分钟 重点 与 难点 对策 重点： 图的两种遍历的思想及算法； 难点： 最小生成树算法； 教学策略： 在授课过程中采用多媒体教学，首先还原问题的本来面目——提出问题，引导学生 积极参与——尝试解决问题，在讨论的基础上给出结论——讲授教学内容、解决 问题，最后采用课件进行算法的动态演示，加大课堂信息量，提高教学效率

教学 教学方法：导入，配合图形、实刚讲解，提问、讨论 方法 教学手段：PpT课件，板书，动画演示 与 段 作业： (1)已知如图627所示的有向图，请给出： ①每个顶点的入度和出度； ②邻接矩阵； 目邻接表： ④逆接表。 （2)已知如图6.28所示的无向网，请给出： ①邻接矩连： 作业 ②邻接表； 及 课外 ③最小生成树 （3)已知图的邻接矩阵如6.29所示。试分别画出自顶点1出发进行遍历所得的深 度优先生成树和广度优先生成树。 课后导读： 图的基本术语在本科生的教材中大同小异，更深入的介绍请参见《图论简明教 程》(Frd Buckley著李慧霸泽清华大学出版社) 深度优先遍历图的性质和广度优先遍历图的性质请参见《数据结构与算法》 (齐德层清华大学出版社) 拓扑排序算法的其它讨论参见《数据结构与算法》（许卓群清华大学出版社） “某路径为关键路径的充分必要条件是其上的活动均为关键活动”的证明请参 见《数据结构与算法》（齐德昱清华大学出版社） 教学 后记

教学 方法 与 手段 教学方法：导入，配合图形、实例讲解，提问、讨论 教学手段：PPT 课件，板书，动画演示 作业 及 课外 推荐 资源 作业： （1）已知如图 6.27 所示的有向图，请给出： ① 每个顶点的入度和出度； ② 邻接矩阵； ③ 邻接表； ④ 逆邻接表。 （2）已知如图 6.28 所示的无向网，请给出： ① 邻接矩阵； ② 邻接表； ③ 最小生成树 （3）已知图的邻接矩阵如 6.29 所示。试分别画出自顶点 1 出发进行遍历所得的深 度优先生成树和广度优先生成树。 课后导读： ➢ 图的基本术语在本科生的教材中大同小异，更深入的介绍请参见《图论简明教 程》（Frd Buckley 著 李慧霸译 清华大学出版社） ➢ 深度优先遍历图的性质和广度优先遍历图的性质请参见《数据结构与算法》 （齐德昱 清华大学出版社） ➢ 拓扑排序算法的其它讨论参见《数据结构与算法》（许卓群 清华大学出版社） ➢ “某路径为关键路径的充分必要条件是其上的活动均为关键活动”的证明请参 见《数据结构与算法》（齐德昱 清华大学出版社） 教 学 后记