第七章图（Graphs)课件

第七章图（Graphs),图的基本概念图的存储表示图的遍历最小生成树活动网络最短路径,图例,结点,边:(v2,v5),图的构成：结点集：V=v1,v2,v3,v4,v5,边集：E=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5),图例,有向边V3：始点，v4:终点,图的构成：结点集：V=v1,v2,v3,v4,有向边集：E=,图的概念,图是由顶点(vertex)集合及顶点间的关系集合组成的一种数据结构：Graph(V,E)其中V=x|x某个数据对象是顶点的有穷非空集合；E=|x,yV是顶点之间关系的有穷集合，也叫做边(edge)的集合。,有向图G1V1=v1,v2,v3,v4,E1=,无向图G2V2=v1,v2,v3,v4,v5,E2=,或者E2=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5),(a)G1=(V1,E1),(b)G2=(V2,E2),图的术语,v3邻接到v4,v4的入度ID(v4)=1,v1的出度OD(v4)=1,性质:入度之和=出度之和=边数,结点的度数:TD(v)=ID(v)+OD(v),v1和v4互为邻接点,v4的度数为2TD(v4)=2,度数之和=边数的二倍（因为每个边“贡献”了两个度数）,子图设有两个图G(V,E)和G(V,E)。若VV且EE,则称图G是图G的子图。权某些图的边具有与它相关的数,称之为权。这种带权图叫做网络。完全图若有n个顶点的无向图有n(n-1)/2条边,则此图为完全无向图。有n个顶点的有向图有n(n-1)条边,则此图为完全有向图。,路径:(1),(简单路径)(2),(环)(3),路径:在图G(V,E)中,若存在边的序列(vi,vp1)、(vp1,vp2)、.、(vpm,vj)则称顶点序列(vivp1vp2.vpmvj)为从顶点vi到顶点vj的路径。,路径长度非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和,简单路径若路径上各顶点v1,v2,.,vm均不互相重复,则称这样的路径为简单路径。回路若路径上第一个顶点v1与最后一个顶点vm重合,则称这样的路径为回路或环。,连通图与连通分量在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。,强连通图在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。,生成树一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。,图的存储结构,邻接矩阵,存储原则:存储结点集和边集的信息.,（1）存储结点集；（2）存储边集：存储每两个结点是否有关系。,图的存储结构,有向图的邻接矩阵,带权图的邻接矩阵,邻接矩阵表示法,在图的邻接矩阵表示中:有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。,#defineMAX_VERTEX_NUM20/最大顶点个数typedefstructVertexTypevexsMAX_VERTEX_NUM；/顶点向量intarcsMAX_VERTEX_NUMMAX_VERTEX_NUM；/邻接矩阵intvexnum，arcnum；/图的当前顶点数和弧数MGraph;,容易计算结点的度数;容易判定两个结点间是否有边相连;容易判定结点之间是否有路径相连(计算Am);对于有向图，需要n个单元存储结点数据，n*n个单元存储邻接矩阵；无向图的邻接矩阵是对称的,可以压缩存储;存储量与结点数有关,与边数无关;若边数n2,则邻接矩阵是稀疏矩阵;,邻接表,每个结点拉出一个邻接边链表(以此结点为始点的所有邻接点),所有结点存储与一个表中,以A为始点的边链,以A为终点的边链,邻接表,图的邻接表存储表示,#defineMAX_VERTEX_NUM20typedefstructArcNode/单链表结点结构intadjvex；/该弧所指向的顶点的位置structArcNode*nextarc；/指向下一条弧的指针InfoType*info；/该弧相关信息的指针ArcNode；typedefstructVNode/顶点结构VertexTypedata；/顶点信息ArcNode*firstarc;/指向第一条依附该顶点的弧的指针VNode，AdjListMAX_VERTEX_NUM,Typedefstruct/邻接表结构AdjListvertices；intvexnum，arcnum；/图的当前顶点数和弧数ALGraph；,顶点vi的度恰为第i个链表中的结点数；在有向图中，第i个链表(出边表)中的结点个数是顶点的出度;,邻接表的特点,求入度必须遍历整个邻接表:在所有链表中其邻接点域的值为i的结点的个数是顶点vi的入度。为了求入度的便利,可以建立逆邻接表,即链表为入边表;,设图中有n个顶点，e条边，则用邻接表表示无向图时，需要n个顶点结点，2e个边结点；用邻接表表示有向图时，若不考虑逆邻接表，只需n个顶点结点，e个边结点。,邻接表,(B,D)边出现在D的边链表中,(B,D)边出现在B的边链表中,如果以边为处理对象,如删除一个边,则需扫描每个结点的边表,找到同一条边.,邻接多重表,将邻接表中代表同一个边的结点合并;边表合并为多重表;在邻接多重表中，每一条边只有一个边结点,为有关边的处理提供了方便。,边结点结构：,mark:记录是否处理过的标记;ivex,jvex:该边的两顶点位置;ilink:指向下一条依附于顶点ivex的边；jlink:指向下一条依附于顶点jvex的边。,markivexjverxilinkjlink,typedefemnuunvisited，visitedVisited；typedefstructEBoxVisitedmark；/访问标记intivex，jvex；/该边依附的两个顶点的位置structEBox*ilink，*jlink；/分别指向依附这两个顶点的下一条边InfoType*info；/该边信息指针EBox；,markivexjverxilinkjlink,data:存放与该顶点相关的信息，firstedge:指示第一条依附于该顶点的边的指针,顶点结点的结构：,datafirstedge,typedefstructVexBoxVertexTypedata；EBox*firstedge/指向第一条依附该顶点的边VexBox；,typedefstructVexBoxadjmulistMAX_VERTEX_NUM；intvexnum，edgenum；/无向图的当前顶点数和边数AMLGraph;,图的抽象数据类型,ADTGraph数据对象V：V是具有相同特性的数据元素的顶点集。数据关系R：R=VRVR=|v，wV且P(v，w)，谓词P(v，w)定义了弧的意义或信息,基本操作P：CreateGraph(/使用全局变量VisitFunc，使DFS不必设函数指针参数for(v=0；v=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G，w)；/对v的尚未访问的邻接顶点w递归调用DFS,每个结点最多调用一次,每个结点一次,循环工作量：寻找结点v的邻接点,时间复杂度：访问每个结点的时间：O(n);寻找每个结点的所有邻接结点工作量;设图中有n个顶点，e条边。如果用邻接表表示图，沿Firstedgelink链可以找到某个顶点v的所有邻接顶点w。无向图有2e个边结点，有向图有e个边，所以扫描边的时间为O(e);时间复杂度为O(n)+O(e)=O(n+e);如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为O(n)，则遍历图中所有的顶点所需的时间为O(n)+O(n2)=O(n2).,广度优先遍历,基本思想访问v1;访问v1的邻接点w1,w2,wm;依次访问w1,w2,的未被访问的邻接点，如此进行下去，直至访问完所有结点。,算法的实现需要设置一个数组visited标记结点是否访问过；设置一个队列纪录当前层访问的结点以备访问下一层结点。,取一个结点未访问结点v,访问v，标记，入队；（访问v的所有邻接点）：取队头元素，每次取v的下一个未访问的邻接点访问，标记并入队；重复2,直至队列空；如果图中仍然有未访问的结点，重复1，直至所有结点均已标记为访问过。,基本思想访问v1;访问v1的邻接点w1,w2,wm;依次访问w1,w2,的未被访问的邻接点，如此进行下去，直至访问完所有结点。,voidBFSTraverse(GraphG，Status(*Visit)(intv)/按广度优先非递归遍历图G。/使用辅助队列Q和访问标志数组visited。for(v=0；vG.vexnum；+v)visitedv=FALSE；InitQueue(Q)；/置空的辅助队列Q,for(v=0；vG.vexnum；+v)if(!visitedv)/v尚未访问visitedv=TRUE；visit(v)；EnQueue(Q，v)；/v入队列while(!QueueEmpty(Q)DeQueue(Q，u)/队头元素出队并置为ufor(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w)if(!Visitedw)/w为u的尚未访问的邻接顶点visitedw=TRUE;Visit(w);EnQueue(Q,w);/if/while/if/BFSTraverse,复杂度与深度优先相同,图的连通性,对于连通的无向图，从一个结点出发可以访问所有结点；结点与遍历时通过的边构成图的生成树；,深度优先生成树,广度优先生成树,对于不连通的无向图，则需从多个顶点出发访问；结点与遍历时经过的边构成生成树林。,深度优先生成森林,voidDFSTraverse(GraphG，Status(*visit)(intv)visitFunc=Visit;for(v=0；vlchild=p；first=FALSE；elseq-nextsibling=p；q=p；DFSTree(G,w,q)；/if/DFSTree,T,p,q,最小生成树,问题：设在n个城市间建立通信网络，要求建设费用尽可能低。,模型：n个结点的图，结点连线的权表示建设两点间通信线路的费用。在此网络的生成树中找出建设费用最小的生成树。,最小生成树,设G是一个带权的无向图（网络），则G的生成树可能有多个，生成树各边的权之和称为生成树的权。网络G的具有最小权的生成树称为G的最小生成树。,模型：n个结点的图，结点连线的权表示建设两点间通信线路的费用。求此网络的最小生成树。,应用：设在n个城市间建立通信网络，要求建设费用尽可能低。,Prim算法,假设N=(V，E)是连通网，T=(U,TE)表示下列算法构造的N上最小生成树。算法从U=u0(u0V)，TE=开始;重复执行下述操作,直至U=V为止：在所有uU，vV-U的边(u，v)E中找一条权最小的边(u，v)，将v并入U，同时边(u，v)并入集合TE。,设N有n个结点.则算法结束时,T中必有n个结点,n-1条边.在2中,如果有相同权的边,可任选一条,故最小生成树不唯一.,例:求下图的最小生成树,初始状态:U=v0,循环:对于每个结点viU，在vi与U中所有结点的邻接边中找出权最小的边ei=(vi,uk),并在这些边ei中求出权最小的边,设为(vi,uk).将uk并入U,(vi,uk)并入构造中的生成树。,MST性质,定理:假设N=(V，E)是一个连通网,T=(U,TE)是正在构造的生成树,若(u，v)是一条端点分别在U和V-U,并具有最小权值的边，则必存在一棵包含T和边(u，v)的最小生成树。,证明:用反证法.设任何包含T的最小生成树均不包含边e=(u,v).设T是一颗这样的树.将e加到T中必然得到一条回路:u,w1,wk,v,u其中必然存在边e=(wp,wp+1),wpU,wp+1U去掉边e后打开回路,又形成一颗生成树T,因为W(e)=W(e),故T是一颗包含T和e的最小生成树.矛盾!,Prim算法的实现,需要设置一个数组closedge,纪录当前每个结点viU到达U的最小权边(vi,uk)的信息,即closedegei为(uk,minimumW(vi,uk)|ukU)structVertexTypeadjvex；VRTypelowcost；closedgeMAX_VERTEX_NUM,初始状态:U=v0closedge0=(v0,0);/0表示相应结点属于Uclosedgei=(v0,W(vi,v0),在closedge中选择最小权的边。假设vkU是closedge中具有最小权边的结点,则置closedgeklowcost=0,即将vk并入U修改closedge:对于vjU,只需考虑可能出现的新边(vj,vk)是否具有更小的权closedgej=minclosedgej.lowcost,W(vj,vk),循环：,voidMiniSpanTree_PRIM(MGraphG，VertexTypeu)/用普里姆算法从第u个顶点出发构造网G的最小生成树T，/输出T的各条边。假设用邻接矩阵存储G.k=LocateVex(G，u)；for(j=0；j0)边printf(closedgek.adjvex,G.vexsk);/输出生成树的边closedgek.lowcost=0;/第k个顶点并入U集for(j=0;jG.vexnum;+j)if(G.acrskj.adjclosedgej.lowcost)closedgej=G.vexsk,G.arcskj.adj;/for/MiniSpanTree,时间复杂度：O(n)+O(n2)=O(n2),Kruskal算法,假设连通网N=(V，E)，使用Kruskal构造最小生成树的算法：最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V，)，图中每个顶点自成一个连通分量在E中选择代价最小且顶点落在T中不同的连通分量上的边，将此边加入到T中；重复上述过程2，直至所有顶点都在同一连通分量上为止。,克鲁斯卡尔算法构造最小生成树的过程,Kruskal算法可以用堆来实现。设e是图的边数，则构造最小生成树的总时间代价是O(eloge).,可见，Prim算法适合于边数多的图，而Kruskal算法适合于边数少(eadivex；/对i号顶点的每个邻接点的入度减1if(！(-indegreek)Push(S，k)；/若入度减为0，则入栈/for/whileif(countadivex；/对i号顶点的每个邻接点的入度减1if(！(-indegreek)Push(S，k)；/若入度减为0，则入栈/for/whileif(countvej)vej=r;当j的所有前驱已经排序时,vej便是所求的值.,datafirstarc,StatusTopologicalOrder(ALGraphG，Stack/i号顶点入T栈并计数for(p=G.verticesi.firstarc；p；p=p-nextarc)j=p-adjvex；/对i号顶点的每个邻接点的入度减1if(-indegreej=0)Push(S，j)；/若入度减为0，则入栈if(vei+*(p-info)vej)vej=vei+*(p-info)；/for*(p-info)=dut()/whileif(countadjvex；dut=*(p-info)；/dutif(vlk-dutadjvex；dut=*(p-info)；ee=vej；el=vlk-dut；tag=(ee=e1)?*：；printf(j，k，dut，ee，el，tag)；/输出关键活动/CriticalPath,在拓扑排序求vei和逆拓扑有序求vli时,所需时间为O(n+e),求各个活动的ek和lk时所需时间为O(e),总时间复杂度仍然是O(n+e)。,最短路径,问题的提出：一位旅客要从A城到B城他希望选择一条途中中转次数最少的路线；他希望选择一条途中所花时间最短的路线；他希望选择一条途中费用最小的路线；,这些问题均是带权图上的最短路径问题。,边上的权表示一站边上的权代表距离边的权代表费用,设G是带权有向图，称路径上的第一个顶点为源点(Source)，最后一个顶点为终点(Destination)；一条路经的长度是路径上边的权之和；最短路径问题：如果从图中某一顶点出发到达另一顶点的路径可能不止一条，如何找到一条长度最小的路径。,单源最短路径问题：设G是带权(=0)有向图，给定一个顶点v，求v到其余顶点的最短距离。,最短路径的Dijkstra算法,Dijkstra算法基本思想:按路径长度的递增次序，逐步产生最短路径.设源点为v0首先求出v0为源点长度最短的一条最短路径，即具有最小权的边;求出源点到各个顶点下一个最短路径：设其终点是u，则v0到u的最短路径或者是边，或者由一条已求得的最短路径（v0v)和边构成；重复2直到从顶点v0到其它各顶点的最短路径全部求出为止。,例：求v0其他各点的最短路径用S表示已求出最短路径的结点集初始状态：S=v0,第一条最短路径：(v0,v2)S=v0,v2,求下一条最短路径：先求v0到其他顶点vi的只经过S结点的路径：,v0-v1:v0-v3:(v0,v2,v3)60v0-v4:(v0,v4)30v0-v5:(v0,v5)100,第二条最短路径：(v0,v4)，S=v0,v2,v4,第一条最短路径：(v0,v2)S=v0,v2,求下一条最短路径：先求v0到其他顶点vi的只经过S结点的路径：,v0-v1:v0-v3:(v0,v2,v3)60,(v0,v4,v3)50v0-v5:(v0,v5)100,(v0,v4,v5)90,第二条最短路径：(v0,v4)，S=v0,v2,v4,第三条最短路径：(v0,v4,v3)，S=v0,v2,v4,v3,第四条最短路径：(v0,v4,v3,v5)，S=v0,v2,v4,v3,v5,用S表示当前找到最短路径的终点集；引入一个辅助数组D