《图的定义和术语》PPT课件

第6章图,6.1图的定义和术语6.2图的存储结构6.3图的遍历6.4最小生成树6.5最短路径6.6拓扑排序6.7典型题例6.8实训例题,6.1图的定义和术语611图的定义,图(Graph)图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)其中：V(G)是顶点的非空穷集合有穷集合E(G)是用顶点对表示的边（Edge）的有穷集合，可以为空。无向图若图G中表示边的顶点对是无序的（称无向边），则称图G为无向图。通常用(vi，vj)表示顶点vi和vj间的无向边。有向图若图G中表示边的顶点对是有序的（称有向边），则称图G为有向图。通常用表示从顶点vi到顶点vj的有向边，有向边也称为弧，顶点vi称为弧尾（或初始点），顶点vj称为弧头（或终端点），用由弧尾指向弧头的箭头形象地表示弧。,例如图6.1所示，G1是无向图，其中，V=v0，v1，v2，v3，v4，E=(v0，v1)，(v0，v3)，(v0，v4)，(v1，v4)，(v1，v2)，(v2，v4)，(v3，v4)；G2是有向图，其中，V=v0，v1，v2，v3，E=，。,6.1.2图的基本术语,邻接点在无向图G(V，E)中，若边(vi，vj)E，则称顶点vi和vj互为邻接点（Adjacent），或vi和vj相邻接，并称边(vi，vj)与顶点vi和vj相关联，或者说边(vi，vj)依附于顶点vi，vj。在有向图G（V，E）中，若弧E，则称顶点vi邻接到顶点vj，顶点vj邻接自顶点vi，并称弧和顶点vi，vj相关联。顶点的度、入度和出度顶点vi的度（Degree）是图中与vi相关联的边的数目，记为TD(vi)。对于有向图，顶点vi的度等于该顶点的入度和出度之和，即TD（vi）ID（vi）OD（vi）。其中，顶点vi的入度（InDegree）ID（vi），是以vi为弧头的弧的数目；顶点vi的出度（OutDegree）OD（vi）是以vi为弧尾的弧的数目。,完全图、稠密图、稀疏图若无向图中有n(n1)条边，即图中每对顶点之间都有一条边，则称该无向图为无向完全图。若有向图中有n(n1)条弧，即图中每对顶点之间都有方向相反的两条弧，则称该有向图为有向完全图。有很少条边或弧（evertexi.firstarc=NULL；/*边表置为空表*/,for(k=0；karcnum；k+)/*建立边表*/printf(“pleaseinputedges:n”);scanf(dd，/*邻接点序号为i*/s-nextarc=g-vertexj.firstarc；/*将新结点*s插入顶点vj的边表头部*/g-vertexj.firstarc=s；/*CreateALGraph*/,在建立邻接表或逆邻接表时，若输入的顶点信息即为顶点的编号，则建立邻接表的时间复杂度为O(n+e)，否则，需要通过查找才能得到顶点在图中位置，则时间复杂度为O(n*e)。注意：从逻辑上说，一个顶点的所有邻接点之间并没有先后之分，但当图的具体的存储结构建立后，一个顶点的所有邻接点之间就可以分出先后。,6.2.3邻接矩阵和邻接表的比较,（1）邻接矩阵是一种静态的存储结构；邻接表是一种动态的存储结构。（2）邻接矩阵是顺序存储结构，因此相应的算法实现较简单；邻接表中有指针，因此相应的算法较为复杂。（3）邻接矩阵占用的存储单元数目只与图中顶点个数有关，而与边（弧）的数目无关，对于一个具有n个顶点e条边的图G，其邻接矩阵所占存储单元为n2，而其邻接表（和逆邻接表）中有n个表头结点和2e个边（弧）结点；在稀疏图中边的数目远远小于n2（即en2），这时用邻接表比用邻接矩阵节省存储空间；若是稠密图，因邻接表中要附加链域，则选取邻接矩阵更合适。（4）在邻接矩阵中，很容易判定任意两个顶点vi，vj之间是否有边或弧相连，只要判定矩阵中的第i行第j列上的元素的值即可；但是在邻接表中，需搜索第i个或第j个边表，最坏情况下要耗费O（n）时间。(5）在邻接矩阵中求边的数目e，必须检测整个矩阵，所耗费的时间是O（n2），与e的大小无关；而在邻接表中，只要对每个边表的结点个数计数即可求得e，所耗费的时间是O（e+n）。因此，当earcsij=1)/*DFS1*/,以邻接表作为图的存储结构的深度优先搜索遍历算法描述如下：intvisitedMaxSize=0;voidDFS2(AdjList*g,inti)/*从第i个顶点出发深度优先遍历图G，G以邻接表表示*/printf(“%3c”,g-vertexi.data);/*访问顶点vi*/visitedi=1;for(p=g-vertexi.firstarc;p;p=p-nextarc)if(!visitedp-adjvex)DFS2(g,p-adjvex);/*DFS2*/,算法分析：分析DFS算法得知，遍历图的过程实质上是对每个顶点搜索其邻接点的过程。耗费的时间取决于所采用的存储结构。假设图中有n个顶点，那么，当用邻接矩阵表示图时，搜索一个顶点的所有邻接点需花费的时间为O（n），则从n个顶点出发搜索的时间应为O（n2）,所以算法DFS1的时间复杂度是O（n2）；如果使用邻接表作为图的存储结构时，搜索一个顶点的所有邻接点需花费的时间为O（e），其中e为无向图中边的数目或有向图中弧的数目，则算法DFS2的时间复杂度为O(n+e)。,6.3.2连通图的广度优先搜索,基本思想:从图中某个顶点vi出发，在访问了vi之后，依次访问vi的各个未曾访问过的邻接点；然后分别从这些邻接点出发，依次访问它们的未曾访问过的邻接点，直至所有和起始顶点vi有路径相通的顶点都被访问过为止。,以图6.11(a)中图G为例说明广度优先搜索的过程顶点访问序列为：v0v1v2v3v4v5v6v7。,以邻接矩阵作为图的存储结构的广度优先搜索遍历算法描述如下：intvisitedMaxSize=0;voidBFS1(AdjMatrixg,inti)/*从第i个顶点出发广度优先遍历图G，G以邻接矩阵表示*/intk;QueueQ;/*定义一个队列*/printf(“%3c”,g.vexsi);/*访问顶点vi*/visitedi=1;InitQueue(/*vi入队列*/,while(!Empty(Q)DeQueue(/*vj入队列*/*BFS1*/,以邻接表作为图的存储结构的广度优先搜索遍历算法描述如下：intvisitedMaxSize=0;voidBFS2(AdjListg,inti)/*从第i个顶点出发广度优先遍历图G，G以邻接表表示*/intk,;ArcNode*p;QueueQ;/*定义一个队列*/printf(“%3c”,G.vertexi.data);/*访问顶点vi*/visitedi=1;InitQueue(/*vi入队列*/,while(!Empty(Q)DeQueue(/*求k的下一个邻接点*/*BFS2*/,算法分析：分析上述算法，每个顶点至多进一次队列，所以算法中的内、外循环次数均为n次，故算法BFS1的时间复杂度为O（n2）；若采用邻接表存储结构，广度优先搜索遍历图的时间复杂度与深度优先搜索是相同的。,6.3.3非连通图的遍历,如果给定的图是不连通的，则调用上述遍历算法（深度或广度优先搜索算法）只能访问到起始顶点所在的连通分量中的所有结点，其它连通分量中的结点是访问不到的。为此，需从每一个连通分量中选取起始顶点，分别进行遍历，才能访问到图中的所有顶点。深度优先搜索遍历非连通图的算法描述如下：voidDFSUnG(AdjMatrix*g)intifor(i=0;ivexnum;i+)ifvisitedi=0)DFS(g,i);,6.4最小生成树641生成树及最小生成树,1生成树一个连通图的生成树是是一个极小连通子图，它含有图中全部顶点，但只有n-1条边。一个连通图的生成树是不惟一的。由深度优先搜索得到的生成树称为深度优先生成树；由广度优先搜索得到的生成树称为广度优先生成树。,2最小生成树在一个连通网的所有生成树中，各边的权值之和最小的那棵生成树称为该连通网的最小代价生成树（MinimumCostSpanningTree），简称为最小生成树。构造最小生成树的算法很多，其中多数算法都利用了最小生成树的一种称之为MST的性质。MST性质：假设G=（V，E）是一连通网，U是顶点集V的一个非空子集。若（u，v）是一条具有最小权值的边，其中uU，vV-U，则必存在一棵包含边（u，v）的最小生成树。常用的构造最小生成树的算法有普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。,6.4.2普里姆算法,1算法的思想假设G（V，E）是一个连通网，U是最小生成树中的顶点的集合，TE是最小生成树中边的集合。初始令U=u1（u1V）,TE=，重复执行下述操作：在所有uU，vW=V-U的边(u，v)E中选择一条权值最小的边(u，v)并入集合TE，同时将u并入U中，直至U=V为止。此时TE中必有n-1条边，则T=(U，TE)便是G的一棵最小生成树。普利姆算法逐步增加集合U中的顶点，直至U=V为止。,2算法的实现为了实现普里姆算法，需要附设一个辅助数组closedge，以记录从U到VU的具有最小权值的边。其数据类型定义如下：structclosedgeVexTypeadjvex;intlowcost;closedgeMaxSize;对于每个顶点viVU，在辅助数组closedge中存在一个分量closedgei，其中closedgei.lowcost存储所有与vi邻接的、从U到VU的那组边中的最小边上的权值，显然有closedgei.lowcostMincost(u,vi)|uU，其中cost(u,vi)表示边(u,vi)的权值。一旦顶点vi并入U，则closedgei.lowcost置为零；而closedgei.adjvex存储依附于该边的U中的顶点。图6.15展示了在图6.14所示的构造最小生成树的过程中，辅助数组closedge中各分量值的变化情况。P161,算法描述如下：intLocatVex(AdjMatrixg,VexTypeu0);intMininum(structclosedgeclosedge,intvexnum);voidPrim(AdjMatrixg,VexTypeu0)/*从顶点u0出发构造网G的最小生成树T，输出T中的每条边*k=LocatVex(g,u0);*确定顶点u0在网G中的序号*closedgek.lowcost=0;for(j=0;jg.vexnum;j+)/*初始化辅助数组*if(j!=k)closedgej.adjvex=u0;closedgej.lowcost=g.arcskj;closedgek.lowcost=0;/*初始U=u0*/,for(i=1;i=g.vexnum-1;i+)k=Mininum(closedge,g.vexnum);/*求权值最小的顶点的序号，vk*/printf(“(%c,%c),%d”,closedgek.adjvex,g.vexsk,closedgek.lowcost);/*输出生成树T的边及权值*closedgek.lowcost=0;/*顶点vk并入U*/for(j=0;jg.vexnum;j+)/*重新调整closedge*/if(g.arcskjclosedgej.lowcost)closedgej.lowcost=g.arcskj;closedgej.adjvex=g.vexsk;/*if*/*for*/*Prim*/,intLocatVex(AdjMatrixg,VexTypeu0)/*返回顶点u0在网G中的序号*for(i=0;ig.vexnum;i+)if(g.vexsi=u0)return(i);/*LocatVex*/intMininum(structclosedgeclosedge,intvexnum)/*在辅助数组closedge中求出权值最小的边的顶点序号min,且vminV-U*/for(i=0;ivexnum;i+)if(closedgei.lowcost!=0)break;min=i;for(i=0;ivexnum;i+)if(closedgei.lowcost!=0/*Mininum*/假设网中有n个顶点，普里姆算法中有两个循环，所以时间复杂度为（n），它与网中边的数目无关，因此普里姆算法适合于求边稠密的网的最小生成树。,643克鲁斯卡尔算法,基本思想:按权值递增的次序来选择合适的边构成最小生成树。假设G（V，E）是连通网，最小生成树T（V，TE）。初始时，TE，即T仅包含网G的全部顶点，没有一条边，T中每个顶点自成一个连通分量。算法执行如下操作：在图G的边集E中按权值递增次序依次选择边（u,v），若该边依附的顶点u,v分别是当前的两个连通分量中的顶点，则将该边加入到TE中；若u,v是当前同一个连通分量中的顶点，则舍去此边而选择下一条权值最小的边。依此类推直到T中所有顶点都在同一连通分量上为止，此时T便是G的一棵最小生成树。与普里姆算法不同，克鲁斯卡尔算法是逐步增加生成树的边。,克鲁斯卡尔算法可描述如下：T=(V,);While(T中的边数en-1)从E中选取当前权值最小的边（u,v）；if(u,v)并入T之后不产生回路)将边（u,v）并入T中；else从E中删去边（u,v）；可以证明克鲁斯卡尔算法的时间复杂度是（eloge），其中e是网G的边的数目。克鲁斯卡尔算法适合于求边稀疏的网的最小生成树。,现以图6.14(a)所示的网为例，按克鲁斯卡尔算法构造最小生成树。其构造过程如图6.16所示。,65最短路径,问题提出用带权的有向图表示一个地区的交通运输网，图中：顶点表示城市边上的权表示城市间的公路权表示两个城市间的距离，或者表示通过这段公路所需的时间或需要花费的代价等问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径最短路径从某个源点到其余各顶点的最短路径,迪杰斯特拉(Dijkstra)算法按路径长度递增的次序产生最短路径的算法基本思想：把V分成两组：S：已求出最短路径的顶点的集合,V-S=T：尚未确定最短路径的顶点集合初始时，S中只包含源点v0，T中包含除源点外的其余顶点，此时各顶点的当前最短路径长度为源点到该顶点的弧上的权值，然后按最短路径长度递增的次序逐个把T中的顶点加到S中去，直至从v0出发可以到达的所有顶点都包括到S中为止。保证：（1）从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度（2）每个顶点对应一个距离值S中顶点：从V0到此顶点的最短路径长度T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度,设有向图G有n个顶点（v0为源点），其存储结构用邻接矩阵表示。算法实现时需要设置三个数组sn、distn和pathn。s用以标记那些已经找到最短路径的顶点集合S，若si=1,则表示已经找到源点到顶点vi的最短路径，若si=0，则表示从源点到顶点vi的最短路径尚未求得，数组的初态为：s0=1，si=0,i=1,2,n-1，表示集合S中只包含一个顶点v0。数组dist记录源点到其他各顶点的当前的最短距离，其初值为：disti=g.arcs0ii=1,2,n-1path是最短路径的路径数组，其中pathi表示从源点v0到顶点vi之间的最短路径上该顶点的前驱顶点，若从源点到顶点vi无路径，则pathi=-1。,求最短路径步骤初使时令S=V0,T=其余顶点，T中顶点对应的距离值若存在，为弧上的权值若不存在，为从T中选取一个其距离值为最小的顶点W，加入S，即令sw=1；对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值，即从原来的distj和distw+g.arcswj中选择较小的值作为新的distj。重复上述步骤，直到S中包含所有顶点，即S=V为止,网采用邻接矩阵做存储结构，用迪杰斯特拉算法求最短路径的算法描述如下：voidDijkstra(AdjMatrixg,intv0,intpath,intdist)/*求有向网g的从顶点v0到其余顶点v的最短路径，pathv是v0到v的最短路径上v的前驱顶点，distv是路径长度*intsMaxSize,v;for(v=0;vg.vexnum;v+)*初始化s、dist和path三个数组*sv=0;distv=g.arcsv0v;if(distvMAXINT*初始时源点v0S集*,*循环求v0到某个顶点v的最短路径，并将v加入S集*for(i=0;ig.vexnum-1;i+)min=MAXINT;/*MAXINT是一个足够大的数*/v=-1;/*v记录找到的最小距离的顶点序号*/for(w=0;wg.vexnum;w+)if(!sw/*if*/*if*/*for*/*Dijkstra*/,通过pathi向前推导直到v0为止，可以找出从v0到顶点vi的最短路径。例如，对于图6.17(a)的有向网络，按上述算法计算出的path数组的值为：求顶点v0到顶点v3的最短路径的计算过程为：path3=2,说明路径上顶点v3之前的顶点是顶点v2；path2=1,说明路径上顶点v2之前的顶点是顶点v1；path1=0,说明路径上顶点v1之前的顶点是顶点v0。则顶点v0到顶点v3的路径为v0，v1，v2，v3。迪杰斯特拉算法中有两个循环次数为顶点个数n的嵌套循环，所以其时间复杂度为（n2）。,输出最短路径的算法描述如下：voidPrintPath(intv0,intp,intd,intvexnum)*输出源点v0到其余顶点的最短路径和路径长度,路径逆序输出*for(i=0;ivexnum;i+)if(diMAXINT/*PrintPath*/,对于图6.17(a)的有向网络，其邻接矩阵如图6.18(a)所示，利用Dijkstra算法计算从顶点v0到其他各顶点的最短路径的动态执行情况如图6.18(b）所示。P166,最后的输出结果是：v-v0:8v2-v1-v0:13v3-v2-v1-v0:19v4-v3-v2-v1-v0:21v5-v0：13v6vertexj.data);/*输出顶点*/n+;q=g-vertexj.firstarc;/*找第一个邻接点*/while(q!=NULL)k=q-adjvex;g-vertexk.indegree-;if(g-vertexk.indegree=0)/*入度为0的邻接点入栈*/s+top=k;q=q-nextarc;/*找下一个邻接点*/*while*/*while*/printf(nn=%dn,n);if(nvexnum)printf(Thenetworkhasacyclen);/*TopSort*/算法分析：O(n+e)。,67典型题例,【例1】已知一个无向图的邻接表如图6.22所示，要求：（1）画出该无向图；（2）根据邻接表，分别写出按DFS和BFS算法从顶点v0开始遍历的遍历序列，并画出DFS生成树和BFS生成树。6v60123图6.22一个图的邻接表表示:,（1）该无向图如图6.23(a)所示。（2）根据该无向图的邻接表表示，从顶点v0开始的深度优先遍历的序列为：v0v2v3v1v4v6v5，其相应的生成树如图6.23(b)所示；从顶点v0开始的广度优先遍历的序列为：v0v2v5v6v1v3v4，其相应的生成树如图6.23(c)所示。,【例2】以邻接表为存储结构，利用DFS搜索策略设计一个算法，求图中从顶点u到顶点v的一条简单路径，并输出该路径。从顶点u开始，进行深度优先搜索，如果能够搜索到顶点v，则表明从顶点u到顶点v有一条路径。由于在搜索过程中每个顶点只访问一次，所以这条路径一定是简单路径。因此，只要在搜索过程中把当前的搜索线路记录下来，并在搜索到顶点v时退出搜索过程，就可以得到从u到v的一条简单路径。为了记录当前的搜索路线，设立一个数组pathn，当从某个顶点vi找到其邻接点vj进行访问时，将pathi置为j，即pathi=j。这样，当退出搜索后，输出path数组，就可以得到从u到v的简单路径。,算法描述如下：intpathMaxSize;intvisitedMaxSize,found;/*found为是否找到路径标志*/voidSimplePath(AdjList*g,intu,intv)/*找一条从u到v的简单路径*/for(i=0;ivexnum;i+)visitedi=0;found=0;DFSPath(g,u,v);/*利用深度优先搜索找一条从u到v的简单路径*/*SimplePath*,voidDFSPath(Adjlist*g,intu,intv)ArcNode*q;if(found)return;visitedu=1;for(q=g-vertexu.firstarc;q;q=q-nextarc)if(q-adjvex=v)pathu=v;found=1;PrintPath(u,v);/*输出路径*/elseif(!visitedq-adjvex)pathu=q-adjvex;DFSPath(g,q-adjvex,v);/*DFSPath*/,voidPrintPath(intu,intv)printf(“%d”,u);for(k=pathu;k!=v;k=pathk)printf(“%d”,k);printf(“%d”,v);/*PrintPath*/,68实训例题,实训例题1设计学习计划【问题描述】软件专业的学生要学习一系列课程，其中有些课程在其先修课程完成后才能学习，如6.6节图6.19所示。假设每门课程的学习时间为一学期，试为该专业的学生设计学习计划，使他们能够在最短的时间内修完这些课程。【基本要求】功能：为学生设计学习计划。输入：输入学生需要学习的课程之间的先修关系。即把课程之间的先修关系表示为AOV网，输入该网。输出：学生学习课程的计划，即输入的AOV网的拓扑序列。,【数据结构】采用AOV网表示课程之间的先修关系，因为在算法中要涉及求顶点的邻接点，所以存储结构采用邻接表比较合适。其类型描述为：typedefintVertexType;/*为简单起见，顶点信息设为顶点序号*/typedefstructArcNodeintadjvex;/*邻接点序号*/structArcNode*nextarc;otherinfoinfo;ArcNode;/*边结点*/typedefstructVertexNodeVertexTypedata;intindegree;/*入度*/ArcNode*firstarc;VertexNode;/*表头结点*/typedefstructVertexNodevertexMaxSize;intvexnum,arcnum;AdjList;/*图的邻接表*/,【算法思想】以顶点表示课程，弧表示课程之间的先修关系，对任意两门课程i和j，如果i是j的先修课，则在顶点i和顶点j之间画一条弧，按题中条件建立有向图。依题意，该问题的求解便成了求有向图的拓扑有序序列。在算法中，在邻接表的表头结点中加入了存放顶点入度的域indegree，每个顶点的入度域初始值均为0，随着弧的输入动态地累计得到各顶点的入度。在拓扑排序的过程中，和6.6节中介绍的方法不同，没有为堆栈专门开辟空间，而是利用表头结点数组中入度为0的顶点的indegree域进行链接形成链栈。,【模块划分】整个算法分三个模块建立有向图的邻接表CreateAdjList;以邻接表作存储结构实现拓扑排序TopSort；主函数main()，功能是建立邻接表的表头数组，调用CreateAdjList函数形成有向图的邻接表，调用TopSort函数求得学习计划。,【源程序】#include#defineMaxSize50typedefintVertexType;/*为简单起见，顶点信息设为顶点序号*/typedefstructArcNodeintadjvex;/*邻接点序号*/structArcNode*nextarc;ArcNode;/*边结点*/typedefstructVertexNodeVertexTypedata;intindegree;/*入度*/ArcNode*firstarc;VertexNode;/*表头结点*/typedefstructVertexNodevertexMaxSize;intvexnum,arcnum;AdjList;/*图的邻接表*/,voidCrea