第八章图 教学内容:8.1图的基本概念 8.2图的存储表示 8.3图的遍历 8.4图的连通性 8.5最小生成树 8.6最短路径 8.7有向无环图及其应用 2教学目的:(理解图的基本概念及术语 2)掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法 (3)熟练掌握图的两种遍历的算法思想、步骤 (4)理解最小生成树的概念,能按Prim算法构造最小生成树 ⑤5领会并掌握拓扑排序、关键路径、最短路径的算法思想。 3教学重点:(1理解图的定义、术语及其含义: (2)掌握各种图的邻接矩阵表示法及其类型说明 ③3理解并掌握图的按深度优先搜索遍历方法和按广度优先搜索遍历方法 4领会生成树和最小生成树的概念 (5)掌握由Pim算法思想构造最小生成树按Pim算法思想 (6)领会拓扑序列和拓扑排序的概念 (7)理解并掌握拓扑排序的算法思想 ⑧)理解并掌握关键路径的算法思想: (9)理解并掌握最短路径的算法思想 4.教学难点:(正确理解与区别图的常用术语 (2)区别图的两种存储结构的不同点及其应用场合 (3)关键路径的算法思想 (4)最短路径的算法思想 5学时安排:12学时 2021年1月21日 数据结构讲义2021年1月21日 数据结构讲义 1 第八章 图 ⒈教学内容：8.1 图的基本概念 8.2 图的存储表示 8.3 图的遍历 8.4 图的连通性 8.5 最小生成树 8.6 最短路径 8.7 有向无环图及其应用 ⒉教学目的：⑴理解图的基本概念及术语； ⑵掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法； ⑶熟练掌握图的两种遍历的算法思想、步骤； ⑷理解最小生成树的概念，能按Prim算法构造最小生成树； ⑸领会并掌握拓扑排序、关键路径、最短路径的算法思想。 ⒊教学重点：⑴理解图的定义、术语及其含义； ⑵掌握各种图的邻接矩阵表示法及其类型说明； ⑶理解并掌握图的按深度优先搜索遍历方法和按广度优先搜索遍历方法； ⑷领会生成树和最小生成树的概念； ⑸掌握由Prim算法思想构造最小生成树按Prim算法思想； ⑹领会拓扑序列和拓扑排序的概念； ⑺理解并掌握拓扑排序的算法思想； ⑻理解并掌握关键路径的算法思想； ⑼理解并掌握最短路径的算法思想。 ⒋教学难点：⑴正确理解与区别图的常用术语； ⑵区别图的两种存储结构的不同点及其应用场合； ⑶关键路径的算法思想； ⑷最短路径的算法思想。 ⒌学时安排： 12学时