数据结构授课教案-第7章

《数据结构授课教案-第7章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、山东轻工业学院教师授课教案课程名称：数据结构（计科）课程代码：0301306学分：4.5课程类别：必修开课单位:信息科学与技术学院授课班级：授课教师：杨春花山东轻工业学院教务处制授课时间年月日星期第节年月日星期第节年月日星期第节授课内容概要第七章图第一节图的定义和术语图的定义；有向图和无向图、完全图、顶点的度、路径、连通分量、生成树等基本术语。第二节图的存储结构邻接矩阵、邻接表、十字链表和邻接多重表。第三节图的遍历深度优先搜索的定义及实现和广度优先搜索的定义及实现。第四节图的连通性问题无向图的连通分量和生成树，最小生成树的定义以及构造最小生成树的算法（P

2、rim算法和Kruskal算法）。第五节有向无环图及其应用有向无环图的定义；拓扑排序、AOV-网的定义和拓扑排序的算法；AOE-网的定义、关键路径的定义和求法。第六节最短路径单源最短路径问题：Dijkstra算法；各顶点之间的最短路径问题：Floyd算法。目的要求目的：理解图的定义和实现。基本要求：理解拓扑排序的概念和算法，理解关键路径问题、最短路径问题；掌握图的基本概念、邻接矩阵和邻接表存储结构、深度和广度优先遍历、最小生成树的概念、普里姆算法和克鲁斯卡尔算法求最小生成树的方法。重点图的邻接矩阵和邻接表存储结构；深度和广度优先遍历方法；最小生成树。难点

3、图的深度和广度优先遍历方法；关键路径；最短路径。作业布置习题7参考书1.数据结构题集(C语言版),严蔚敏，清华大学出版社，2002。3.数据结构、算法与应用－C++语言描述，(美)SartajSahni著，汪诗林等译，机械工业出版社，2002。课型理论课学时分复习分钟配主要教具投影、黑板讲授分钟教学方法讲解、提问、示例指导分钟教学手段板书、课件总结分钟备注共8学时注：课型一栏填写理论课、实验课、习题课等授课内容备注第7章图7.1图的定义和术语7.1.1图的定义图（Graph）是一种网状数据结构，其形式化定义如下：Graph=（V，VR）其中V是顶点（Ve

4、rtex）的非空有限集合，VR是顶点间关系的集合。弧：若∈VR，则表示从顶点x到顶点y的一条弧（arc），并称x为弧尾（tail）或起始点(Initialnode)，称y为弧头（head）或终端点(Terminalnode)。此时的图称为有向图(Digraph)。无向图：若∈VR，必有∈VR，即VR是对称关系，这时以无序对（x，y）来代替两个有序对，表示x和y之间的一条边（edge），此时的图称为无向图(Undigraph)。7.1.2图的应用举例例1交通图（公路、铁路）顶点：地点边：连接地点的公路交通图中的有单行

5、道双行道，分别用有向边、无向边表示；例2电路图顶点：元件边：连接元件之间的线路例3通讯线路图顶点：地点边：地点间的连线例4各种流程图如产品的生产流程图顶点：工序边：各道工序之间的顺序关系7.1.3图的基本术语设用n表示图中顶点的个数，用e表示图中边或弧的数目，并且不考虑图中每个顶点到其自身的边或弧。无向完全图：有n（n-1）/2条边（图中每个顶点和其余n-1个顶点都有边相连）的无向图为完全图(Completedgraph)。有向完全图：有n（n-1）条边（图中每个顶点和其余n-1个顶点都有弧相连）的有向图为（1）有向完全图。稀疏图(Sparsegraph

6、)：对于有很少条边的图（e

7、为邻接点(Adjacent)，即v，v¢相邻接。边（v，v¢）依附(Incident)于顶点v和v¢，或者说边（v，v¢）与顶点v和v¢相关联。对于有向图G=（V，{A}）而言，若弧∈A，则称顶点v邻接到顶点v¢，顶点v¢邻接自顶点v，或者说弧与顶点v，v¢相关联。度、入度和出度：对于无向图而言，顶点v的度(Degree)是指和v相关联的边的数目，记作TD（v）。对于有向图而言，顶点v的度有出度和入度两部分：以顶点v为弧头的弧的数目称为该顶点的入度(InDegree)，记作ID（v），以顶点v为弧尾的弧的数目称为该顶点的出度(Ou

8、tDegree)，记作OD（v）则顶点v的度为：TD（v）=ID（v）+OD（v