数据结构第七章图ppt课件.ppt

《数据结构第七章图ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图的定义和术语图的存储结构图的遍历生成树最短路径拓扑排序习题图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间有线性关系，每一个数据元素只有一个直接前驱和一个直接后续；在树形结构中，数据元素之间有着明显的层次关系，即每一个数据元素有一个直接前驱(双亲)和零个或多个直接后续(孩子)；而在图形结构中，结点之间的关系是任意的，图中任意两个数据元素之间都可能相关。由此，图的应用极为广泛。例如，城市间的最短路径，火车的联票，交通网的计划，战场上的运输问题，庞大的施工进度图等都是图的应用。图的定义和术语定义：图(graph)：是一

2、种数据结构，由二个集合V和E组成，记作G=(V,E)。其中V是数据元素(顶点)的非空有限集，E是V中二元关系(边edge)的集合。树是图的特例，而线性表是树的特例。术语：有向图：图的每条边都是有序顶点对(即边是有方向)。弧：有向图的边。并将构成该边的有序顶点对用一对尖括号括起来。如∈E，表示从顶点u到顶点v的一条弧，称u为弧尾或初始点，v为弧头或终端点。并且说v是与u相邻的顶点，或v是u的邻接点例如，图7.1(a)所示的为有向图，它是由集合V={v0,v1,v2,v3}E={,,,

3、}组成的。图7.1(a)有向图G1无向图：图的每条边是无方向的，有∈E，必有∈E。即用圆括号括起来(u,v)∈E表示边，并且，u和v互称为邻接点例如，图7.1(b)为无向图，它是由集合V={v0,v1,v2,v3,v4}E={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3),(v2,v4)}组成的。网络：若图中每条边或弧都附加一个数值作为权,带权图。子图：若G1={V1,E1}，G2={V2,E2}是两个图，且V2被包含在V1中，E2被包含在E1中，则称图G2是图G1的

4、子图。度：无向图中，顶点的度是依附于该顶点的边数。有向图中，该顶点入边的数目叫入度，该顶点出边的数目叫出度，该顶点的度就是入度+出度。图中的顶点度数之和等于边数的2倍。路径：在有向图(或无向图)中，如果存在首尾相接并且无重复边的边序列,,…,(或(v0,v1),(v1,v2),…,(vn-2,vn-1))，那么称这个序列是一条从顶点到v0到vn-1的一条路径，记着(v0,v1,v2,…,vn-2,vn-1)。序列中的边数称为路径长度。在有向图中，路径是有方向的；而在无向图中，路径无方

5、向。简单路径：在一条路径中，若除起点和终点外，所有顶点彼此各不相同。回路：在一条路径中，若起点和终点是同一顶点。简单回路：有简单路径组成的回路称为简单回路。连通：在无向图G中，若从顶点vi到顶点vj有路径存在。连通图：在无向图G中，若任意二个顶点之间都是连通的.连通分量：在非连通的无向图G中，极大连通子图(在满足连通条件下，尽可能多的包含G中的顶点和这些顶点之间的边).如图7.2中，图G有三个连通分量。(a)有向图G(b)图G的三个连通分量强连通：在有向图G中，若从顶点vi到顶点vj有路径存在，并且从顶点vj到顶点vi也有路径存在。

6、强连通图：在有向图G中，若任意二个顶点之间都是强连通的。强连通分量：在非强连通的有向图G中，极大强连通子图称为有向图的强连通分量。如图7.3中，有向图G有两个强连通分量。生成树：在一个有n顶点的连通图G中，存在一个极小的连通子图G′，G′包含图G的所有顶点，但只有n-1条边，并且G′是连通的。(a)有向图G(b)图G的二个强连通分量图7.3有向图及其强连通分量图的存储结构常用的图的存储结构有邻接矩阵、邻接表、十字链表、多重链表等方法。本节介绍最为常用的邻接矩阵和邻接表方法。对图的存储结构的选择取决于具体的应用。1、邻接矩阵(1)存储

7、形式邻接矩阵是用一个二维数组来表示图中顶点间的相邻关系的数据结构。设图G=(V,E)，有n≥1个顶点，则所对应图G的邻接矩阵A是按如下定义的一个n×n的二维数组。若图G是一个网络，其邻接矩阵借助于邻接矩阵很容易判定任意两个顶点之间是否有边(或弧)相连，并容易求得各个顶点的度，操作方便。(2)邻接矩阵法的特点：1.存储空间：对于无向图而言，它的邻接矩阵是对称矩阵，所以可采用压缩存储法（下三角），其存储空间只需n(n+1)/2。但对于有向图而言，因为它的弧是有方向的，它的邻接矩阵不一定是对称矩阵，所以需要n2个存储空间。2.便于运算：采

8、用邻接矩阵表示法，便于判定图中任意两个顶点之间是否有边相连，即根据A[i，j]=0或1来判断。另外还便于求得各个顶点的度。2、邻接表(1)存储形式对一个有n个顶点图的顶点进行编号，顶点的编号从1到n。图的邻接表存储结构与树的孩子表示法