资源描述：
《数据结构详细教案——图》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第0页数据结构教案第七章图第12页数据结构教案第7章图第7章图【学习目标】 1．领会图的类型定义。 2．熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。 3．熟练掌握图的两种遍历算法。 4．理解各种图的应用问题的算法。【重点和难点】 图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。【知识点】 图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径【学习指南】 离散数学中的图论是专门研究图性质的
2、一个数学分支，但图论注重研究图的纯数学性质，而数据结构中对图的讨论则侧重于在计算机中如何表示图以及如何实现图的操作和应用等。图是较线性表和树更为复杂的数据结构，因此和线性表、树不同，虽然在遍历图的同时可以对顶点或弧进行各种操作，但更多图的应用问题如求最小生成树和最短路径等在图论的研究中都早已有了特定算法，在本章中主要是介绍它们在计算机中的具体实现。这些算法乍一看都比较难，应多对照具体图例的存储结构进行学习。而图遍历的两种搜索路径和树遍历的两种搜索路径极为相似，应将两者的算法对照学习以便提高学习的效益。【课前思考】1.你有没有发现现在的十字路口的交
3、通灯已从过去的一对改为三对，即每个方向的直行、左拐和右拐能否通行都有相应的交通灯指明。你能否对某个丁字路口的6条通路画出和第一章绪论中介绍的"五叉路口交通管理示意图"相类似的图？2.如果每次让三条路同时通行，那么从图看出哪些路可以同时通行？同时可通行的路为：(AB,BC,CA),(AB,BC,BA),(AB,AC,CA),(CB,CA,BC)第12页数据结构教案第7章图目录第7章图17.1图的定义和基本术语17.2图的存储和创建27.2.1图的存储表示27.2.2图的创建47.3图的遍历57.3.1深度优先搜索57.3.2广度优先搜索67.4遍历
4、算法的应用77.4.1应用问题概述77.4.2求一条包含图中所有顶点的简单路径87.4.3求距v0的各顶点中最短路径长度最长的一个顶点97.5图的连通性问题107.5.1无向图的连通分量和生成树107.5.2最小生成树117.6有向无环图及其应用12第7章第12页数据结构教案第7章图第7章图7.1图的定义和基本术语1、图的特征任意两个数据元素之间都可能相关。结点之间的关系是多对多的。G=(V,{E})2、基本术语结点：顶点结点间的关系：无向图：边(v,w)，v与w互为邻接点，边(v,w)依附于顶点v,w，边(v,w)和顶点v,w相关联v的度：和v
5、相关联的边的数目。有向图：弧，v弧尾，w弧头，顶点v邻接到顶点w，顶点w邻接自顶点v，弧和顶点v,w相关联。v的入度：以v为弧头的弧的数目；v的出度：以v为弧尾的弧的数目；v的度：v的入度与出度之和。路径、回路(环)、简单路径、简单回路(简单环)连通性：若从顶点v到顶点v’有路径，则称v和v’是连通的图的规模：顶点数n、边(弧)数e、顶点的度(有向图：入度/出度)子图：G’=(V’,{E’}),G=(V,{E})，若V’ÍV且E’ÍE，则称G’是G的子图。图的分类：1）关系的方向性（无向/有向）、关系上是否有附加的数——权(图
6、/网)有向图、无向图、有向网、无向网2）边(弧)数：完全图(边数=n(n-1)/2的无向图)、有向完全图(弧数=n(n-1)的有向图)稀疏图(enlogn)3）连通性：无向图：连通图(任意两顶点都是连通的)、连通分量(极大连通子图)、生成树(极小连通子图)、生成森林有向图：强/弱连通图、强连通分量、生成树(极小连通子图)、生成森林3、抽象数据类型定义ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={
7、v,wÎV且P(v,w)，表示从v到w的弧
8、，谓词P(v,w)定义了弧的意义或信息}基本操作：CreateGraph(&G,V,VR)初始条件：V是图的顶点集，VR是图中弧的集合操作结果：按V和VR的定义构造图GDestroyGraph(&G)初始条件：图G存在操作结果：销毁图GLocateVex(G,u)初始条件：图G已存在，u和G中顶点有相同特征操作结果：若G中存在顶点u，则返回该顶点在图中位置，否则返回其它信息12第12页数据结构教案第7章图GetVex(G,v)初始条件：图G存在，v是G中某个顶点操作结果：返回v的值PutVex(&G,v,value)初始条件：图G存在，
9、v是G中某个顶点操作结果：对v赋值valueFirstAdjVex(G,v)初始条件：图G存在，v是G中某个顶点操作结果：返回v的第一个
