数据结构 第七章 图 7.1—7.22000版本(改).ppt

第7章图,线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。在树形结构中，数据元素之间有着层次关系，每一层上的数据元素可能和下一层中多个元素相关，只能和上一层中一个元素相关。在图形结构中，结点之间的关系是任意的，图中任意两个数据元素之间都可能相关。,7.1图的定义和术语,7.2图的存储结构,7.3图的遍历,7.4图的连通性问题,7.5有向无环图及其应用,7.6最短路径,图是由一个顶点集V（vertex）和一个弧集（边集）R（arc）构成的数据结构。Graph=(V,R)其中数据关系R，R=VR,VR|v,wV且P(v,w),表示从v到w的一条弧，谓词P(v,w)定义了弧的意义或信息。,图的定义:,7.1图的定义和术语,顶点：图中的数据元素。,若VR,则表示从v到w的一条弧，v为弧尾（初始点），w为弧头（终端点）。由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。,例如:,G1=(V1,VR1),其中V1=A,B,C,D,EVR1=,若VR必有VR,即VR是对称的，则以无序对（v,w)代替这两个有序对，表示v和w之间的一条边。,由顶点集和边集构成的图称作无向图。,例如:G2=(V2,VR2)V2=A,B,C,D,E,FVR2=(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F),名词和术语,权、网、子图,完全图、有向完全图、稀疏图、稠密图,邻接点、依附、相关联、度、入度、出度,路径、回路（环）、简单路径、简单回路（简单环）,连通、连通图、连通分量、强连通图、强连通分量,生成树、生成森林,假设图中有n个顶点，e条边，则,含有e=n(n-1)/2条边的无向图称作完全图；,含有e=n(n-1)条弧的有向图称作有向完全图；,图中最大边数是多少？,图中最大弧数是多少？,有很少条边或弧（enlogn）的图称为稀疏图，否则称作稠密图。,权：与图的边或弧相关的数。,网:带权的图。,B,有两个图G=(V,E)和图G=(V,E),且VV,EE,则称G为G的子图,A,B,E,C,F,例如:TD(B)=TD(A)=,边(v,v)依附于顶点v和v，边(v,v)和顶点v和v相关联。顶点v的度是和顶点v相关联的边的数目。,对于无向图G(V,E)，如果边(v,v)E，则称v和v互为邻接点，即v和v相邻接,3,2,顶点的出度（OutDegree）:以顶点v为尾的弧的数目,顶点的入度（InDegree）:以顶点v为头的弧的数目,ID(B)=,例如:OD(B)=,TD(B)=,对于有向图G(V,A)，如果弧A，则称顶点v邻接到顶点v,顶点v邻接自顶点v。,顶点的度(TD)=出度(OD)+入度(ID),1,2,3,无向图G=(V,E)中从顶点v到顶点v的路径是一个顶点序列（v=vi,0,vi,1,vi,m=v），其中(vi,j-1,vi,j)E，1jm。如果G是有向图，则路径也是有向的，顶点序列应满足E，1jm。,路径长度是路径上边的数目,A,B,E,C,F,简单路径:序列中顶点不重复出现的路径。,简单回路(简单环):除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。,回路（环）:第一个顶点和最后一个顶点相同的路径。,ABCFABCFAECFA,若图G中任意两个顶点vi,vjV，vi和vj都是连通的，则称此图为连通图,B,A,C,D,F,E,在无向图G中，如果从顶点v到顶点v有路径，则称v和v是连通的,无向图中的极大连通子图是连通分量,在有向图中，对于每一对vi,vjV，vi=vj，从vi到vj和从vj到vi都存在路径，则称此有向图为强连通图。,有向图中的极大强连通子图称作有向图的强连通分量。,A,B,C,F,一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边,B,C,F,E,如果在一棵生成树中添加一条边，必定构成一个环？一棵有n个顶点的生成树有且仅有n-1个边一个图有n个顶点和小于n-1条边，则是非连通图如果多于n-1条边，则一定有环有n-1条边的图不一定是生成树,B,C,F,E,一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧,有向图及其生成森林,结构的建立和销毁,插入或删除顶点,对邻接点的操作,对顶点的访问操作,遍历,插入和删除弧,基本操作,CreatGraph(/若G存在，u和G中顶点有相同特征。/若存在u，则返回该顶点在图中“位置”，否则返回其它信息。,GetVex(G,v);/返回v的值。,PutVex(/对v赋值value。,对邻接点的操作,FirstAdjVex(G,v);/返回v的第一个邻接点。若该顶点/在G中没有邻接点，则返回“空”。,NextAdjVex(G,v,w);/返回v的（相对于w的）下一个邻接/点。若w是v的最后一个邻接点，则/返回“空”。,插入或删除顶点,InsertVex(/在图G中增添新顶点v。,DeleteVex(/删除G中顶点v及其相关的弧。,插入和删除弧,InsertArc(/在G中增添弧，若G是无向的，/则还增添对称弧。,DeleteArc(/在G中删除弧，若G是无向的，/则还删除对称弧。,遍历,DFSTraverse(G,Visit();/深度优先遍历图G，并对每个顶点调用/函数Visit一次且仅一次。一旦visit()失败，则操作失败,BFSTraverse(G,Visit();/广度优先遍历图G，并对每个顶点调/用函数Visit一次且仅一次。一旦visit()/失败，则操作失败,一、数组(邻接矩阵)表示法,二、邻接表,三、有向图的十字链表,四、无向图的邻接多重表,7.2图的存储结构,一、数组(邻接矩阵)表示法,无向图的邻接矩阵用两个数组分别存储顶点的信息和顶点之间关系,B,A,C,D,F,E,为对称矩阵,ABCDEF,ABCDEF,利用邻接矩阵容易判定两个顶点间是否有边相连，无向图中，顶点vi的度是邻接矩阵第i行（或第j列）元素之和,有向图的邻接矩阵,为非对称矩阵,ABCDE,ABCDE,对于有向图，第i行元素之和为顶点vi的出度，第j列元素之和为顶点vj的入度,有向网的邻接矩阵,Aij=,wi,j若或(vi,vj)VR,反之,typedefstructArcCell/弧的定义VRTypeadj;/VRType是顶点关系类型。对无权图,/用1或0表示相邻否;对带权图,则为权值类型。InfoType*info;/该弧相关信息的指针ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;,#defineINFINITYINT_MAX/最大值#defineMAX_VERTEX_NUM20/最大顶点个数TypedefenumDG,DN,UDG,UDNGraphKind;/有向图，有向网，无向图，无向网,图的数组（邻接矩阵）存储表示,typedefstruct/图的定义VertexTypevexsMAX_VERTEX_NUM;/顶点向量AdjMatrixarcs;/邻接矩阵intvexnum,arcnum;/图的当前顶点数和弧数GraphKindkind;/图的种类标志MGraph;,StatusCreateUDN(MGraph/adj,info,For(k=0;k的权值If(IncInfo)Input(*G.);/若弧含有相关信息,则输入G.arcsji=G.arcsij;/置的对称弧ReturnOK;/CreateUDN,typedefstructArcNode/弧的结点结构intadjvex;/该弧所指向的顶点的位置structArcNode*nextarc;/指向下一条弧的指针InfoType*info;/该弧相关信息的指针ArcNode;,adjvexnextarcinfo,表结点结构,#defineMAX_VERTEX_NUM20,邻接点域链域数据域,二、图的邻接表,typedefstructVNode/顶点的结点结构VertexTypedata;/顶点信息ArcNode*firstarc;/指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;,datafirstarc,头结点结构,数据域链域,typedefstruct/图的结构AdjListvertices;intvexnum,arcnum;/图的当前顶点数和弧数intkind;/图的种类标志ALGraph;,图的结构,0A1B2C353D254E015F123,B,A,C,D,F,E,无向图的邻接表,邻接点域链域,数据域链域,1,4,045,顶点vi的度恰为第i个链表中的结点数,如何求某结点的度？,14,2,3,01,2,01234,ABCDE,有向图的邻接表,A,B,E,C,D,可见，在有向图的邻接表中不易找到指向该顶点的弧(入弧)，求入度需遍历整个邻接表,邻接点域链域,数据域链域,如果求入度？,A,B,E,C,D,有向图的逆邻接表,ABCDE,01234,在有向图的逆邻接表中，对每个顶点，链接的是指向该顶点的弧(入弧),邻接点域链域,数据域链域,三、有向图的十字链表,弧结点结构,弧尾顶点位置弧头顶点位置弧的相关信息,指向弧头相同的下一条弧,typedefstructArcBox/弧的结构表示inttailvex,headvex;/该弧的尾和头结点的位置structArcBox*hlink,*tlink;/分别为弧头相同和弧尾相同的弧的链域InfoType*info;/该弧相关信息的指针ArcBox;,#defineMAX_VERTEX_NUM20,指向弧尾相同的下一条弧,顶点的结点结构,顶点信息数据,指向以该顶点为弧头的第一个弧结点,指向以该顶点为弧尾的第一个弧结点,typedefstructVexNode/顶点的结构表示VertexTypedata;ArcBox*firstin,*firstout;/分别指向该顶点第一条入弧和出弧VexNode;,typedefstructVexNodexlistMAX_VERTEX_NUM;/表头向量intvexnum,arcnum;/有向图的当前顶点数和弧数OLGraph;,有向图的结构表示,四、无向图的邻接多重表,typedefstructEboxVisitIfmark;/访问标记intivex,jvex;/该边依附的两个顶点的位置structEBox*ilink,*jlink;/分别指向依附这两个顶点的下一条边InfoType*info;/该边信息指针EBox;,边的结点结构,typedefstruct/邻接多重表VexBoxadjmulistMAX_VERTEX_NUM;intvexnum,edgenum;/无向图的当前顶点数和边数AMLGraph;,typedefstructVexBoxVertexTypedata;EBox*firstedge;/指向第一条依附该顶点的边VexBox;,顶点的结点结构,无向图的结构表示,深度优先搜索,广度优先搜索,图的遍历：从图中某一顶点出发访遍图中其余顶点，且使每个顶点仅被访问一次。,图的遍历算法是求解图的连通性问题、拓扑排序和关键路径等算法的基础,7.3图的遍历,一、深度优先搜索,连通图的深度优先搜索遍历,从图中某个顶点V出发，访问此顶点，然后依次从V的未被访问的邻接点出发深度优先遍历图，直至图中所有和V有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。,V1,V2,V3,V4,V5,V6,V7,V8,深度优先搜索顶点访问序列：V1，v2，v4，v8，v5，v3，v6，v7,1.从深度优先搜索遍历连通图的过程类似于树的先根遍历；,解决的办法是：设一个辅助数组visited0.n-1,初始值为“假”或者零，一旦访问了顶点vi,便置visitedi为“真”或者为被访问时的次序号。,2.如何判别V的邻接点是否被访问？,voidDFSTraverse(GraphG,Status(*Visit)(intv)/对图G作深度优先遍历。VisitFunc=Visit;/使用全局变量VisitFunc,使DFS不必设函数指针参数for(v=0;vw1,V-w2,V-w8的路径长度为1；,V-w7,V-w3,V-w5的路径长度为2；,V-w6,V-w4的路径长度为3。,w1,V,w2,w7,w6,w3,w8,w5,w4,V1,V2,V3,V4,V5,V6,V7,V8,广度优先搜索顶点访问序列：V1，v2，v3，v4，v5，v6，v7，v8,voidBFSTraverse(GraphG,Status(*Visit)(intv)/按广度优先非递归遍历图Gfor(v=0;vG.vexnum;+v)visitedv=FALSE;/初始化访问标志数组InitQueue(Q);/置空的辅助队列Q,接下页,For(v=0;v=0;w=NextAdjVex(G,u,w)if(!visitedw)/w为u的尚未访问的邻接顶点visitedw=TRUE;visit(w);EnQueue(Q,w);/访问的顶点w入队列/if/while/if/BFSTraverse,队列Q,v1,v2,v3,v4,v5,v6,v7,v8,一、无向图的连通分量和生成树,对无向图进行遍历时对于连通图，从任一顶点出发，进行深度优先搜索或广度优先搜索，便可访问图中所有顶点。对于非连通图，则需从多个顶点出发进行搜索，每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。,7.4图的连通性问题,每个连通分量中的顶点集，和遍历时走过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的生成森林。,从图中任一顶点出发遍历图时，将边集分为两个集合，其中一个是遍历图过程中历经的边的集合，另一个是剩余边的集合。顶点集和遍历图过程中历经的边的集合构成连通图的极小连通子图，它是连通图的一棵生成树,非连通图,连通图,连通图,连通图,A,B,L,M,C,F,D,E,G,H,J,K,I,非连通图,A,B,L,M,C,F,J,邻接表存储结构参照教材P171图7.14,VoidDFSForest(GraphG,CSTree/建立以p为根的生成树/DFSForest,假设以孩子兄弟链表作生成森林的存储结构，建立无向图G的深度优先生成森林的孩子兄弟链表,T,p,q,VoidDFSTree(GraphG,intv,CSTree/从第w个顶点出发深度优先遍历图G，建立子生成树q/if/DFSTree,从第v个顶点出发深度优先遍历图G，建立以T为根的生成树,A,B,L,M,C,F,D,E,G,H,J,K,I,T,二、最小生成树(连通网),问题：假设要在n个城市之间建立通信联络网，则连通n个城市只需要修建n-1条线路，如何在最节省经费的前提下建立这个通讯网？,n个城市之间，最多可能设置n(n-1)/2条线路，在这些线路中选n-1条，使总的耗费最少,构造网的一棵最小生成树，即：在n(n-1)/2条带权的边中选取n-1条边（不构成回路），使“权值之和”为最小。,该问题等价于：,对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树可以是一个通信网。现在我们要选取这样一棵树，使总耗费最少，即树上各边代价之和最小。,算法二：克鲁斯卡尔算法(Kruskal),算法一：普里姆算法(Prim),取图中任意一个顶点v作为生成树的根，之后往生成树上添加新的顶点w。在添加的顶点w和已经在生成树上的顶点v之间必定存在一条边，并且该边的权值在所有连通顶点v和w之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有n个顶点为止。,普里姆算法的基本思想,在生成树的构造过程中，图中n个顶点分属两个集合：已落在生成树上的顶点集U和尚未落在生成树上的顶点集V-U，则应在所有连通U中顶点和V-U中顶点的边中（非本集合内部的边）选取权值最小的边。,一般情况下所添加的顶点应满足下列条件:,U,V-U,所得生成树权值和,=14+8+3+5+16+21=67,a,c,d,f,b,e,U,V-U,g,a,b,c,d,e,g,f,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,g,f,7,14,8,5,3,16,21,设置一个辅助数组，对当前VU集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边：,structVertexTypeadjvex;/顶点集U中顶点VRTypelowcost;/边的权值closedgeMAX_VERTEX_NUM;,a,b,c,d,e,g,f,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,7,a,a,a,19,14,18,14,例如:,e,12,e,e,8,16,8,d,3,d,d,7,21,3,c,5,5,abcdefg,g,f,书上P174图7.17第一行标注出序号15对应结点,voidMiniSpanTree_P(MGraphG,VertexTypeu)/用普里姆算法从顶点u出发构造网G的最小生成树k=LocateVex(G,u);for(j=0;jG.vexnum;+j)/辅助数组初始化if(j!=k)closedgej=u,G.arcskj.adj;closedgek.lowcost=0;/初始，Uufor(i=1;iG.vexnum;+i)/MiniSpanTree,/继续向生成树上添加顶点,k=minimum(closedge);/求出加入生成树的下一个顶点(k)printf(closedgek.adjvex,G.vexsk);/输出生成树上一条边closedgek.lowcost=0;/第k顶点并入U集for(j=0;jadjvex;if(visitedv=0)DFSArticul(G,v);/从第v顶点出发深度优先查找关节点/while/if/FindArticual,for(p=G.verticesv0.firstarc;p;p=p-nextarc),voidDFSArticul(ALGraphG,intv0)/从第v0个顶点出发深度优先遍历图G,/查找并输出关节点,visitedv0=min=+count;/v0是第count个访问的顶点,并设lowv0的初值为min,/检查v0的每个邻接点,lowv0=min;,/DFSArticul,w=p-adjvex;/w为v0的邻接顶点if(visitedw=0)/w未曾被访问DFSArticul(G,w);/返回前求得lowwelse,if(loww=visitedv0)printf(v0,G.verticesv0.data);/输出关节点,if(visitedwadjvex;/对i号顶点的每个邻接点的入度减1if(!(-indegreek)Push(S,k);/若入度为零，则入栈/for/whileif(countnextarc)k=p-adjvex;/对j号顶点的每个邻接点的入度减1if(-indegreek=0)Push(S,k);/若入度减为零则入栈if(vej+*(p-info)vek)vek=vej+*(p-info);/for*(p-info)=dut();/whileif(countnextarc)k=p-adjvex;dut=*(p-info);/dutif(vlk-dutadjvex;dut=*(p-info);ee=vej;el=vlk-dut;tag=(ee=el)?*:;printf(j,k,dut,ee,el,tag);/输出关键活动/CriticalPath,用图的结构表示交通网络，图中顶点表示城市，边表示城市间的交通联系。这个咨询系统可以回答各种问题，例如旅客希望选择交通费用最少的路线，司机希望选择距离最短的路线。为了在图中表示有关信息，可对边赋以权，权值表示两城市间的距离、时间或交通费用。路径长度的度量不是路径上边的数目，而是路径上边的权值之和。下面讨论两种最常见的最短路径问题。,7.6最短路径,从某个源点到其余各顶点的最短路径(迪杰斯特拉算法),每一对顶点之间的最短路径（弗洛伊德算法）,求从源点到其余各顶点的最短路径的算法的基本思想:,依路径长度递增的次序产生最短路径,迪杰斯特拉(Dijkstra)算法,在这条路径上，必定只含一条弧，假设这条弧的权值最小，v1加到最短路径终点集当中。,长度最短的最短路径：,它只可能有两种情况：或者是直接从源点v0到另一点v2(只含一条弧)；或者是从源点经过顶点v1，而最后到达v2的路径(由两条弧组成),下一条长度次短的最短路径：,其余最短路径：,它可能有三种情况：或者是直接从源点v0到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点。,它或者是直接从源点到该点(只含一条弧)；或者是从源点经过已求得最短路径的顶点，再到达该顶点。,再下一条长度次短的最短路径:,求最短路径的迪杰斯特拉算法：,设置辅助数组D，其中每个分量Di表示当前所求得的从源点到其余各顶点vi的最短路径的长度。,Di=或者=+,1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。,V0和Vk之间存在弧,V0和Vk之间不存在弧,其中的最小值即为最短路径的长度，设S为已找到从源点出发的最短路径的终点的集合,初始状态为空集。选择vj，使得Dj=MinDi|viV-SVj是当前求得的一条从源点出发的最短路径的终点，令S=Sj,2）修改从源点出发到集合V-S上任一顶点vk可达的最短路径长度。若Dj+arcsjkDk则将Dk改为Dj+arcsjk重复操作，由此求得从v到图上其余各顶点的最短路径是依路径长度递增的序列。,v5,v4,v0,v1,v2,v3,100,60,30,10,20,50,10,5,S为已求得最短路径终点的集合,有向图从v0到其余各点的最短路径,voidShortestPath_DIJ(MGraphG,intv0,PathMatrix/初始化,v0顶点属于S集,/开始主循环,每次求得v0到某个v顶点的最短路径,并加v到S集for(i=1;iG.vexnum;+i)min=