《数据结构与算法(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图的存储表示
6 . 2. 1邻接矩阵
7 .2.2邻接表
6. 3图的遍历
6. 3.1深度优先遍历
6. 3.2广度优先遍历
6.4图的连通性
6. 4. 1无向图的连通分量和生成树
6. 4.2最小生成树
6. 5最短路径
案例实施
案例总结
思考与练习主要概念：
1 .图.有向图
2 .无向图.混合图
3 .无向完全图.有向完全图
4 .稀疏图.稠密图
5 .主子图. n阶完全图
6 .补图.入度
7 .出度.度
8 .路径长度.自回路
9 .回路（环）.简单路径
10 .简单回路（简单环）.连通图
11 .强连通图.强连通分量
12 .权.赋权图
13 .欧拉回路.欧拉图
14 .欧拉通路.半欧拉图
15 .图的邻接矩阵法.图的邻接表法
16 .图的遍历.深度优先搜索
17 .广度优先搜索.最小生成树（MST）
18 .最短路径问题.拓扑排序
19 .偏序关系.全序关系
实验：
实验一八皇后问题（1学时）本书附录中上机实验3；
实验二旅行商问题（2学时）本书附录中上机实验5。