数据结构第6章课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《数据结构第6章课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课件
- 资源描述:
-
1、第第6 6章章 图图本章概述本章概述 图是一种重要的非线性结构,并且是一种比线性图是一种重要的非线性结构,并且是一种比线性表和树更为复杂的数据结构。图的特点是每个顶点都表和树更为复杂的数据结构。图的特点是每个顶点都可以与其他顶点相连;在图结构中,每个顶点的地位可以与其他顶点相连;在图结构中,每个顶点的地位是一样的,图中任意两个顶点之间都可以相关。是一样的,图中任意两个顶点之间都可以相关。图的应用极为广泛,特别是图论的迅速发展,使图的应用极为广泛,特别是图论的迅速发展,使得图的应用已渗入到运筹学、逻辑学、计算机科学及得图的应用已渗入到运筹学、逻辑学、计算机科学及语言学等其他分支学科中。语言学等其
2、他分支学科中。6.1 6.1 图的定义和术语图的定义和术语 图是由一个顶点集图是由一个顶点集V V和一个弧集和一个弧集R R构成的数据结构。构成的数据结构。图的抽象数据类型数学表述为:图的抽象数据类型数学表述为:Graph=Graph=(V V,R R),),且且VRVR t|th|t,hVhV且且P(tP(t,h)h)其中,其中,VRVR表示两个顶点之间的关系,表示两个顶点之间的关系,th表示从表示从t t到到h h的一条弧,的一条弧,P(tP(t,h)h)定义了弧定义了弧 th的意义。的意义。图中的数据元素通常称为顶点(图中的数据元素通常称为顶点(vertexvertex)。)。V V是顶
3、点的有穷非空集合。是顶点的有穷非空集合。VRVR表示两个顶点之间的关系的集合。表示两个顶点之间的关系的集合。若若tVRhVR,则,则th表示从表示从t t到到h h的一条弧,且称的一条弧,且称t t为为弧尾弧尾(tailtail),),h h为为弧头弧头(head)(head),此时的图称为,此时的图称为有向有向图图。若若tVRhVR必有必有hVR,tVR,即即VRVR是对称的,则是对称的,则用无序对(用无序对(t t,h h)代替这两个有序对,表示)代替这两个有序对,表示t t和和h h这两个这两个顶点之间的一条边,此时的图称为顶点之间的一条边,此时的图称为无向图无向图。下图下图(a)(a)
4、所示为无向图,所示为无向图,(b)(b)所示为有向图。所示为有向图。【例【例6-16-1】使用集合的表示方法,上面的两个图可以用如】使用集合的表示方法,上面的两个图可以用如下的方法表示:下的方法表示:Ga=(Va,EaGa=(Va,Ea);Gb=(Vb,EbGb=(Vb,Eb)VaVa=1,2,3,4=1,2,3,4;Ea=(1,2),(1,3),(1,4),(2,3)Ea=(1,2),(1,3),(1,4),(2,3)VbVb=1,2,3,4,5=1,2,3,4,5;EbEb=,=,注意:注意:无向图的顶点无序偶对使用一对圆括号表示,无向图的顶点无序偶对使用一对圆括号表示,有向图的顶点有序偶
5、对使用一对尖括号表示。有向图的顶点有序偶对使用一对尖括号表示。每条边都是有向边的图,称为每条边都是有向边的图,称为有向图有向图;每条边都;每条边都是无向边的图,称为是无向边的图,称为无向图无向图。既有有向边又有无向边。既有有向边又有无向边的图,称为的图,称为混合图混合图。用用n n表示图中顶点的数目,用表示图中顶点的数目,用e e表示图中边的数目。表示图中边的数目。不考虑顶点到自身的边,对于无向图,不考虑顶点到自身的边,对于无向图,e e的取值范的取值范围是围是0n(n-1)/20n(n-1)/2,具有,具有n(n-1)/2n(n-1)/2条边的无向图称为条边的无向图称为无无向完全图向完全图。
6、对于有向图,对于有向图,e e的取值范围是的取值范围是0n(n-1)0n(n-1),具有,具有n(n-1)n(n-1)条边的有向图称为条边的有向图称为有向完全图有向完全图。在工程应用中,边数。在工程应用中,边数e e小于小于nlognlog n n的图称为的图称为稀疏图稀疏图,反之称为,反之称为稠密图稠密图。假设有两个图假设有两个图G=(VG=(V,E)E)和和G=(V,E)G=(V,E),如果,如果 V VV V且且E EE E,则称,则称GG为为G G的子图。的子图。下图所示是子图的一些例子。下图所示是子图的一些例子。子图是在原图上删去若干条边或若干个点剩下的图。子图是在原图上删去若干条边
7、或若干个点剩下的图。删边指删去图中的某一条边但仍保留边的顶点。删边指删去图中的某一条边但仍保留边的顶点。删点指删去图中某一点以及与这点相连的所有边。删点指删去图中某一点以及与这点相连的所有边。图中删去一点所得的子图称为图中删去一点所得的子图称为主子图主子图。设有一个设有一个n n阶无向图,在其中添加一些边后,可使其成阶无向图,在其中添加一些边后,可使其成为为n n阶完全图阶完全图。由这些新添加的边和其顶点构成的图称为原图的由这些新添加的边和其顶点构成的图称为原图的补补图图。对于无向图对于无向图G=(VG=(V,E)E),顶点,顶点v v的度是和的度是和v v相连的边的相连的边的数目,记为数目,
8、记为D(vD(v)。对于有向图对于有向图G=(VG=(V,R)R),以顶点,以顶点t t为弧头的弧的数目称为弧头的弧的数目称为顶点为顶点t t的的入度入度,记为,记为ID(tID(t);以顶点;以顶点t t为弧尾的弧的数为弧尾的弧的数目称为顶点目称为顶点t t的的出度出度,记为,记为OD(tOD(t);顶点;顶点t t的度记为的度记为D(t)=ID(t)+OD(tD(t)=ID(t)+OD(t)。特殊情况下,度数为零的顶点称为特殊情况下,度数为零的顶点称为孤立点孤立点,度数为,度数为1 1的顶点称为的顶点称为悬挂点悬挂点。一般地,如果顶点一般地,如果顶点vivi的度记为的度记为D D(vivi
9、),那么一个有),那么一个有n n个顶点,个顶点,e e条边的图,满足如下关系:条边的图,满足如下关系:定理定理1 1:设图:设图G G是具有是具有v v个顶点,个顶点,e e条边的无向图,则有条边的无向图,则有D(vD(v)=2e)=2e。定理定理2 2:设图:设图G G是具有是具有v v个顶点,个顶点,e e条边的有向图,则有条边的有向图,则有ID(v)=OD(vID(v)=OD(v)=e)=e。11()2niieDv 路径长度路径长度是路径上边的数目或弧的数目。是路径上边的数目或弧的数目。一条边的两端重合,称为一条边的两端重合,称为自回路自回路。第一个顶点和最后一个顶点相同的路径称为回第
10、一个顶点和最后一个顶点相同的路径称为回路路或或环环。在顶点序列中,顶点不重复出现的路径称为在顶点序列中,顶点不重复出现的路径称为简单路径简单路径。除了第一个顶点和最后一个顶点之外,其余顶点不重复除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为出现的回路,称为简单回路简单回路或或简单环简单环。在无向图在无向图G=(VG=(V,E)E)中,如果存在一条从顶点中,如果存在一条从顶点v v到到顶点顶点w w的路径,则称的路径,则称从从v v到到w w可达可达。如果图中任意两点是可达的,则称如果图中任意两点是可达的,则称v v和和w w是是连通连通的,的,否则不连通。否则不连通。对于图中
11、任意两个顶点对于图中任意两个顶点v v、wVwV,v v和和w w都是连通都是连通的,则称的,则称G G是是连通图连通图。有向图有向图G=VG=R中,如果对于每一对中,如果对于每一对t t、hVhV,从从t t到到h h和从和从h h到到t t都存在路径,则称都存在路径,则称G G是是强连通图强连通图。有向图中的极大强连通子图称为有向图的有向图中的极大强连通子图称为有向图的强连通分量强连通分量。例如,下图不是强连通图,但它有两个强连通分量。例如,下图不是强连通图,但它有两个强连通分量。在图的顶点或边上表明某种信息的数称为权,含有在图的顶点或边上表明某种信息的数称为权,含有权的图,称为权的图,称
12、为赋权图赋权图。例如,下图就是一个赋权图。例如,下图就是一个赋权图。最短路径问题的算法:最短路径问题的算法:先求出到某一顶点的最短路径,然后利用这个结先求出到某一顶点的最短路径,然后利用这个结果再去确定到另一顶点的最短路径,如此继续下去,果再去确定到另一顶点的最短路径,如此继续下去,直到找到最短路径为止。直到找到最短路径为止。如果图中存在一条通过图中各边一次且仅一次的如果图中存在一条通过图中各边一次且仅一次的回路,则称此回路为回路,则称此回路为欧拉回路欧拉回路,具有欧拉回路的图称,具有欧拉回路的图称为为欧拉图欧拉图。如果图中存在一条通过图中各边一次且仅一次的如果图中存在一条通过图中各边一次且仅
13、一次的通路,则称此通路为通路,则称此通路为欧拉通路欧拉通路,具有欧拉通路的图称,具有欧拉通路的图称为为半欧拉图半欧拉图。定理定理3 3:一个无向连通图是欧拉图的充要条件是图:一个无向连通图是欧拉图的充要条件是图中各点的度数为偶数。中各点的度数为偶数。定理定理4 4:一个无向连通图是半欧拉图的充要条件是:一个无向连通图是半欧拉图的充要条件是图中至多有两个奇数度点。图中至多有两个奇数度点。定理定理5 5:设图:设图G G是有向连通图,图是有向连通图,图G G是欧拉图的充是欧拉图的充要条件是图中每个顶点的入度和出度相等。要条件是图中每个顶点的入度和出度相等。定理定理6 6:设图:设图G G是有向连通
14、图,图是有向连通图,图G G是半欧拉图的是半欧拉图的充要条件是至多有两个顶点的出度和入度不相等,其充要条件是至多有两个顶点的出度和入度不相等,其中一个顶点的入度比它的出度大中一个顶点的入度比它的出度大1 1,另一个顶点的入度,另一个顶点的入度比它的出度小比它的出度小1 1,而其他顶点的入度和出度相等。,而其他顶点的入度和出度相等。一个连通图的生成树是一个极小的连通子图,它一个连通图的生成树是一个极小的连通子图,它含有图中全部顶点,但只有构成一棵树的含有图中全部顶点,但只有构成一棵树的n-1n-1条边。条边。一棵有一棵有n n个顶点的生成树有且仅有个顶点的生成树有且仅有n-1n-1条边。条边。如
15、果一个图有如果一个图有n n个顶点和小于个顶点和小于n-1n-1条边,则图一定条边,则图一定是非连通图,如果它多于是非连通图,如果它多于n-1n-1条边,则一定有环。条边,则一定有环。6.26.2 图的存储结构图的存储结构 设设G=G=(V V,E E)是具有)是具有n n个顶点的图,则个顶点的图,则G G的邻接矩阵的邻接矩阵定义为:定义为:【例【例6-26-2】将下图】将下图(a)(a)所示的无向图和图所示的无向图和图(b)(b)所示的有所示的有向图用邻接矩阵表示。向图用邻接矩阵表示。1(,),0(,),v wv wEAv wv wv wE若或若或6.2.1 6.2.1 邻接矩阵邻接矩阵 解
16、:以上无向图和有向图分别用邻接矩阵解:以上无向图和有向图分别用邻接矩阵M1M1和和M2M2表示如下:表示如下:设设G=G=(V V,E E)是具有)是具有n n个顶点的赋权图,则个顶点的赋权图,则G G的邻接矩的邻接矩阵定义为:阵定义为:10 1 1 11 0 1 11 1 0 01 1 0 0M20 1 0 0 01 0 0 0 10 1 0 1 01 0 0 0 00 0 0 1 0M,(,),0(,),v wv wv wv wEpA v wv wv wE若或 其中:表示边上的权值。p或若或【例【例6-36-3】将下图所示的赋权图用邻接矩阵表示。】将下图所示的赋权图用邻接矩阵表示。解:赋权
17、图可以用邻接矩阵解:赋权图可以用邻接矩阵M M3 3或或M M4 4表示如下:表示如下:30 5 0 7 0 00 0 4 0 0 08 0 0 0 0 90 0 5 0 0 60 0 0 5 0 03 0 0 0 1 0M45748956531M 图的邻接矩阵存储结构的描述形式如下:图的邻接矩阵存储结构的描述形式如下:#define MAX_VERTEX_NUMBER 100#define MAX_VERTEX_NUMBER 100 最大顶点数最大顶点数typedef char VertexTypetypedef char VertexType;顶点类型顶点类型typedef inttype
18、def int edge;edge;边上的权值类型边上的权值类型typedef struct MGraphtypedef struct MGraph存储图的结构体存储图的结构体 VertexType vArrayMAX_VERTEX_NUMBERVertexType vArrayMAX_VERTEX_NUMBER;顶点数组顶点数组edge eArrayMAX_VERTEX_NUMBERMAX_VERTEX_NUMBERedge eArrayMAX_VERTEX_NUMBERMAX_VERTEX_NUMBER;邻接矩阵邻接矩阵intint n;n;顶点数顶点数intint e;e;边数边数;算法
19、算法6.16.1是在邻接矩阵存储结构是在邻接矩阵存储结构MGraphMGraph上对图构造上对图构造的实现算法。的实现算法。注意注意:在简单应用中,可直接用二维数组作为邻:在简单应用中,可直接用二维数组作为邻接矩阵,顶点数和边数均可省略。接矩阵,顶点数和边数均可省略。对于无向图,顶点对于无向图,顶点vivi的度是邻接矩阵中第的度是邻接矩阵中第i i行(或行(或第第i i列)的元素之和。列)的元素之和。对于有向图,顶点对于有向图,顶点vivi的度是邻接矩阵中第的度是邻接矩阵中第i i行和第行和第i i列的元素之和,且第列的元素之和,且第i i行的元素之和为顶点行的元素之和为顶点vivi的出度,的
20、出度,第第i i列的元素之和为顶点列的元素之和为顶点vivi的入度。的入度。对于图中的每个顶点对于图中的每个顶点vivi,把所有邻接于,把所有邻接于vivi的顶点的顶点vjvj链成一个带头结点的单链表,这个单链表称为顶点链成一个带头结点的单链表,这个单链表称为顶点vivi的邻的邻接表。接表。邻接表的结构由两部分组成:邻接表的结构由两部分组成:头结点:用于存储顶点信息和指向表结点的指针;头结点:用于存储顶点信息和指向表结点的指针;表结点:用于存储头结点中顶点相邻接的顶点信息和表结点:用于存储头结点中顶点相邻接的顶点信息和指向表结点的指针。指向表结点的指针。6.2.2 6.2.2 邻接表邻接表【例
21、【例6-46-4】给出下图中无向图】给出下图中无向图G G的邻接表表示。的邻接表表示。解:无向图解:无向图G G的邻接表表示如下图所示。的邻接表表示如下图所示。注意注意:在编程时,头结点以数组的形式存储,表:在编程时,头结点以数组的形式存储,表结点以单链表的形式存储。显然,在稀疏图中,用邻结点以单链表的形式存储。显然,在稀疏图中,用邻接表存储比用邻接矩阵存储节省存储空间。接表存储比用邻接矩阵存储节省存储空间。【例【例6-56-5】给出下图中有向图】给出下图中有向图G G的邻接表表示。的邻接表表示。解:有向图解:有向图G G的邻接表表示如下图所示。的邻接表表示如下图所示。为了方便确定顶点的入度,
22、可以建立有向图的逆为了方便确定顶点的入度,可以建立有向图的逆邻接表,下图就是例【邻接表,下图就是例【6-56-5】中有向图的逆邻接表。】中有向图的逆邻接表。在邻接表上容易找到任一顶点的第一个邻接点和在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点,但要判定任意两个顶点之间是否有边下一个邻接点,但要判定任意两个顶点之间是否有边相连,则要搜索单链表,不如邻接矩阵方便。相连,则要搜索单链表,不如邻接矩阵方便。图的邻接表存储结构的表示形式如下:图的邻接表存储结构的表示形式如下:#define MAX_VERTEX_NUMBER 100#define MAX_VERTEX_NUMBER 100 最
23、大顶点数最大顶点数typedef char VertexTypetypedef char VertexType;顶点类型顶点类型typedef struct eNodetypedef struct eNode 表结点表结点int adjVerint adjVer;eNode eNode*pNextpNext;typedef struct vNodetypedef struct vNode 头结点头结点VertexTypeVertexType vertex;vertex;eNode eNode*pFirstpFirst;typedef struct ALGraphtypedef struct A
24、LGraph 邻接表结构体邻接表结构体vNode adjListMAX_VERTEX_NUMBERvNode adjListMAX_VERTEX_NUMBER;头结点数组头结点数组intint n;n;顶点数顶点数intint e;e;边数边数;算法算法6.26.2是在邻接表存储结构是在邻接表存储结构ALGraphALGraph上对图的构上对图的构造的实现算法。造的实现算法。注意注意:通常头结点以顺序结构存储,表结点以链:通常头结点以顺序结构存储,表结点以链式结构存储。式结构存储。6.3 6.3 图的遍历图的遍历 设图设图G G中的所有顶点均未被访问过,在图中的所有顶点均未被访问过,在图G G
25、中任选一个中任选一个顶点顶点v v为初始出发点,则深度优先搜索描述如下:为初始出发点,则深度优先搜索描述如下:首先访问初始出发点首先访问初始出发点v v,并将其标记为已访问过,然后,并将其标记为已访问过,然后依次从依次从v v出发遍历出发遍历v v的每个邻接点的每个邻接点w w。若邻接点。若邻接点w w未曾访问过,未曾访问过,则以则以w w为新的出发点继续进行深度优先搜索,直至图中所有为新的出发点继续进行深度优先搜索,直至图中所有和出发点和出发点v v有路径相通的顶点均已被访问过为止。若此时图有路径相通的顶点均已被访问过为止。若此时图中仍有未访问的顶点,则另选一个未访问的顶点作为新的出中仍有未
展开阅读全文