71图的结构定义和术语课件

第七章第七章 图图7.17.1图的结构定义和术语图的结构定义和术语7.27.2图的存储结构图的存储结构 7.2.1 7.2.1 数组表示法数组表示法 7.2.2 7.2.2 邻接表邻接表 7.2.3 7.2.3 邻接多重表邻接多重表 7.37.3图的遍历图的遍历 7.3.1 7.3.1 深度优先搜索深度优先搜索 7.3.2 7.3.2 广度优先搜索广度优先搜索7.47.4图的连通性问题图的连通性问题 7.4.1 7.4.1 无向图的连通分量和生成树无向图的连通分量和生成树 7.4.27.4.2最小生成树最小生成树7.57.5有向无环图及其应用有向无环图及其应用 7.5.1 7.5.1 拓扑排序拓扑排序 7.5.2 7.5.2 关键路径关键路径7.6 7.6 最短路径最短路径第第7 7章章 图图 一、教学内容：一、教学内容：1、图的基本概念2、图的存储结构（邻接矩阵、邻接表及有向图十字邻接表）；3、图的遍历（深度优先搜索、广度优先搜索）；4、最小生成树（kruskul算法、prim算法）；5、最短路径（dijkstra算法、floyd算法）;6、AOV网络与拓扑排序；7、AOE网络与关键路径。第第7 7章章 图图 二、教学要求：二、教学要求：1、理解图的基本概念，熟悉图的各种存储结构及其构造算法；2、熟练掌握图的两种搜索路径的遍历；3、掌握构造最小生成树的方法，并理解算法；4、理解用Dijkstra方法求解单源最短路径问题；5、掌握求活动网络的拓扑排序的方法，并理解算法；6、掌握求解关键路径的方法。引言:图（Graph）是一种较线性表和树更为复杂的数据结构。线性表:树:图形结构中，结点之间图形结构中，结点之间 的关系可以是任意的，任意的关系可以是任意的，任意两个数据元素之间都可能相关。两个数据元素之间都可能相关。应用广泛:如电路网络分析、交通运输、管理与线路的铺设、印刷电路板与集成电路的布线等众多直接与图有关的问题，它们必须用图的有关方法进行处理；另外像工作的分配、工程进度的安排、课程表的制订、关系数据库的设计等许多实际问题，如果间接地用图来表示，处理起来比较方便。这些技术领域都是把图作为解决问题的主要数学手段来使用，因此，如何在计算机中表示和处理图结构，就是计算机科学需研究的一项重要课题。一、一、图的结构定义图的结构定义:1 1、图图是由一个是由一个顶点集顶点集 V V 和一个和一个顶点间的关系集合顶点间的关系集合弧集弧集 R R（边的集合）边的集合）构成的数据结构。构成的数据结构。可以用二元组定义为：可以用二元组定义为：Graph=(V,R)Graph=(V,R)其中，其中，VRVR|v,wV|v,wV 且且 P(v,w)P(v,w)谓词谓词 P(v,w)P(v,w)定义了弧定义了弧 的意义或信息。的意义或信息。顶点顶点:图中的数据元素称为顶点图中的数据元素称为顶点(Vertex),VVertex),V是顶点的有穷是顶点的有穷非空集合非空集合;VR VR是两个顶点之间的关系的集合。是两个顶点之间的关系的集合。若若 VR.VR.则则 表示从表示从v v到到w w的一条弧（的一条弧（Arc),Arc),且且称称v v为弧尾为弧尾(Tail)(Tail)或为初始点或为初始点(Initial node)(Initial node)，称，称w w为弧头为弧头(Head)(Head)或为终端点（或为终端点（Terminal node).Terminal node).7.1 7.1 图的定义和术语图的定义和术语由于由于“弧弧”是有方向的，因此称由顶点集和弧集构成的图为是有方向的，因此称由顶点集和弧集构成的图为有向有向图图。用尖括号表示。用尖括号表示。A A B B E E C C D D 例如例如:G1=(V1,VR1)其中V1=A,B,C,D,EVR1=,若若 VR VR必有必有 VR,VR,则以则以(v,wv,w)代替，代替，表示两顶点之间有边。此时的图为无向图表示两顶点之间有边。此时的图为无向图（UndigraphUndigraph)。例：例：无无向图向图 G2G2A AB BC CD DE E其中V2=A,B,C,D,EVR2=（A,B）,（A,C),(E,C),(E,D),(D,B)完完 全全 图：有图：有 n(n-1)/2 n(n-1)/2 条边的无向图。其中条边的无向图。其中 n n 是结点个数。是结点个数。有向完全图：有有向完全图：有 n(n-1)n(n-1)条边的有向图。其中条边的有向图。其中 n n 是是结点个数。结点个数。稀疏图：稀疏图：稠密图：稠密图：邻接点：邻接点：对于无向图，对于无向图，则，则 v v 、v v互为邻接点互为邻接点、图的基本术语、图的基本术语v vv v无向图结点的度无向图结点的度：和结点：和结点v v相关联的边的数目。相关联的边的数目。TD(vTD(v)有向图结点的出度和入度有向图结点的出度和入度TD(vTD(v)=)=ID(v)+OD(vID(v)+OD(v)证明：证明：e=1/2e=1/2A AB BC CD DE EH HM M有向图有向图G2G2A AB BC CD D无向图无向图G1 G1 2 2、无无向图的连通性向图的连通性A AB BC CD DE E路径：在无向图路径：在无向图G=(V,E)G=(V,E)中由顶点中由顶点v v至至v v 的顶点序列。的顶点序列。回路或环：第一个顶点和最后一个顶点相同的路径。回路或环：第一个顶点和最后一个顶点相同的路径。简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。复出现的回路。连通：顶点连通：顶点v v至至v v 之间有之间有路径路径存在存在连通图：连通图：若图若图G G中任意两个顶点之间都有路径相通，则称此图为连通图中任意两个顶点之间都有路径相通，则称此图为连通图;连通分量：连通分量：极大极大连通子图连通子图F FG GI IJ JL LH HM MK KA AB BC CD DE EH HM MF FG GI IJ JL LK K无向图无向图G G无向图无向图G G的三个连通分量的三个连通分量3 3、有向图的连通性、有向图的连通性路径：在有向图路径：在有向图G=(V,E)G=(V,E)中由顶点中由顶点v v经有向边至经有向边至v v 的顶点序列。的顶点序列。回路或环：第一个顶点和最后一个顶点相同的路径。回路或环：第一个顶点和最后一个顶点相同的路径。简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。的回路。连通：顶点连通：顶点v v至至v v 之间有路径存在之间有路径存在强连通图：有向图图强连通图：有向图图 G G 的任意两点之间都是连通的，则称的任意两点之间都是连通的，则称 G G 是强连通图。是强连通图。强连通分量：极大连通子图强连通分量：极大连通子图有向图有向图G G有向图有向图G G的两个强连通分量的两个强连通分量A AB BC CD DA AB BC CD D生成树：极小连通子图。包含图的所有生成树：极小连通子图。包含图的所有 n n 个结点，但个结点，但只含图的只含图的 n-1 n-1 条边。在生成树中添加一条边之后，必定条边。在生成树中添加一条边之后，必定会形成回路或环。会形成回路或环。生成森林：生成森林：对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林生成森林。A AB BC CD DE EH HM MA AB BC CD DE EH HM M无向图无向图G G 无向图无向图G G的生成树的生成树 权 在图的边或弧中给出相关的数，称为权。权可以代表一个顶点到另一个顶点的距离，耗费等，带权图一般称为网。带权图的示例具体见图7-3。结构的建立和销毁结构的建立和销毁插入或删除顶点插入或删除顶点对邻接点的操作对邻接点的操作对顶点的访问操作对顶点的访问操作遍历遍历插入和删除弧插入和删除弧 基本操作基本操作CreatGraph(&GCreatGraph(&G,V,VR):,V,VR):/按定义(V,VR)构造图DestroyGraph(&GDestroyGraph(&G):):/销毁图结构的建立和销毁结构的建立和销毁 LocateVex(G,u);/若G中存在顶点u，则返回该顶点在/图中“位置位置”；否则返回其它信息。GetVex(G,v);/返回v的值。PutVex(&G,v,value);/对v赋值value。对顶点的访问操作对顶点的访问操作FirstAdjVex(G,v);/返回v的“第一个邻接点第一个邻接点”。若该顶点/在G中没有邻接点，则返回“空”。NextAdjVex(G,v,w);/返回v的（相对于w的）“下一个邻下一个邻接接/点点”。若w是v的最后一个邻接点，则/返回“空”。对邻接点的操作对邻接点的操作InsertVex(&G,v);/在图G中增添新顶点v。DeleteVex(&G,v);/删除G中顶点v及其相关的弧。插入或删除顶点插入或删除顶点InsertArc(&G,v,w);/在G中增添弧DeleteArc(&G,v,w);/在G中删除弧插入和删除弧插入和删除弧DFSTraverse(G,v,Visit();/从顶点v起深度优先深度优先遍历图G，并对每/个顶点调用函数Visit一次且仅一次。BFSTraverse(G,v,Visit();/从顶点v起广度优先广度优先遍历图G，并对每/个顶点调用函数Visit一次且仅一次。遍遍 历历一、一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示三、有向图的十字链表存储表示四、无向图的邻接多重表存储表示7.2 7.2 图的存储表示图的存储表示Aij=0(i,j)VR1(i,j)VR定义定义:矩阵的元素为矩阵的元素为一、一、图的数组(邻接矩阵)存储表示注意注意:Ai,iAi,i =0;=0;规定自身无边。规定自身无边。ABCD表示成右图矩阵表示成右图矩阵0 1 1 00 0 0 00 0 0 11 0 0 0有向图的邻接矩阵有向图的邻接矩阵求顶点的度：判断两点是否有边分析特点例例:（1）矩阵不一定是对称的;（2）第i 行中1的个数为顶点i 的出度;（3）第i列中1的个数为顶点 i的入度;（4）矩阵中1的个数为图中弧的数目;（5）很容易判断顶点i 和顶点j 是否有弧相连.从有向图的邻接矩阵可以得出如下结论从有向图的邻接矩阵可以得出如下结论无权值的无向图的邻接矩阵无权值的无向图的邻接矩阵 求顶点的度：求顶点的度：判断两点是否有边判断两点是否有边 分析特点分析特点例例:表示成右图矩阵表示成右图矩阵0 1 1 0 01 0 0 1 11 0 0 0 10 1 0 0 10 1 1 1 0ABCDE从无向图的邻接矩阵可以得出如下结论从无向图的邻接矩阵可以得出如下结论（1）矩阵是对称的，可压缩存储（上（下）三角;（2）第i行或第i 列中1的个数为顶点i 的度;（3）矩阵中1的个数的一半为图中边的数目;（4）很容易判断顶点i 和顶点j之间是否有边相连(看矩阵中i行j列值是否为1)。网的邻接矩阵表示类似地可以定义网的邻接矩阵为：wij若（i,j）E(G)或i,jE(G)Aij=其它情形网及网的邻接矩阵见图8-10。容易实现图的操作，如：求某顶点的度、判断顶点之间是否容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。仅耗费有边（弧）、找顶点的邻接点等等。仅耗费 O(1)O(1)时间。时间。n n个顶点需要个顶点需要n*nn*n个单元存储边个单元存储边(弧弧););空间效率为空间效率为O(nO(n2 2)。对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。邻接矩阵法邻接矩阵法优点：优点：邻接矩阵法邻接矩阵法缺点：缺点：邻接矩阵的结构定义：#defineMAX_VERTEX_NUM20TypedefenumDG,DN,AG,ANGraphkind;typedef structArcCell /弧的定义弧的定义VRTypeadj;/VRType是顶点关系类型。/对无权图，用1或0表示相邻否；/对带权图，则为权值类型。InfoType*info;/该弧相关信息的指针 ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct /图的定义图的定义VertexType/顶点信息vexsMAX_VERTEX_NUM;AdjMatrixarcs;/弧的信息 intvexnum,arcnum;/顶点数，弧数GraphKindkind;/图的种类标志MGraph;P162算法7.17.2另外另外:图的邻接矩阵数据类型描述可为图的邻接矩阵数据类型描述可为:图的邻接矩阵数据类型描述如下:#defineMAX100/*最大顶点数*/elemtypeVMAX;/*存放顶点信息,若顶点除编号外无其它信息，则无需数组*/intAMAXMAX/*邻接矩阵*/邻接矩阵的生成程序#define INFINITE 9999 /void creatadj(int n,int e,int t)/*n为顶点数,e为边数,t为14,分别表示无向图、有向图、带权无向图、带权有向图*/int i,j,k,w;for(i=1;i=n;i+)printf(“输入第输入第%d顶点信息顶点信息”,i);vi=getchar();for(i=1;i=n;i+)for(i=1;i=n;i+)for(j=1;j=n;j+)for(j=1;j2)Aij=INFINITE;if(t2)Aij=INFINITE;/赋初值赋初值 else else Aij=0;Aij=0;for(k=1;kn|jn)exit(0);if(t2)scanf(“%d”,&w);Aij=w;if(t=3)Aji=w;elseelse Aij=1;Aij=1;if(tif(t=1)=1)AjiAji=1;=1;7.2.2 邻接表邻接表1 图的邻接表表示图的邻接表表示 图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法，它包括两部分：一部分是单链表，用来存放边的信息；另一部分是数组，主要用来存放顶点本身的数据信息。表结点表结点头结点头结点adjvexnextarcinfodatafirstarc指示与顶点Vi邻接的点在图中的位置指示下一条边或弧的结点信息可无存储顶点Vi的名或其他信息指示链表中第一个结点例如，图7-8所示的无向图G3和有向图G4的邻接表见图8-11所示求顶点的度：判断两点是否有边判断图的边数分析特点求顶点的度：判断两点是否有边判断图的边数分析特点2从无向图的邻接表可以得到如下结论（1）第i个链表中结点数目为顶点i的度；（2）所有链表中结点数目的一半为图中边数；（3）占用的存储单元数目为n+2e。3 从有向图的邻接表可以得到如下结论从有向图的邻接表可以得到如下结论（1）第i个链表中结点数目为顶点i的出度；（2）所有链表中结点数目为图中弧数；（3）占用的存储单元数目为n+e。从有向图的邻接表可知，不能求出顶点的入度。为此，我们必须另外建立有向图的逆邻接表，以便求出每一个顶点的入度。逆邻接表在上图中已经给出，从该图中可知。有向图的逆邻接表与邻接表类似，只是它是从入度考虑结点，而不是从出度考虑结点。例例3 3：已知某网的邻接（出边）表，请画出该网络。已知某网的邻接（出边）表，请画出该网络。8064125当邻接表当邻接表的存储结的存储结构形成后，构形成后，图便唯一图便唯一确定！确定！邻接表的邻接表的缺点：缺点：邻接表的邻接表的优点：优点：空间效率高；空间效率高；容易寻找顶点的邻接点；容易寻找顶点的邻接点；判断任意两顶点间是否有边或弧，需搜判断任意两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵索两结点对应的单链表，没有邻接矩阵方便。方便。4 图的邻接表数据类型描述图的邻接表数据类型描述图的邻接表数据类型描述如下：#defineMAXN50/*MAXN表示图中最大顶点数*/typedefstructarcnode/定义边结点的结构intadjvex;/该弧所指向的顶点的位置 1intweight;structarcnode*nextarc;/指向下一条弧的指针InfoType*info;arcnode;typedefstructvnode/定义邻接表的表头类型intvertex;/顶点信息arcnode*firstarc;/指向第一条依附该顶点的弧vnode;AdjlistMAXN;5.邻接表的生成程序邻接表的生成程序voidcreat_adj_list(vnodehead,intt,intn)intn,i,w=1,v=1;arcnode*p;for(i=1;i=0)&(w0)scanf(“%d%d”,&v,&w);/边if(vn)|(wn)continue;if(v0)&(w0)p=(arcnode*)malloc(sizeof(arcnode);p-adjvex=w;p-next=headv.firstarc;headv.firstarc=p;/头插法if(t=0)/逆邻接表p=(arcnode*)malloc(sizeof(arcnode);p-adjvex=v;p-next=headw.firstarc;headw.firstarc=p;另外，请注意上面的算法中，建立的邻接表不是唯一的,与你从键盘输入边的顺序有关，输入的边的顺序不同，则得到的链表也不同。讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？1.1.联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。链表中结点个数等于一行中非零元素的个数。2.2.区别：区别：对于任一确定的无向图，邻接矩阵是唯一的（行列对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。与顶点编号无关）。邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的空间复而邻接表的空间复杂度为杂度为O(n+e)O(n+e)。3.3.用途：用途：邻接矩阵多用于稠密图的存储（邻接矩阵多用于稠密图的存储（e e接近接近n(n-n(n-1)/2)1)/2)；而邻接表多用于稀疏图的存储（而邻接表多用于稀疏图的存储（enen2 2)0 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3BACDFE补例：图的邻接表存储表示补例：图的邻接表存储表示有向图的邻接表有向图的邻接表142301201234 A B C D EABECD可见，在有向图的邻接表中不易找到指向该顶点的弧ABECD有向图的逆邻接表有向图的逆邻接表A B C D E 303420 01234在有向图的逆邻接表中，对每个顶点，链接的是指向该顶点的弧弧的结点结构弧的结点结构弧尾顶点位置弧头顶点位置弧的相关信息指向下一个有相有相同弧尾同弧尾的结点指向下一个有有相同弧头相同弧头的结点typedef structArcBox/弧弧的结构表示的结构表示inttailvex,headvex;InfoType*info;structArcBox*hlink,*tlink;VexNode;三、有向图的十字链表存储表示三、有向图的十字链表存储表示tailvexheadvexhlinktlink顶点的结点结构顶点的结点结构顶点信息数据指向该顶点的第一条入弧第一条入弧指向该顶点的第一条出弧第一条出弧typedef structVexNode/顶点的结构表示顶点的结构表示VertexTypedata;ArcBox*firstin,*firstout;VexNode;datafirstinfirstout例bdacabcd123413123431434241typedef struct VexNodexlistMAX_VERTEX_NUM;/顶点结点(表头向量)intvexnum,arcnum;/有向图的当前顶点数和弧数OLGraph;有向图的结构表示有向图的结构表示(十字链表十字链表)typedef structEboxVisitIfmark;/访问标记 intivex,jvex;/该边依附的两个顶点的位置structEBox*ilink,*jlink;/分别指向依附这两个顶点的下一条边InfoType*info;/该边信息指针EBox;边的结构表示边的结构表示四、无向图的邻接多重表存储表示markivexilinkjvexjlinktypedef struct /邻接多重表邻接多重表 VexBoxadjmulistMAX_VERTEX_NUM;intvexnum,edgenum;AMLGraph;顶点的结构表示顶点的结构表示typedef structVexBoxVertexTypedata;EBox*firstedge;/指向第一条依附该顶点的边VexBox;无向图的结构表示无向图的结构表示datafirstedge例aecbd1234acdb5e121434323552以以157157页的无向图页的无向图G G2 2为例为例,自己练习自己练习分析分析:在图的链接存储在图的链接存储(邻接表、逆邻接表、十邻接表、逆邻接表、十字链表和邻接多重表字链表和邻接多重表)中，中，表头向量需要占用表头向量需要占用n个存储单元，个存储单元，所有边结点需要占用所有边结点需要占用2e或或e存储单元，存储单元，所以最多需要（所以最多需要（n+2e）个存储单元，个存储单元，稀疏图采用这种存储方式可节省存储空间。稀疏图采用这种存储方式可节省存储空间。7.3 图的遍历图的遍历从图中某个顶点出发遍历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。图的遍历有两种方法：深度优先搜索遍历（DFS）广度优先搜索遍历（BFS）。它们对无向图和有向图都适用。从图中某个顶点V0出发，访问此顶点，然后依次从依次从V0的各个未被访问的邻接的各个未被访问的邻接点出发深度优先搜索遍历图点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。深度优先搜索遍历类似于树的先序遍历。7.3.1深度优先搜索遍历深度优先搜索遍历1 深度优先搜索思想深度优先搜索思想假定给定图G的初态是所有顶点均未被访问过，在G中任选一个顶点i作为遍历的初始点，则深度优先搜索遍历可定义如下：(1)首先访问顶点i，并将其访问标记置为访问过，即visitedi=1；(2)然后搜索与顶点i有边相连的下一个顶点j，若j未被访问过，则访问它，并将j的访问标记置为访问过，visitedj=1，然后从j开始重复此过程，若j已访问，再看与i有边相连的其它顶点；(3)若与i有边相连的顶点都被访问过，则退回到前一个访问顶点并重复刚才过程，直到图中所有顶点都被访问完为止。例如，对图8-13所示无向图G7，从顶点1出发的深度优先搜索遍历序列可有多种，下面仅给出三种，其它可作类似分析。在无向图G7中，从顶点1出发的深度优先搜索遍历序列举三种为：1,2,4,8,5,6,3,71,2,5,8,4,7,3,61,3,6,8,7,4,2,5BooleanvisitedMAX;Status(*visitfunc)(int v);/visitfunc为指向函数的指针变量为指向函数的指针变量voidDFSTraverse(GraphG,Status(*Visit)(intv)/对图对图 G 作深度优先遍历。作深度优先遍历。VisitFunc=Visit;for(v=0;vG.vexnum;+v)visitedv=FALSE;/访问标志数组初始化for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);/对尚未访问的顶点调用DFSvoidDFS(GraphG,intv)/从顶点从顶点v出发，出发，深度优先搜索遍历连通图深度优先搜索遍历连通图 Gvisitedv=TRUE;VisitFunc(v);for(w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/对v的尚未访问的邻接顶点w/递归调用DFS/DFS2深度优先搜索若图是连通的或强连通的，则从图中某一个顶点出发可以访问到图中所有顶点，否则只能访问到一部分顶点。另外，从刚才写出的遍历结果可以看出，从某一个顶点出发的遍历结果是不唯一的。但是,若我们给定图的存贮结构,则从某一顶点出发的遍历结果应是唯一的。voiddfs(GraphG,vtx*v）/*从从v出发深度优先遍历图出发深度优先遍历图g*/visit（v）;visitedv=1;w=FIRSTADJ（G，v）;/w为为v的邻接点的邻接点while(w!=0)/当邻接点存在时当邻接点存在时if(!visitedw)dfs（G，w）;w=NEXTADJ（G，v，w）/找下一邻接点找下一邻接点(1)用邻接矩阵实现图的深度优先搜索以图8-13中无向图G7为例，来说明算法的实现，G7的邻接矩阵见图8-16。分析上述过程，在遍历图时，对图中每个顶点至分析上述过程，在遍历图时，对图中每个顶点至多调用一次多调用一次dfs过程，因为一旦某个过程，因为一旦某个顶点被标志顶点被标志成已被访问，就不再从它出发进行搜索。因此，成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个遍历图的过程实质上是对每个顶点查找其邻接点顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结的过程。其耗费的时间则取决于所采用的存储结构。构。邻接矩阵的深度优先搜索演示邻接矩阵的深度优先搜索演示算法描述为下面形式：voiddfs(inti)/从顶点i出发遍历intj;visit(i);/输出访问顶点visitedi=1;/全局数组访问标记置1表示已经访问for(j=1;jadjvex)dfs1(p-adjvex);p=p-next;而而当当以以邻邻接接表表作作图图的的存存储储结结构构时时，找找邻邻接接点点所所需需时时间间为为O（e），其其中中e为为无无向向图图中中边边的的数数或或有有向向图图中中弧弧的的数数。由由此此，当当以以邻邻接接表表作作存存储储结结构构时时，深深度度优优先先搜搜索索遍遍历历图图的的时间复时间复杂度为杂度为O（ne）。）。邻接表深度优先搜索演示邻接表深度优先搜索演示用刚才算法及图8-16，可以描述从顶点7出发的深度优先搜索遍历示意图，见图8-17,其中实线表示下一层递归，虚线表示递归返回，箭头旁边数字表示调用的步骤。于是，从顶点7出发的深度优先搜索遍历序列，从图8-17中可得出为7，3，1，2，4，8，5，6。从其它顶点出发的深度优先搜索序列，请读者自已写出。3非连通图的深度优先搜索若图是非连通的或非强连通图，则从图中某一个顶点出发。不能用深度优先搜索访问到图中所有顶点，而只能访问到一个连通子图（既连通分量）或只能访问到一个强连通子图（既强连通分量）。这时，可以在每个连通分量或每个强连通分量中都选一个顶点，进行深度优先搜索遍历，最后将每个连通分量或每个强连通分量的遍历结果合起来，则得到整个非连通图的遍历结果。遍历算法实现与连通图的只有一点不同，即对所有顶点进行循环，反复调用连通图的深度优先搜索遍历算法即可。具体实现如下：for(inti=1;i=n;i+)if(!visitedi)dfs(i);for(inti=1;i=n;i+)if(!visitedi)dfs1(i);或者从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它按这些顶点被访问的先后次序依次访问它们的邻接点们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。7.3.2 广度优先搜索遍历广度优先搜索遍历1 广度优先搜索的思想广度优先搜索的思想 广度优先搜索遍历类似于树的按层次遍历。设图G的初态是所有顶点均未访问，在G 中任选一顶点i作为初始点，则广度优先搜索的基本思想是：(1)首先访问顶点i，并将其访问标志置为已被访问，即visitedi=1；(2)接着依次访问与顶点i有边相连的所有顶点W1，W2，Wt；(3)然后再按顺序访问与W1，W2，Wt有边相连又未曾访问过的顶点；依此类推，直到图中所有顶点都被访问完为止。void BFSTraverse(GraphG,Status(*Visit)(intv)for(v=0;vG.vexnum;+v)visitedv=FALSE;/初始化访问标志InitQueue(Q);/置空的辅助队列Qfor(v=0;vG.vexnum;+v)if(!visitedv)/v尚未访问 visitedv=TRUE;Visit(v);/访问uEnQueue(Q,v);/v入队列while(!QueueEmpty(Q)DeQueue(Q,u);/队头元素出队并置为u for(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w)if(!visitedw)visitedw=TRUE;Visit(w);EnQueue(Q,w);/访问的顶点w入队列/if /while /if /BFSTraverse例如，对图8-13所示无向图G7，从顶点1出发的广度优先搜索遍历序列可有多种，下面仅给出三种，其它可作类似分析。在无向图G7中，从顶点1出发的广度优先搜索遍历序列举三种为：1,2,3,4,5,6,7,81,3,2,7,6,5,4,81,2,3,5,4,7,6,8 和深度优先搜索类似，在遍历的过程中也需要一和深度优先搜索类似，在遍历的过程中也需要一个访问标志数组。并且，为了顺次访个访问标志数组。并且，为了顺次访 问路径长度为问路径长度为2、3、的顶点，需附设队列以存储已被访问的路径长度的顶点，需附设队列以存储已被访问的路径长度为为1，2，的顶点。广的顶点。广 度优先遍历的算法如下所示。度优先遍历的算法如下所示。voidbfs(Graphg,vtx*v）visit(v);visitedv=1;INIQUEUE(Q);ENQUEUE(Q,v);while(!EMPTY(Q)DLQUEUE(Q,v);/队头元素出队队头元素出队w=FIRSTADJ(g,v);/求求v的邻接点的邻接点while(w!=0)if(!visitedw)visit(w);visitedw=1;ENQUEUE(Q,w);w=NEXTADJ(g,v,w);/求下一邻接点求下一邻接点/bfs(1)用邻接矩阵实现图的广度优先搜索遍历用邻接矩阵实现图的广度优先搜索遍历仍以图8-13中无向图G7及8-14所示的邻接矩阵来说明对无向图G7的遍历过程根据该算法用及图7-14中的邻接矩阵，可以得到图7-13的无向图G7的广度优先搜索序列，若从顶点1出发，广度优先搜索序列为：1，2，3，4，5，6，7，8。若从顶点3出发，广度优先搜索序列为：3，1，6，7，2，8，4，5,从其它点出发的广度优先搜索序列可根据同样类似方法分析。算法描述如下：voidbfs(inti)/从顶点i出发遍历intQn+1;/Q为队列intf,r,j;/f,r分别为队列头，尾指针f=r=0;/设置空队列visit(vi);/输出访问顶点visitedi=1;/全局数组标记置1表示已经访问r+;qr=i;/入队列while(fr)f+;i=qf;/出队列for(j=1;j=n;j+)if(Aij=1)&(!visitedj)visit(vj);visitedj=1;r+;qr=j;（2）用邻接表实现图的广序优先搜索遍历）用邻接表实现图的广序优先搜索遍历仍以无向图G7及图8-16所示邻接表来说明邻接表上实现广度优先搜索遍历的过程根据该算法及图8-16，可以得到图G7的广度优先搜索序列，若从顶点1出发，广度优先搜索序列为：1，2，3，4，5，6，7，8，若从顶点7出发，广度优先搜索序列为：7，3，8，1，6，4，5，2，从其它顶点出发的广度优先搜索序列可根据同样类似方法分析。算法描述如下：voidBFS1(inti)intqn+1;/定义队列intf,r;E_NODE*p;/P为搜索指针f=r=0;visit(headi);visitedi=1;r+;qr=i;/进队while(fadjvex)visit(headp-adjvex.vertex;visitedp-adjvex=1;r+;qr=p-adjvex;p=p-next;邻接表的广度优先搜索演示邻接表的广度优先搜索演示3.非连通图的广度优先搜索若图是非连通的或非强连通图，则从图中某一个顶点出发。不能用广度优先搜索遍历访问到图中所有顶点，而只能访问到一个连通子图（既连通分量）或只能访问到一个强连通子图（既强连通分量）。这时，可以在每个连通分量或每个强连通分量中都选一个顶点，进行广度优先搜索遍历，最后将每个连通分量或每个强连通分量的遍历结果合起来，则得到整个非连通图或非强连通图的广度优先搜索遍历序列。遍历算法实现与连通图的只有一点不同，即对所有顶点进行循环，反复调用连通图的广度优先搜索遍历算法即可。具体可以表示如下：for(inti=1;i=n;i+)for(inti=1;i=n;i+)if(!visitedi)或if(!visitedi)bfs(i);bfs1(i);分析上述过程，每个顶点至多进一次队列。遍历图的分析上述过程，每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻接过程实质上是通过边或弧找邻接 点的过程、因此广度优先点的过程、因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之不同之 处仅仅在于对顶点访问的顺序不同。处仅仅在于对顶点访问的顺序不同。7.4 图的连通性问题图的连通性问题7.4.1 无向图的连通分量和生成树无向图的连通分量和生成树若图是连通的或强连通的，则从图中某一个顶点出发可以访问到图中所有顶点；若图是非连通的或非强连通图，则需从图中多个顶点出发搜索访问而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为每个连通分量中的顶点集。如:下页DEABCFJLMGHIKDEGHIKABCFJLM深度优先搜索遍历算法及广度优先搜索遍历算法中遍历图过程中历经边的集合和顶点集合一起构成连通图的极小连通子图。它是连通图的一颗生成树。生生成成树树：是是一一个个极极小小连连通通子子图图，它它含含有有图图中中全全部部顶顶点点，但只有但只有n-1n-1条边。条边。由深度优先搜索遍历得到的生成树，称为深度优先生成树，由广度优先搜索遍历得到的生成树，称为广度优先生成树。图8-13中无向图G7的两种生成树见图8-19(下页)。例例1 1：画出下图的生成树：画出下图的生成树DFS生生成成树树v0v1v2v4v4v3邻接表0123413341420v4v3v2v1v0231420v0v2v1v4v3BFS生生成成树树v0v1v3v2v4无向连通图无向连通图2生成森林若一个图是非连通图或非强连通图，但有若干个连通分量或若干个强连通分量，则通过深度优先搜索遍历或广度优先搜索遍历，不可以得到生成树，但可以得到生成森林，且若非连通图有n个顶点，m个连通分量或强连通分量，则可以遍历得到m棵生成树，合起来为生成森林，森林中包含n-m条树边。生成森林可以利用非连通图的深度优先搜索遍历或非连通图的广度优先搜索遍历算法得到。3最小生成树在一般情况下，图中的每条边若给定了权，这时，我们所关心的不是生成树，而是生成树中边上权值之和。若生成树中每条边上权值之和达到最小，称为最小生成树最小生成树。DEABCFJLMGHIK例例2 2：画出下图的生成森林（或极小连通子图）：画出下图的生成森林（或极小连通子图）求解步骤：求解步骤：Step1:Step1:先求出邻接矩阵或邻接表；先求出邻接矩阵或邻接表；Step2:Step2:写出写出DFSDFS或或BFSBFS结果序列；结果序列；Step3:Step3:画出对应子图或生成森林。画出对应子图或生成森林。这是一个无向非连通图这是一个无向非连通图（参见教材（参见教材P170-171P170-171例）例）下面选用下面选用邻接表邻接表方式来求方式来求深度深度优先搜索生成森林优先搜索生成森林注：亦可由邻接矩阵或邻接表直接画出生成森林注：亦可由邻接矩阵或邻接表直接画出生成森林115 5M12L11K10J9I8H7G6F5E4D3C2B1A01201200437810661011126709121911112294710811DEGHIK子图子图1：再再写出写出DFS结果（结果（3次）次）ABMJLCFDEGHKIABCFJLM先写出邻接表（或邻接矩阵）：先写出邻接表（或邻接矩阵）：子图子图2：子图子图3：最小连最小连通！通！DEGHIK子图子图(或连通分量或连通分量)ABCFJLMABCFJLMDEGHIK生生成成森森林林2.2.求最小生成树求最小生成树首先明确：首先明确：使用不同的遍历图的方法，可以得到不同的生成树；从使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，按照生成树的定义，n n 个顶点的个顶点的连通网络连通网络的生成树有的生成树有 n n 个顶点、个顶点、n-n-1 1 条边。条边。即有权图即有权图目标：目标：在网络的多个生成树中，寻找一个在网络的多个生成树中，寻找一个各边权值之和最小各边权值之和最小的的生成树。生成树。构造最小生成树的准则构造最小生成树的准则v必须只使用该网络中的必须只使用该网络中的边边来构造最小生成树；来构造最小生成树；v必须使用且仅使用必须使用且仅使用n n-1-1条边条边来联结网络中的来联结网络中的n n个顶点；个顶点；v不能使用产生回路的边。不能使用产生回路的边。欲在欲在n n个城市间建立通信网，则个城市间建立通信网，则n n个城市应铺个城市应铺n-1n-1条线路；但条线路；但因为每条线路都会有对应的经济成本，而因为每条线路都会有对应的经济成本，而n n个城市可能有个城市可能有n(n-n(n-1)/2 1)/2 条线路，那么，条线路，那么，如何选择如何选择n1n1条线路，使总费用最少？条线路，使总费用最少？典型用途：典型用途：数学模型：数学模型：顶点顶点表示城市，有表示城市，有n n个；个；边边表示线路，有表示线路，有n1n1条；条；边的权值边的权值表示线路的经济代价；表示线路的经济代价；连通网连通网表示表示n n个城市间通信网。个城市间通信网。显然此连通网是显然此连通网是一个一个生成树！生成树！问题抽象：问题抽象：n个顶点的生成树很多，需要从中选一棵个顶点的生成树很多，需要从中选一棵代价最小代价最小的生成树，即该树的生成树，即该树各边的代价之和各边的代价之和最小。此树便称为最小生最小。此树便称为最小生成树成树MST(MinimumcostSpanningTree)MST MST 性质性质：假设假设 G=V,E G=V,E 是一个连通图，是一个连通图，U U 是结点是结点集合集合 V V 的一个非空子集。若的一个非空子集。若(u,v)u,v)是一条代价是一条代价最小的边，且最小的边，且 u u 属于属于 U,v U,v 属于属于 V-UV-U，则必存则必存在一棵包括边在一棵包括边 (u,v)u,v)在内的最小代价生成树。在内的最小代价生成树。证明：假定存在一棵不包括边证明：假定存在一棵不包括边 (u,v)u,v)在内的最小代价生成在内的最小代价生成树，设其为树，设其为 T T。将边将边(u,v)u,v)添加到树添加到树 T T，则形成一条包则形成一条包含含 (u,v)u,v)的回路。因此，必定存在另一条边的回路。因此，必定存在另一条边 (u u ，v v )，且且 u u 属于属于 U,v U,v 属于属于 V-UV-U。删去边删去边 (u u ，v v )，得到另一棵生成树得到另一棵生成树 T T ;因为边因为边(u,v)u,v)的代价小于边的代价小于边 (u u ，v v )的代价，所以新的代价，所以新的生成树的生成树T T 将是代价最小的树。和原假设矛盾将是代价最小的树。和原假设矛盾。uvu vT16543271317918127524101564325791013下面将介绍求最小生成树的两种方法：普里姆算法和克鲁斯卡尔算法。7.4.3普里姆算法1普里姆(prim)算法思想下面仅讨论无向网的最小生成树问题。普里姆方法的思想是：在图中任取一个顶点K作为开始点，令U=k，W=V-U，其中V为图中所有顶点集，然后找一个顶点在U中，另一个顶点在W中的边中最短的一条，找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入U集合中，并从W中删去这些顶点，然后重新调整U中顶点到W中顶点的距离,使之保持最小，再重复此过程，直到W为空集止。求解过程参见图8-20。例1654326513566425131163141643142116432142516543214253Prim算法构造最小生成树演示假设开始顶点就选为顶点1，故首先有U=1，W=2，3，4，5，6i123456closesti111111lowcosti0615closest用于存放顶点序号用于存放顶点序号lowest存放权值存放权值i123456closesti131133lowcosti050554i123456closesti131633lowcosti050250i123456closesti131633lowcosti050050i123456closesti131623lowcosti000030i123456closesti131623lowcosti000000#define INFINITE9999#defineMAXN100voidprim(intcostMAXN,intn,intv)intlowcostMAXN,min,closestMAXN,i,j,k;for(i=1;i=n;i+)lowcosti=costvi;closesti=v;for(i=1;in;i+)min=INFINITE;for(j=1;j=n;j+)if(lowcostj!=0&lowcostjmin)min=lowcostj;k=j;printf(“%d%d%d”,closestk,k,min);lowcostk=0;for(j=1;j=n;j+)if(costkj!=0)&(costkjlowcostj)lowcostj=costkj;closestj=k;分析分析:时间复杂度为O(n2)考虑问题的出发点:为使为使生成树上生成树上边的权值之和达到最小边的权值之和达到最小，则应使生成树中每一条边的权值尽则应使生成树中每一条边的权值尽可能地小。可能地小。7.4.4 7.4.4 克鲁斯卡尔（克鲁斯卡尔（kruskalkruskal）算法算法1 克鲁斯卡尔算法基本思想克鲁斯卡尔算法基本思想克鲁斯卡尔算法的基本思想是：将图中所有边按权值递增顺序排列，依次选定取权值较小的边，但要求后面选取的边不能与前面选取的边构成回路，若构成回路，则放弃该条边，再去选后面权值较大的边，n个顶点的图中，选够n-1条边即可。例如，对图8-20（a）中无向网，用克鲁斯卡尔算法求最小生成树的过程见图8-22。克鲁斯卡尔算法构造最小生成树演示例如例如:abcdegf195141827168213ae12dcbgf71485316217121819abcdegf例如例如:195141827168213ae12dcbgf7148531621所得生成树权值和=14+8+3+5+16+21=67 7.5 7.5 有向无环图及其应用有向无环图及其应用一个无环的有向图叫做有向无环图一个无环的有向图叫做有向无环图(directed(directed acyclineacycline graph),graph),简称简称DAGDAG图图判断有向图中是否存在环的方法判断有向图中是否存在环的方法有向树DAG图有向图有向无环图是描述含有公共子式的表达式的有效工具。(a+b)*(b*(c+d)+(c+d)*e)*(c+d)*e)*+abbcccddd用二叉树描述表达式ee*+abbcd用DAG描述表达式e有向无环图也是描述一项工程或系统的进行过程的有效工具。C12C10C11C9C1C2C3C4C6C5C7C87.5.1 AOV7.5.1 AOV网与拓扑排序的概念网与拓扑排序的概念一、一、AOVAOV网的概念网的概念 1.AOV1.AOV网定义网定义 在一个有向图中，若用顶点表示活动，有向边表在一个有向图中，若用顶点表示活动，有向边表示活动间先后关系，称该有向图叫做顶点表示活动的示活动间先后关系，称该有向图叫做顶点表示活动的网络网络(Activity On Vertex network)(Activity On Vertex network)简称为简称为AOVAOV网。网。在在AOVAOV网中，若从顶点网中，若从顶点i i到顶点到顶点j j之间存在一条有向之间存在一条有向路径，称顶点路径，称顶点i i是是顶点顶点j j的前驱，或者称顶点的前驱，或者称顶点j j是顶点是顶点i i的后继。若的后继。若是图中的边，则称顶点是图中的边，则称顶点i i是顶点是顶点j j的直的直接前驱，顶点接前驱，顶点j j是顶点是顶点i i的直接后继。的直接后继。2.AOV2.AOV网实际意义网实际意义现代化管理中现代化管理中,通常我们把计划、施工过程、生产流通常我们把计划、施工过程、生产流程、程序流程等都当成一个工程，一个大的工程常常被划程、程序流程等都当成一个工程，一个大的工程常常被划分成许多较小的子工程，这些子工程称为活动。分成许多较小的子工程，这些子工程称为活动。在整个工程实施过程中，有些活动开始是以它的所有在整个工程实施过程中，有些活动开始是以它的所有前序活动的结束为先决条件的，必须在其它有关活动完成前序活动的结束为先决条件的，必须在其它有关活动完成之后才能开始，有些活动没有先决条件，可以安排在任意之后才能开始，有些活动没有先决条件，可以安排在任意时间开始。时间开始。AOVAOV网就是一种可以形象地反映出整个工程中各个活动网就是一种可以形象地反映出整个工程中各个活动之间前后关系的有向图。之间前后关系的有向图。例如，计算机专业学生的课程开设可看成是一个工程，例如，计算机专业学生的课程开设可看成是一个工程，每一门课程就是工程中的活动，图每一门课程就是工程中的活动，图7.277.27给出了若干门所开给出了若干门所开设的课程，其中有些课程的开设有先后关系，有些则没有设的课程，其中有些课程的开设有先后关系，有些则没有先后关系，有先后关系的课程必须按先后关系开设。先后关系，有先后关系的课程必须按先后关系开设。在图中，我们用一种有向图来表示课程开设例课程代号课程名称先修棵C1C2C3C4C5C6C7C8C9C10C11C12无C1C1,C2C1C3,C4C11C3.C5C3,C6无C9C9C1,C9,C10程序设计基础离散数学数据结构汇编语言语言的设计和分析计算机原理编译原理操作系统高等数学线性代数普通物理数值分析C1C2C3C4C5C6C7C8C9C10C11C12二二 拓扑排序拓扑排序1.1.定义定义 给出有向图给出有向图G=(V,E)G=(V,E)，对于对于V V中的顶点的线性序列中的顶点的线性序列(vi1,vi2,.,(vi1,vi2,.,vinvin)，如果满足如下条件：若在如果满足如下条件：若在G G中从顶点中从顶点 vi vi 到到vjvj有一条路经，则在序列中顶点有一条路经，则在序列中顶点vivi必在顶点必在顶点 vjvj之前；则称之前；则称该序列为该序列为 G G的一