图的定义和术语及存储结构.ppt

1,数据结构课程的内容：,多对多（m:n),2,7.1基本术语7.2存储结构7.3图的遍历7.4图的连通性7.5图的应用,第7章图,3,7.1图的基本术语,其中：V是G的顶点集合，是有穷非空集；VR|v,wV且P(v,w),是有穷集.,问：当VR为空时，图G存在否？,V=vertex,图：记为Graph(V,VR),表示从v到w的一条弧，并称w为弧头，v为弧尾。P(v,w)定义了弧的意义或信息。,答：还存在！但此时图G只有顶点。,4,例如:,G=(V,VR),其中V=A,B,C,D,EVR=,无向图：由顶点集和边集构成的图(“边”无方向）,若VR必有VR,则称(v,w)为顶点v和顶点w之间存在一条边。,有向图：由顶点集和弧集构成的图（“弧”是有方向的）,5,例如:G=(V,VR)其中：V=A,B,C,D,E,FVR=(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F),若n个顶点的无向图有n(n-1)/2条边,称为无向完全图若n个顶点的有向图有n(n-1)条边,称为有向完全图,证明：,有向完全图有n(n-1)条边。,证明：若是有向完全图，则n个顶点中的每个顶点都有一条弧指向其它n-1个顶点,因此总边数=n(n-1),6,证明：从可以直接推论出无向完全图的边数因为无方向，两弧合并为一边，所以边数减半，总边数为n(n-1)/2。,无向完全图有n(n-1)/2条边。,例：判断下列4种图形各属什么类型？,7,稀疏图：稠密图：,设有两个图G(V,E)和G(V,E)。若VV且EE,则称图G是图G的子图。,子图：,边较少的图。通常边数远少于nlogn边很多的图。,无向图中，边数接近n(n-1)/2有向图中，边数接近n(n-1),B,例如：,8,15,9,7,21,11,3,2,有向网或无向网是弧或边带权的图。,邻接点：若边(v,w)VR，则顶点v和顶点w互为邻接点。,边(v,w)依附于顶点v和w，或者与顶点v,w相关联。,顶点v的度：是和v相关联的边的数目,记为TD(v).,顶点v的出度:以顶点v为尾的弧的数目;记为OD(v).,顶点v的入度:以顶点v为头的弧的数目,记为ID(v).,顶点的度(TD)=出度(OD)+入度(ID),问：当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何形状？,答：是树！而且是一棵有向树！,9,路径:设图G=(V,VR)中的一个顶点序列:v=vi,0,vi,1,vi,m=w中，(vi,j-1,vi,j)（或vi,j-1,vi,j）VR1jm,则称从顶点v到顶点w之间存在一条路径。路径长度：路径上边（或弧）的数目。,如:从A到F长度为3的路径A,B,C,F或A，E，C，F,简单路径:指序列中顶点不重复出现的路径。,简单回路:指序列中第一个顶点和最后一个顶点相同，其余顶点不重复出现的回路。,10,连通图：无向图G中任意两个顶点之间都有路径相连通。,连通分量：非连通图中的极大连通子图。,强连通图：在有向图中,每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,强连通分量：非强连通图中的极大强连通子图。,11,生成树：,生成森林：,假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。,由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。（对有向或无向图均适用）,12,CreatGraph(/返回v的“第一个邻接点”若该顶点在G中没有邻接点，则返回“空”。,NextAdjVex(G,v,w);/返回v的（相对于w的）“下一个邻接点”。若w是v的最后一个邻接点，则返回“空”。,插入或删除顶点,InsertVex(/在图G中增添新顶点v。,DeleteVex(/从顶点v起深度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。,BFSTraverse(G,v,Visit();/从顶点v起广度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。,遍历,15,7.2图的存储结构,图的特点：,链式存储结构：,顺序存储结构：,难！,（多个顶点，无序可言，无法仅以顶点坐标表达相互关系）,可用多重链表,邻接矩阵(数组)表示法邻接表(链式)表示法十字链表表示法邻接多重表表示法,但可用数组描述元素间关系。,非线性结构（m:n）,邻接矩阵,邻接表十字链表邻接多重表,各种表示法成立的原则：存入电脑后能唯一复原,16,建立一个顶点表和一个邻接矩阵。,1.邻接矩阵（数组）表示法,记录各个顶点信息,表示各个顶点之间关系,设图A=(V,E)有n个顶点，则图的邻接矩阵是一个二维数组A.arcsnn，定义为：,17,分析1：无向图的邻接矩阵是对称的；分析2：顶点i的度第i行(列)中1的个数；特别：完全图的邻接矩阵中，对角元素为0，其余全1。,例1：,邻接矩阵：,A.arcs=,（v1v2v3v4v5）,v1v2v3v4v5,0101010101010111010101110,顶点表：,无向图的邻接矩阵如何表示？,18,例2：有向图的邻接矩阵如何表示？,分析1：有向图的邻接矩阵可能是不对称的。分析2：顶点vi的出度=第i行元素之和;顶点vi的入度=第i列元素之和;顶点的度=第i行元素之和+第i列元素之和。,邻接矩阵：,A.arcs=,(v1v2v3v4),v1v2v3v4,注：在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧(即出度边）；第j列含义：以结点vj为头的弧(即入度边）。,顶点表：,0110000000011000,19,例3：有权图（即网络）的邻接矩阵如何表示？,定义：,邻接矩阵：,N.arcs=,(v1v2v3v4v5v6),顶点表：,5748956531,v1v2v3v4v5v6,20,容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。,邻接矩阵法优点：,邻接矩阵法缺点：,对稀疏图而言尤其浪费空间。,图的邻接矩阵在机内如何表示？（参见教材P161）,注：用两个数组分别存储顶点表和邻接矩阵#defineINFINITYINT_MAX/最大值#defineMAX_VERTEX_NUM20/假设的最大顶点数typedefenumDG,DN,UDG,UDNGraphKind;/有向图，有向网，无向图，无向网,21,typedefstructArcCell/弧的定义VRTypeadj;/VRType是顶点关系类型。/对无权图,用1或0表示相邻否；对带权图，则为权值类型。InfoType*info;/该弧相关信息的指针ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;,typedefstruct/图的定义VertexTypevexsMAX_VERTEX_NUM;/顶点向量AdjMatrixarcs;/邻接矩阵intvexnum,arcnum;/顶点数，弧数GraphKindkind;/图的种类标志MGraph;,22,2.邻接表（链式）表示法,对每个顶点vi建立一个单链表，把与vi有关联的边（或以vi为尾的弧)的信息链接起来，表中每个结点都设为3个域。,每个单链表还应当附设一个表头结点（设为2个域），存vi信息；,表结点,头结点,邻接点域，表示vi邻接点的位置,链域，指向下一条边或弧的结点,数据域，存储顶点vi信息,链域，指向单链表的第一个结点,每个单链表的头结点另外用顺序存储结构存储。,边或弧的信息,23,例1：无向图的邻接表如何表示？,邻接表：,请注意：邻接表不唯一！因各个边结点的链入顺序是任意的。,v1邻接点v4的位置,此无权图未开第3分量,TD(Vi)=单链表中Vi链接的结点个数,24,例2：有向图的邻接表如何表示？,邻接表(出边),逆邻接表(入边),0123,0123,在有向图的邻接表中不易找到指向该顶点的弧。,OD(Vi)=邻接表中Vi链接的结点数ID(Vi)=逆邻接表中Vi链接的结点数,TD(Vi)=OD(Vi)+ID(Vi),25,例3：已知某网的邻接（出边）表，请画出该网络。,80,64,1,2,5,当邻接表的存储结构形成后，图便唯一确定！,26,分析1：对于n个顶点e条边的无向图，邻接表中除了n个头结点外，只有2e个表结点,空间效率为O(n+2e)。若是稀疏图(en2)，则比邻接矩阵表示法O(n2)省空间。,邻接表存储法的特点：,分析2:在有向图中，邻接表中除了n个头结点外，只有e个表结点,空间效率为O(n+e)。若是稀疏图，则比邻接矩阵表示法合适。,它其实是对邻接矩阵法的一种改进，两个结点表示一条边或弧,邻接表的缺点：,邻接表的优点：,空间效率高；容易寻找顶点的邻接点；,判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。,27,讨论：邻接表与邻接矩阵有什么异同之处？,1.联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。2.区别：对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。3.用途：邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于稀疏图的存储（en2),28,图的邻接表在机内如何表示？（参见教材P163）,#defineMAX_VERTEX_NUM20/假设的最大顶点数,TypedefstructArcNode/弧结构intadjvex;/该弧所指向的顶点位置structArcNode*nextarcs;/指向下一条弧的指针InfoArc*info;/该弧相关信息的指针ArcNode；,29,Typedefstruct/图结构AdjListvertics;/应包含邻接表intvexnum,arcnum;/应包含顶点总数和弧总数intkind;/还应说明图的种类（用标志）ALGraph;,TypedefstructVNode/顶点结构VertexTypedata;/顶点信息ArcNode*firstarc;/指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;/邻接表,30,它是有向图的另一种链式存储结构。思路：将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。(1)开设弧结点，设5个域（每段弧是一个数据元素）(2)开设顶点结点，设3个域（每个顶点也是一个数据元素）,弧结点,3.十字链表表示法,tailvex:弧尾顶点位置headvex:弧头顶点位置hlink:弧头相同的下一弧位置tlink:弧尾相同的下一弧位置info:弧信息,31,data:顶点信息firstin:以顶点为弧头的第一条弧结点firstout:以顶点为弧尾的第一条弧结点,问：n个顶点的集合怎样储存？,顺序存储结构,顶点结点,十字链表优点：容易操作，如求顶点的入度、出度等。,空间复杂度和建表的时间复杂度都与邻接表相同。,32,012,例：画出有向图的十字链表。,弧结点,顶点结点,33,这是无向图的另一种链式存储结构，当对边操作时建议采用此种结构存储。（1）设立边结点，6个域（每条边是一个数据元素）（2）设立顶点结点，2个域（每个顶点也是一个数据元素）,边结点,4.邻接多重表表示法,mark：标志域，标记该边是否被搜索过。ivex，jvex:边依附的两个顶点位置ilink:指向下一条依附顶点i的边位置Jlink：指向下一条依附顶点j的边位置info:边信息,34,data:存储顶点信息firstedge:依附顶点的第一条边结点,顶点结点,问:n个顶点的集合怎样储存？,仍用顺序存储结构,邻接多重表优点：容易操作，如求顶点的度,对边操作等。,空间复杂度和建表的时间复杂度都与邻接表相同。,35,例：画出无向图的邻接多重表。,边结点,顶点结点,(v1,v2),(v1,v4),(v2,v5),(v2,v3),(v3,v4),(v3,v5),(v4,v5),