数据结构与算法“图”教学设计 北京大学信息科学技术学院王腾蛟 1.图在课程中的定位和前测知识点 图是比线性表、数和集合更一般、更复杂的数据结构,在线性结构中,每个数据元素只 有一个直接前驱和一个直接后继结点。在树结构中,数据元素之间有着明显的层次关系,同 层的每个数据元素可以与它下一层的零个或多个元素相关,但只能与上一层中的一个元素相 关。集合结构中,数据元素间除了同属于一个集合的联系之外没有其他关系。然而在图结构 中,数据元素之间的关系是任意的,每个元素都可以和任何其他元素相关。 图这一章阐述了图的基本概念以及图的存储结构:相邻矩阵表示法、邻接表表示法,并 讨论了图的深度优先周游和广度优先周游。此外提出了最小支撑树的概念,并讨论了生成最 小支撑树的Prim算法和 Kruskal算法。 前测知识点要求如下,可以根据需要给学生补充: 图的顶点与边的概念。 2.学习目标 (1)理解并掌握图的基本概念。 (2)能写出图的抽象数据类型。 (3)理解图的各种存储结构,并能设计基于图的存储结构的算法。 4)重点掌握图的周游、最短路径和最小支撑树的相关算法 (5)了解图的相关知识。 3.知识点和学时分配 理论授课4学时,建议安排实验8学时。 各知识点建议授课时间如下: 图的基本概念0.5小时 图的存储结构 1小时 图的周游 1小时 最短路径问题 0.5小时1 数据结构与算法“图”教学设计 北京大学信息科学技术学院 王腾蛟 1. 图在课程中的定位和前测知识点 图是比线性表、数和集合更一般、更复杂的数据结构，在线性结构中，每个数据元素只 有一个直接前驱和一个直接后继结点。在树结构中，数据元素之间有着明显的层次关系，同 层的每个数据元素可以与它下一层的零个或多个元素相关，但只能与上一层中的一个元素相 关。集合结构中，数据元素间除了同属于一个集合的联系之外没有其他关系。然而在图结构 中，数据元素之间的关系是任意的，每个元素都可以和任何其他元素相关。 图这一章阐述了图的基本概念以及图的存储结构：相邻矩阵表示法、邻接表表示法，并 讨论了图的深度优先周游和广度优先周游。此外提出了最小支撑树的概念，并讨论了生成最 小支撑树的 Prim 算法和 Kruskal 算法。 前测知识点要求如下，可以根据需要给学生补充： 图的顶点与边的概念。 2．学习目标 （1） 理解并掌握图的基本概念。 （2） 能写出图的抽象数据类型。 （3） 理解图的各种存储结构，并能设计基于图的存储结构的算法。 （4） 重点掌握图的周游、最短路径和最小支撑树的相关算法。 （5） 了解图的相关知识。 3. 知识点和学时分配 理论授课 4 学时，建议安排实验 8 学时。 各知识点建议授课时间如下： 图的基本概念 0.5 小时 图的存储结构 1 小时 图的周游 1 小时 最短路径问题 0.5 小时