您好,欢迎访问三七文档
2020/1/31第七章图(数据结构)1第四章图4.1图的定义和术语4.2图的存储结构4.3图的遍历4.4图的连通性问题4.5有向无环图及其应用4.6最短路径2020/1/31第七章图(数据结构)2图(Graph)是一种较线性表和树更为复杂的非线性结构。在线性结构中,结点之间的关系是线性关系,除开始结点和终端结点外,每个结点只有一个直接前趋和直接后继。在树形结构中,结点之间的关系实质上是层次关系,同层上的每个结点可以和下一层的零个或多个结点(即孩子)相关,但只能和上一层的一个结点(即双亲)相关(根结点除外)。然而在图结构中,对结点(图中常称为顶点)的前趋和后继个数都是不加限制的,即结点之间的关系是任意的。图中任意两个结点之间都可能相关。由此,图的应用极为广泛,特别是近年来的迅速发展,已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。2020/1/31第七章图(数据结构)34.1图的定义和术语图是由结点的有穷集合V和边的集合E组成。其中,为了与树形结构加以区别,在图结构中常常将结点称为顶点,若两个顶点之间存在一条边,就表示这两个顶点具有相邻关系。2020/1/31第七章图(数据结构)4图(Graph)是一种网状数据结构,其形式化定义如下:Graph=(V,RV={x|x∈DataObject}R={VR}VR={x,y|P(x,y)∧(x,y∈V)}DataObject为一个集合,该集合中的所有元素具有相同的特性。V中的数据元素通常称为顶点(vertex),VR是两个顶点之间关系的集合。P(x,y)表示x和y之间有特定的关联属性P。2020/1/31第七章图(数据结构)5抽象数据类型定义:ADTGraph数据对象V:一个集合,该集合中的所有元素具有相同的特性。数据关系R:R={VR}VR={x,y|P(x,y)∧(x,y∈V)}基本操作:(1)CreateGraph(G):创建图G。(2)DestoryGraph(G):销毁图G。(3)LocateVertex(G,v):确定顶点v在图G中的位置。若图G中没有顶点v,则函数值为“空”。2020/1/31第七章图(数据结构)6顶点:图中的数据元素通常称为顶点。V是顶点的有穷非空集合。VR是两个顶点之间关系的集合。若x,y∈VR,则x,y表示从顶点x到顶点y的一条弧(arc)。并称x为弧尾(tail)或起始点,称y为弧头(head)或终端点,此时图中的边是有方向的,称这样的图为有向图。若x,y∈VR,必有y,x∈VR,即VR是对称关系,这时以无序对(x,y)来代替两个有序对,表示x和y之间的一条边(edge),此时的图称为无向图。2020/1/31第七章图(数据结构)71324G11425G2(a)G1是有向图(b)G2是无向图3图7.12020/1/31第七章图(数据结构)8基本术语1.完全图、稀疏图与稠密图我们设n表示图中顶点的个数,用e表示图中边或弧的数目,并且不考虑图中每个顶点到其自身的边或弧。即若vi,vj∈VR,则vi≠vj。对于无向图而言,其边数e的取值范围是0~n(n-1)/2。我们称有n(n-1)/2条边(图中每个顶点和其余n-1个顶点都有边相连)的无向图为完全图。对于有向图而言,其边数e的取值范围是0~n(n-1)。我们称有n(n-1)条边(图中每个顶点和其余n-1个顶点都有弧相连)的有向图为有向完全图。对于有很少条边的图(enlogn)称为稀疏图,反之称为稠密图。2020/1/31第七章图(数据结构)92.设有两个图G=(V,{E})和图G′=(V′,{E′}),若V′V且E′E,则称图G′为G的子图。1131343412(a)G1的子图11253125412543(b)G2的子图2020/1/31第七章图(数据结构)103.邻接点对于无向图G=(V,{E}),如果边(v,v′)∈E,则称顶点v,v′互为邻接点,即v,v′相邻接。边(v,v′)依附于顶点v和v′,或者说边(v,v′)与顶点v和v′相关联。对于有向图G=(V,{A})而言,若弧v,v′∈A,则称顶点v邻接到顶点v′,顶点v′邻接自顶点v,或者说弧v,v′与顶点v和v′相关联。2020/1/31第七章图(数据结构)114.度、入度和出度对于无向图而言,顶点v的度是指和v相关联边的数目,记作TD(v)。例如:图G2中顶点v3的度是3,v1的度是2;在有向图中顶点v的度有出度和入度两部分,其中以顶点v为弧头的弧的数目成为该顶点的入度,记作ID(v),以顶点v为弧尾的弧的数目称为该顶点的出度,记作OD(v),则顶点v的度为TD(v)=ID(v)+OD(v)。例如:图G1中顶点v1的入度是ID(v1)=1,出度OD(v1)=2,顶点v1的度TD(v1)=ID(v1)+OD(v1)=3。一般地,若图G中有n个顶点,e条边或弧,则图中顶点的度与边的关系如下:2)(1niivTDe2020/1/31第七章图(数据结构)125.权与网在实际应用中,有时图的边或弧上往往与具有一定意义的数有关,即每一条边都有与它相关的数,称为权,这些权可以表示从一个顶点到另一个顶点的距离或耗费等信息。我们将这种带权的图叫做赋权图或网,如图所示。15241663191833142111656图7.32020/1/31第七章图(数据结构)136.无向图G=(V,{E})中从顶点v到v′的路径是一个顶点序列vi0,vi1,vi2,…,vin,其中(vij-1,vij)∈E,1≤j≤n。如果图G是有向图,则路径也是有向的,顶点序列应满足vij-1,vij∈A,1≤j≤n。路径的长度是指路径上经过的弧或边的数目。在一个路径中,若其第一个顶点和最后一个顶点是相同的,即v=v′,则称该路径为一个回路或环。若表示路径的顶点序列中的顶点各不相同,则称这样的路径为简单路径。除了第一个和最后一个顶点外,其余各顶点均不重复出现的回路为简单回路或简单环。2020/1/31第七章图(数据结构)147.在无向图G=(V,{E})中,若从vi到vj有路径相通,则称顶点vi与vj是连通的。如果对于图中的任意两个顶点vi、vj∈V,vi,vj都是连通的,则称该无向图G为连通图。例如:G2就是连通图。无向图中的极大连通子图称为该无向图的连通分量。在有向图G=(V,{A})中,若对于每对顶点vi、vj∈V且vi≠vj,从vi到vj和vj到vi都有路径,则称该有向图为强连通图。有向图的极大强连通子图称作有向图的强连通分量。如图所示。2020/1/31第七章图(数据结构)15ALBMJCFEDHGIK(a)无向图G3ALBMJCFEDHGIK(b)无向图G3的三个连通分量1342图7.4(c)有向图G1的两个连通分量2020/1/31第七章图(数据结构)168、生成树一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但是只有足以构成一棵树的n-1条边。如果在一棵生成树上添加一条边,必定构成一个环。一棵有n个顶点的生成树有且仅有n-1条边。如果一个图有n个顶点和小于n-1条边,则是非连通图;如果多于n-1条边,则一定有环。2020/1/31第七章图(数据结构)17ALMCFBJ图7.5图G3的最大连通分量的一棵生成树2020/1/31第七章图(数据结构)184.2图的存储结构由于图的结构比较复杂,任意两个顶点之间都可能存在联系,因此无法以数据元素在存储区中的物理位置来表示元素之间的关系,即图没有顺序映像的存储结构。常用的存储结构包括数组表示法、邻接表、邻接多重表和十字链表。2020/1/31第七章图(数据结构)194.2.1数组表示法图的邻接矩阵表示法(AdjacencyMatrix)也称作数组表示法。它采用两个数组来表示图。一个是用于存储顶点信息的一维数组;另一个是用于存储图中顶点之间关联关系的二维数组,这个关联关系数组被称为邻接矩阵。若图G是一个具有n个顶点的无权图,G的邻接矩阵是具有如下性质的n×n矩阵A:01],[jiA若vi,vj或(vi,vj)∈VR反之2020/1/31第七章图(数据结构)200110000000011000A1=0101010101010111010001100A2=图G1,G2的邻接矩阵若图G是一个有n个顶点的网,则它的邻接矩阵是具有如下性质的n×n矩阵A:ijwjiA],[若vi,vj或(vi,vj)∈VR反之2020/1/31第七章图(数据结构)21例如:图就是一个有向网N及其邻接矩阵的示例。图7.7v1v2v6v5v4v354855796122020/1/31第七章图(数据结构)22邻接矩阵表示法的C语言类型描述如下:#defineMAX-VERTEX-NUM10/*最多顶点个数*/#defineINFINITY32768/*表示极大值,即∞*/typedefenum{DG,DN,UDG,UDN}GraphKind;/*图的种类:DG表示有向图,DN表示有向网,UDG表示无向图,UDN表示无向网*/typedefcharVertexData;/*假设顶点数据为字符型*/typedefstructArcNode{AdjTypeadj;/*对于无权图,用1或0表示是否相邻;对带权图,则为权值类型*/2020/1/31第七章图(数据结构)23OtherInfoinfo;}ArcNode,AdjMatrix[MAX-VERTEX-NUM][MAX-VERTEX-NUM];typedefstruct{VertexDatavexs[MAX-VERTEX-NUM];/*顶点向量*/AdjMatrixarcs;/*邻接矩阵*/intvexnum,arcnum;/*图的顶点数和弧数*/GraphKindkind;/*图的种类标志*/}AdjMatrix;/*(AdjacencyMatrixGraph)*/2020/1/31第七章图(数据结构)24邻接矩阵法的特点如下:1、存储空间:对于无向图而言,它的邻接矩阵是对称矩阵(因为若(vi,vj)∈E(G),则(vj,vi)∈E(G)),因此我们可以采用特殊矩阵的压缩存储法,即只存储其下三角即可,这样,一个具有n个顶点的无向图G,它的邻接矩阵需要n(n-1)/2个存储空间即可。但对于有向图而言,其中的弧是有方向的,即若vi,vj∈E(G),不一定有vj,vi∈E(G),因此有向图的邻接矩阵不一定是对称矩阵,对于有向图的邻接矩阵的存储则需要n2个存储空间。2020/1/31第七章图(数据结构)252、便于运算:采用邻接矩阵表示法,便于判定图中任意两个顶点之间是否有边相连,即根据A[i,j]=0或1来判断。另外还便于求得各个顶点的度。对于无向图而言,其邻接矩阵第i行元素之和就是图中第i个顶点的度:njijiAvTD1],[)(对于有向图而言,其邻接矩阵第i行元素之和就是图中第i个顶点的出度:njijiAvOD1],[)(对于有向图而言,其邻接矩阵第i列元素之和就是图中第i个顶点的入度:njiijAvID1],[)(2020/1/31第七章图(数据结构)263、采用邻接矩阵存储法表示图,很便于实现图的一些基本操作,如实现访问图G中v顶点第一个邻接点的函数FirstAdjVertex(G,v)可按如下步骤实现:(1)首先,由LocateVertex(G,v)找到v在图中的位置,即v在一维数组vexs中的序号i。(2)二维数组arcs中第i行上第一个adj域非零的分量所在的列号j,便是v的第一个邻接点在图G中的位置。(3)取出一维数组vexs[j]中的数据信息,即与顶点v邻接的第一个邻接点的信息。4、对于稀疏图而言,不适于用邻接矩阵来存储,因为这样会造成存储空间的浪费。2020/1/31第七章图(数据结构)274.2.2邻接表图的邻接矩阵表示法(即图的数组表示法),虽然有其自身的优点,但对于稀疏图来讲,用邻接矩阵的表示方法会造成存储空间的很大浪费。邻接表(A
本文标题:图的术语什么的
链接地址:https://www.777doc.com/doc-3349955 .html