《数据结构与算法(C语言版)》教学参考模块6.docx

模块6图教学要求:(1)了解图的定义，熟悉图的相关术语，掌握图的基本操作。(2)掌握图的存储表示。(3)掌握图的深度优先遍历和广度优先遍历。(4)掌握图的连通性。(5)熟悉最短路径确定方法。教学重点：图的基本术语；有关图的定理；图的存储结构；图常用的两种遍历方法；最小生成树；最短路径问题求解。教学难点：图常用的两种遍历方法；最小生成树的构造；最短路径问题的求解。课时安排：本章安排10课时。其中，理论讲授7课时，上机实验3课时。教学大纲：模块6图案例导入案例分析相关知识6.1图的定义、术语及基本操作6.1.1图的定义6.1.2图的相关术语6.1.3图的基本操作6.2图的存储表示.2.1邻接矩阵.2.2邻接表6.3图的遍历6.3.1深度优先遍历6.3.2广度优先遍历6.4图的连通性6.4.1无向图的连通分量和生成树6.4.2最小生成树5最短路径案例实施案例总结思考与练习主要概念：.图.有向图.无向图.混合图.无向完全图.有向完全图.稀疏图.稠密图.主子图.n阶完全图.补图.入度.出度.度.路径长度.自回路.回路（环）.简单路径.简单回路（简单环）.连通图.强连通图.强连通分量.权.赋权图.欧拉回路.欧拉图.欧拉通路.半欧拉图.图的邻接矩阵法.图的邻接表法.图的遍历.深度优先搜索.广度优先搜索.最小生成树（MST）.最短路径问题.拓扑排序.偏序关系.全序关系实验：实验一八皇后问题（1学时）本书附录中上机实验3；实验二旅行商问题（2学时）本书附录中上机实验5。