教学大纲教案进度计划算法与数据结构c图查找详细教案.doc

《教学大纲教案进度计划算法与数据结构c图查找详细教案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、授课题目：图（一）课时安排2学时授课计划第18次教学目的、要求（分掌握、熟悉、了解三个层次）：l了解：图的定义及表示l熟悉：AOV网络和AOE网络。l掌握：图的存储结构及遍历算法；求最小生成树的算法；求最短路径算法；教学内容（包括基本内容、重点*、难点#）：重点：邻接表；深度优先搜索；广度优先搜索；最小生成树的算法；求最短路径算法难点：深度优先搜索；广度优先搜索；最小生成树的算法；求最短路径算法知识点：1．图的定义和术语（了解）l图定义、有向图与无向图、完全图、邻接顶点、子图、权；l顶点度、入读、出度、弧尾、弧头；l路径、路径长度、回路（）环）、简单路径、简单回路；l连通图与连通分量（

2、无无向图）、强连通图与强连通分量（有向图）、生成树2．图的存储结构l数组（邻接矩阵）表示（掌握）（1）无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。（2）入读、出度计算；（3）网（带权图）l邻接表（掌握）（1）邻接表:是图的一种链式存储结构；（2）弧的结点结构、顶点的结点结构；（3）无向图的邻接表、有向图的邻接表和逆邻接表、网络(带权图)的邻接表；3．图的遍历（所有顶点，每个顶点仅被访问一次）l深度优先搜索（熟练掌握）详细步骤、举例详细讲解过程l广度优先搜索（熟练掌握）详细步骤、举例详细讲解过程l以上二者的比较时间复杂度、战与队列、不同类型生成树备注：思考题：作业：Ｐ４７－

3、４８：7.7（要写出过程），7.9(只需写出拓扑有序序列)，7.11参考资料（含参考书、文献等）：授课类型（请打√）：理论课□讨论课□实验课√练习课□其他□教学过程设计（请打√）：复习□授新课√安排讨论□布置作业□教学方式（请打√）：讲授□讨论√示教□指导√其他□教学资源（请打√）：多媒体√模型□实物□挂图音像□其他□填表说明：1、每项页面大小可自行添减；2、教学内容与讨论、思考题、作业部分可合二为一；３、教学内容以后的栏目可根据课程特点自行修改。授课题目：图（二）课时安排2学时授课计划第19次教学目的、要求（分掌握、熟悉、了解三个层次）：l了解：图的定义及表示l熟悉：AOV网络和AO

4、E网络。l掌握：图的存储结构及遍历算法；求最小生成树的算法；求最短路径算法；教学内容（包括基本内容、重点*、难点#）：重点：邻接表；深度优先搜索；广度优先搜索；最小生成树的算法；求最短路径算法难点：深度优先搜索；广度优先搜索；最小生成树的算法；求最短路径算法知识点：4．最小生成树l使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。l按照生成树的定义，n个顶点的连通网络的生成树有n个顶点、n-1条边。l构造最小生成树的准则n必须使用且仅使用该网络中的n-1条边来联结网络中的n个顶点；n不能使用产生回路的边；n各边上的权值的总和达到最小。lPrim算法

5、和Kruskal算法（掌握）（1）Prim算法：基本思想、详细步骤、举例详细讲解过程；（2）Kruskal算法:基本思想、详细步骤、举例详细讲解过程；(3)二者的比较：时间复杂度分析、适用图的类型；备注：思考题：作业：Ｐ４７－４８：7.7，7.9(只需写出拓扑有序序列)，7.11参考资料（含参考书、文献等）：授课类型（请打√）：理论课√讨论课□实验课□练习课□其他□教学过程设计（请打√）：复习□授新课√安排讨论□布置作业□教学方式（请打√）：讲授√讨论□示教□指导□其他□教学资源（请打√）：多媒体√模型□实物□挂图音像□其他□填表说明：1、每项页面大小可自行添减；2、教学内容与讨论、思

6、考题、作业部分可合二为一；３、教学内容以后的栏目可根据课程特点自行修改。授课题目：图（三）课时安排2学时授课计划第20次教学目的、要求（分掌握、熟悉、了解三个层次）：l了解：图的定义及表示l熟悉：AOV网络和AOE网络。l掌握：图的存储结构及遍历算法；求最小生成树的算法；求最短路径算法；教学内容（包括基本内容、重点*、难点#）：重点：邻接表；深度优先搜索；广度优先搜索；最小生成树的算法；求最短路径算法难点：深度优先搜索；广度优先搜索；最小生成树的算法；求最短路径算法知识点：5．最短路径最短路径问题：如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路

7、径使得沿此路径上各边上的权值总和达到最小。u边上权值非负情形的单源最短路径问题—Dijkstra算法基本思想、详细步骤、举例详细讲解过程；u所有顶点之间的最短路径—Floyd算法基本思想、详细步骤、举例详细讲解过程；l非负权值的单源最短路径（掌握）l所有顶点之间的最短路径（掌握）6．AOV网络和AOE网络（熟悉）（1）用顶点表示活动的网络(AOV网络)：用途、拓扑排序、拓扑排序方法思想、举例说明过程；（2）AOE-网（ActivityOnEdg