数据结构第七章图(2016).ppt

第七章图,图的概念,图的存储,图的遍历,生成树和最小生成树,最短路径,7.1图的概念,1、图的定义：记为G(V,E)其中：V是G的顶点集合，是有穷非空集；E是G的边集合，是有穷集。,问：当E(G)为空时，图G存在否？答：存在！但此时图G只有顶点而没有边。,有向图：无向图：完全图：,图G中的每条边(有向边)都是有方向的；图G中的每条边(无向边)都是无方向的；图G任意两个顶点都有一条边相连接；,若n个顶点的无向图有n(n-1)/2条边,称为无向完全图若n个顶点的有向图有n(n-1)条边,称为有向完全图,V为顶点(vertex)E为边(edge),7.1图的概念,例：判断下列4种图形各属什么类型？,无向完全图,无向图(树),有向图,有向完全图,G1的顶点集合为V(G1)=0,1,2,3边集合为E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)G3的顶点集合为V(G3)=0,1,2弧的集合为E(G3)=,表示顶点0到顶点1的一条弧。（有序对）,7.1图的概念,3、图的基本术语,1）简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现。,数据结构中讨论的都是简单图。,2）邻接、关联无向图中，对于任意两个顶点vi和顶点vj，若存在边(vi，vj)，则称顶点vi和顶点vj互为邻接点，同时称边(vi，vj)关联于顶点vi和顶点vj。有向图中，对于任意两个顶点vi和顶点vj，若存在弧，则称顶点vi邻接到顶点vj，顶点vj邻接于顶点vi，同时称弧关联于顶点vi和顶点vj。,V1的邻接点：V2、V4V2的邻接点：V1、V3、V5,弧头和弧尾：有向边称为弧，边的起点u叫弧尾，终点v叫弧头。,7.1图的概念,）顶点的度：在无向图中，顶点v的度是指关联于该顶点的边数，通常记为D(v)。如：V3的度为：3；V4的度为2,在具有n个顶点、e条边的无向图G中，各顶点的度之和与边数之和的关系？,握手定理,7.1图的概念,在具有n个顶点、e条边的有向图G中，各顶点的入度之和与各顶点的出度之和的关系？与边数之和的关系？,顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID(v)；顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD(v)。顶点的度：有向图中，入度与出度之和。如：v1的入度为1，出度为2，度为3。,7.1图的概念,设有两个图G(V,E)和G(V,E)。若VV且EE,且E中的边所关联的顶点均在V中，则称图G是图G的子图。,）子图：,7.1图的概念,）路径：在无向图G=(V,E)中，从顶点vp到顶点vq之间的路径是一个顶点序列(vp=vi0,vi1,vi2,vim=vq)，其中，(vij-1,vij)E（1jm）。若G是有向图，则路径也是有方向的，顶点序列满足E。,一般情况下，图中的路径不唯一。,V1到V4的路径：V1V4V1V2V3V4V1V2V5V3V4,路径长度：该路径上边的数目。,7.1图的概念,回路（环）：第一个顶点和最后一个顶点相同的路径。简单路径：序列中顶点不重复出现的路径。简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。,7.1图的概念,）连通图：在无向图中，如果从一个顶点vi到另一个顶点vj(ij)有路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。连通分量：无向图的极大连通子图称为连通分量。,如何求得一个无向图的极大连通分量?,任何连通图的连通分量只有一个，就是它本身,7.1图的概念,V1,V2,V3,V4,V5,V6,V7,非连通的无向图有多个连通分量，且是对无向图的一种划分。,V1,V2,强连通图：在有向图中，对图中任意一对顶点vi和vj(ij)，若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称该有向图是强连通图。强连通分量：非强连通图的极大强连通子图。,如何求得一个非连通图的极大强连通分量?,强连通分量是对有向图的一种划分。,7.1图的概念,）网络：每条边上都带权的图，也称网图。,有向网,无向网,7.2图的存储,邻接矩阵表示法,表示顶点之间相邻关系的矩阵。用一维数组存储顶点信息，二维数组表示图中各个顶点之间的邻接关系。,#definen6/*顶点数*/#definee8/*边数*/typedefcharvextype;typedeffloatadjtype;typedefstructvextypevexsn;adjtypearcsnn;graph;,7.2.1邻接矩阵表示法,无向图的邻接矩阵特点？,无向图的邻接矩阵,主对角线为0且一定是对称矩阵。,7.2.1邻接矩阵表示法,如何求顶点i的度？,无向图的邻接矩阵,V1,V3,V4,V2,邻接矩阵的第i行（或第i列）中非零元素的个数。特别：完全图的邻接矩阵中，对角元素为0，其余全1。,7.2.1邻接矩阵表示法,如何判断顶点i和j之间是否存在边？,无向图的邻接矩阵,V1,V3,V4,V2,测试邻接矩阵中相应位置的元素arcsij是否为1。,7.2.1邻接矩阵表示法,如何求顶点i的所有邻接点？,无向图的邻接矩阵,V1,V3,V4,V2,将数组中第i行元素扫描一遍，若arcsij为1，则顶点j为顶点i的邻接点。,7.2.1邻接矩阵表示法,有向图的邻接矩阵,有向图的邻接矩阵一定不对称吗？,不一定，例如有向完全图。,7.2.1邻接矩阵表示法,有向图的邻接矩阵,如何求顶点i的出度？,邻接矩阵的第i行非零元素个数。,7.2.1邻接矩阵表示法,有向图的邻接矩阵,如何求顶点i的入度？,邻接矩阵的第i列非零元素个数。,7.2.1邻接矩阵表示法,有向图的邻接矩阵,如何判断从顶点i到顶点j是否存在边？,测试邻接矩阵中相应位置的元素arcsij是否为1。,7.2.1邻接矩阵表示法,网(有权图)的邻接矩阵(以有向网为例),网的邻接矩阵可定义为：,建立无向网络的邻接矩阵算法：VoidCREATGRAPH(graph*ga)inti,j,k;floatw;for(i=0;ivexsi=getchar();for(i=0;iarcsij=0;for(k=0;karcsij=w;ga-arcsji=w;,建立无向网络邻接矩阵步骤：（1）读入n个顶点信息，建立顶点表；（2）邻接矩阵初始化，即arcsij=0;（3）读入e条边，修改相应的arcsij的值。注意：无向图：修改arcsij，同时修改相应的arcsji;有向图：只需要修改arcsij。,7.2.1邻接矩阵表示法,容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。对稀疏图而言尤其浪费空间。,邻接矩阵法优点：,邻接矩阵法缺点：,小结：,改进方法：利用邻接表来表示。,7.2.2邻接表表示法,对每个顶点Vi建立一个单链表，把与Vi相邻接的所有顶点Vj链接起来，构成顶点Vi的邻接表。,边表结点,顶点表结点,邻接点域：表示vi一个邻接点的位置,链域：指向vi下一个边或弧的结点,顶点域：存放顶点vi的信息,边表头指针：指向单链表的第一个结点,所有顶点表头结点用顺序存储结构存储。,例1：无向图的邻接表,邻接表,例2：有向图的邻接表,邻接表(出边),逆邻接表(入边),注：邻接表不唯一，因各个边结点的链入顺序是任意的。,思考:如何求结点的度?,思考:如何求结点的度、出度和入度?,分析1:对于n个顶点e条边的无向图，邻接表中除了n个头结点外，只有2e个表结点,空间效率为O(n+2e)。若是稀疏图(enext=gai.link;边表结点s插入vi的边表头部：gai.link=s;由于是无向图，则重复，将另一边表结点插入Vj的边表头部。,voidCREATADJLIST(vexnodega,intn,inte)inti,j,k;edgenode*s;for(i=0;inext=gai.link;gai.link=s;,s=malloc(sizeof(edgenode);s-adjvex=i;s-next=gaj.link;gaj.link=s;,7.2图的存储,O（n2）,O（n+e）,7.3图的遍历,一、深度优先搜索二、广度优先搜索,遍历定义：从某一顶点出发，沿某条搜索路径对图中所有顶点访问且仅访问一次。遍历实质：找每个顶点的邻接点的过程。图的特点：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。怎样避免重复访问？解决思路：可设置一个辅助数组visitedn，用来标记每个被访问过的顶点。它的初始状态为0，在图的遍历过程中，一旦某一个顶点i被访问，就立即改visitedi为1，防止它被多次访问。,图常用的遍历：,7.3.1连通图的深度优先搜索遍历,实例：,基本思想：类似与树的先序遍历,v1,DFS结果,v2,v4,v8,v5,v3,v6,v7,起点,深度优先搜索基本思想：,访问顶点v,并将其标记为已访问过；从v的未被访问的邻接点中选取一个顶点w，再从w出发进行深度优先遍历；若无w则沿途返回上一个结点再找!重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。,递归,7.3.1连通图的深度优先搜索遍历,邻接矩阵,DFS结果:V0V1V4V2V5V3,邻接矩阵中图的基本操作深度优先遍历,intvisitedn;graph*g;voidDFS(inti)intj;printf(“%c”,g-vexsi);visitedi=1;/*已访问该顶点*/for(j=0;jarcsij=1,7.3.1连通图的深度优先搜索遍历,DFS结果:V0V3V2V5V4V1,邻接表,邻接表中图的基本操作深度优先遍历,vexnodegln;voidDFSL(inti)edgenode*p;printf(“%c”,gli.vertex);visitedi=1;/*已访问该顶点*/p=gli.link;while(p!=NULL)if(visitedp-adjvex=0)DFSL(p-adjvex);p=p-next;,7.3.1连通图的深度优先搜索遍历,DFS算法效率分析:,（设图中有n个顶点，e条边）如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历全部顶点所需的时间为O(n2)。如果用邻接表来表示图，只需扫描e条边即可完成遍历，加上访问n个头结点的时间，因此遍历图的时间复杂度为O(n+e)。,结论：稠密图适于在邻接矩阵上进行深度遍历；稀疏图适于在邻接表上进行深度遍历。,7.3.2连通图的广度优先搜索遍历,基本思想：类似与树的层次遍历,v1,BFS结果,实例,起点,广度优先搜索基本思想：,1)在访问了起始点v之后,并将其标记为已访问过；2)依次访问v的所有未被访问过的邻接点,并进行标记；3)然后再依次访问这些顶点中未被访问过的邻接点；4)直到所有顶点都被访问过为止。,思考:先访问过的结点其邻接点也先被访问,可采用何种辅助存储空间?,7.3.2连通图的广度优先搜索遍历,邻接矩阵,BFS结果:V0V1V2V3V4V5,邻接矩阵中图的基本操作广度优先遍历,intvisitedn;graph*g;voidBFS(intk)inti,j;sequeue*Q;SETNULL(Q);printf(“%c”,g-vexsk);visitedk=1;ENQUEUE(Q,k)/*被访问顶点入队*/,while(!EMPTY(Q)i=DEQUEUE(Q);/*将队头元素出队*/for(j=0;jarcsij=1,7.3.2连通图的广度优先搜索遍历,BFS结果:V0V3V2V1V5V4,邻接表,邻接表中图的基本操作广度优先遍历,vexnodegln;voidBFSL(intk)inti;edgenode*p;visitedk=1;/*已访问该顶点*/ENQUEUE(Q,k);/*被访问顶点入队*/,while(!EMPTY(Q)i=DEQUEUE(Q);printf(“%c”,gli.vertex);p=gli.link;/*找Vi的第一个邻接点*/while(p!=NULL)if(visitedp-adjvex=0)visitedp-adjvex=1;ENQUE(Q,p-adjvex);p=p-next;,7.3.2连通图的广度优先搜索遍历,BFS算法效率分析:,DFS与BFS之比较：空间复杂度相同，都是O(n)(借用了堆栈或队列）；时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。,如果使用邻接表来表示图，则BFSL外循环次数为n次，内循环次数取决于各个顶点的边表结点个数，时间复杂度为O(n+e)。如果使用邻接矩阵，则BFSL外循环次数为n次，而内循环对于每一个被访问到的顶点，都要检测矩阵中的整整一行（n个元素），时间复杂度为O(n2)。,（设图中有n个顶点，e条边）,7.3.3非连通图的遍历,分析:从每个连通分量中选一结点作为出发点,可访问到该连通分量中的所有顶点,通过多次调用DFS或BFS,即可访问到非连通图中的所有顶点.,DFS结果:V0V1V3V4V2V5V6V7,BFS结果:V0V1V2V3V4V5V6V7,intvisitedn;graphg;voidTRAVER()inti;for(i=0;in;i+)visitedi=0;/*标志数组初始化*/for(i=0;in;i+)if(visitedi=0)DFS(i);/*从顶点i出发遍历某一个连通分量*/ptintf(“compendn”);,邻接矩阵中非连通图的深度优先遍历,7.4生成树和最小生成树,一、生成树,生成树：是一个极小连通子图，它含有图中全部顶点，但只有n-1条边。生成森林：由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。,思考1：对连通图进行遍历，得到的是什么？得到的将是一个极小连通子图，即图的生成树！由深度优先搜索得到的生成树，称为深度优先搜索生成树。由广度优先搜索得到的生成树，称为广度优先搜索生成树。思考2：对非连通图进行遍历，得到的是什么？得到的将是各连通分量的生成树，即图的生成森林！,7.4生成树和最小生成树,例：画出下图的生成树,DFS生成树,邻接表,v0,v2,v1,v4,v3,BFS生成树,v0,无向连通图,起点,7.4生成树和最小生成树,首先明确：使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，n个顶点的连通网络的生成树有n个顶点、n-1条边。,即带权图,目标：最小生成树:在网络的多个生成树中，寻找一个各边权值之和最小的生成树。,需解决的问题尽可能选取权值小的边,但不能构成回路；必须使用且仅使用n-1条边来联结网络中的n个顶点。,二、最小生成树,7.4生成树和最小生成树,欲在n个城市间建立通信网，则n个城市应铺n-1条线路；但因为每条线路都会有对应的经济成本，而n个城市可能有n(n-1)/2条线路，那么，如何选择n1条线路，使总费用最少？,典型用途：,数学模型：顶点表示城市，有n个；边表示线路，有n1条；边的权值表示线路的经济代价；连通网表示n个城市间通信网。,显然此连通网是一个生成树！,问题抽象：n个顶点的生成树很多，需要从中选一棵代价最小的生成树，即该树各边的代价之和最小。此树便称为最小生成树MST(MinimumcostSpanningTree),7.4生成树和最小生成树,最小生成树的MST性质如下：,假设G=(V,E)是一个连通网络，若U是顶点集V的一个非空子集，若(u,v)是一条图G中权值最小的边，其中uU，vV-U；则：必存在一棵最小生成树包含边(u,v)。,利用MST性质构造最小生成树的两种常用算法：,Prim（普里姆）算法Kruskal（克鲁斯卡尔）算法,Prime算法特点:将顶点归并，一次增加一个顶点一条边。Kruskal算法特点：将边归并，一次增加一条边。,（1）从V中任选一顶点u0，并置T为只含一个顶点的树：即初始状态：U=u0,TE=；（2）只要UV,就找出一条权值最小的边(u,v),且uU,vV-U,将该条边(u,v)和不在T中的顶点v加入T中。即：while(UV)(u,v)=minwuv,uU,vV-U;U=U+v;TE=TE+(u,v)（3）直到把所有顶点加入T为止。,设：G=（V,E）是个连通网，且V=1,2,n并设所求的最小生成树为T=(U,TE)。其中：U为最小生成树的顶点集，TE为最小生成树的边集。,1普利姆（Prim）算法,构造步骤:,7.4生成树和最小生成树,注：连通网的最小生成树不是惟一的，但最小生成树的总代价一定相同（最小）。(当有两条具有同样的最小权值的边可供选择时，选哪一条都可以)。,1,1,2,3,4,5,7.4生成树和最小生成树,讨论:计算机内怎样实现Prim（普里姆）算法？,Prime算法特点:将顶点归并，一次增加一个顶点一条边。采用邻接矩阵作为图的存储表示。,存储结构：typedefstructintfromvex,endvex;/*要存储边的起点和终点*/floatlength;edge;floatdistnn;/*连通网络的带权邻接矩阵*/edgeTn-1;/*生成树的边集*/,实例：,起点,注：用表示不存在边的权值。,分析:6个顶点5条边,即T0T4.(1)初始:设u0=1,此时,T中存储的都是候选边。（for循环实现）(2)依次选n-1条边加入T中即：for(k=0;kn-1;k+)(3)选取最短边，即依次比较TkTn-2中侯选边的权值，并记录最短边位置，假设为Tm。(4)将选到的最短边加入T中，由于规定T0Tk-1存放生成树T中边，则只需互换Tm和Tk位置即可。(5)调整侯选边，只需用现在T中的边与顶点m相关联的边比较，确定最小值即可。(6)重复(3)(5)，选下一条最短边。,7.4生成树和最小生成树,voidPrim()intk,j,m,v,min,max=10000;floatd;edgee;/*临时变量，存放最短边*/for(j=1;jn;j+)/*初始化*/Tj-1.fromvex=1;Tj-1.endvex=j+1;/*不考虑自己到自己的边*/Tj-1.length=dist0j;,for(k=0;kn-1;k+)/*找n-1条边*/min=max;for(j=k;jn-1;j+)/*找最短边*/if(Tj.lengthmin)min=Tj.length;m=j;e=Tm;Tm=Tk;Tk=e;/*交换*/v=Tk.endvex;for(j=k+1;jn-1;j+)/*调整候选边*/d=distv-1Tj.endvex-1;if(d2:101-4:301-4-3:501-4-3-5:60,7.5最短路径,将有向网络G=(V,E)中所有顶点分成两个集合:S和T。S集合：以u为源点已确定了最短路径的终点集；初态：S=uT集合：尚未确定最短路径的顶点集；初态：T=V-u,按各顶点与u间最短