数据结构之图的存储结构与遍历

1、第7章 图7.1 图的定义与基本术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图的应用 7.6 最短路径返回主目录图结构与与表结构构和树结结构的不不同表现现在结点点之间的的关系上上，线性性表中结结点之间间的关系系是一对对一的；树是按按分层关关系组织织的结构构，树结结构之间间是一对对多；对对于图结结构，图图中顶点点之间的的关系可可以是多多对多，即一顶顶点和其其它顶点点间的关关系是任任意的，可以有有关也可可以无关关。因此此，图G树TL，图是一一种比较较复杂的的非线性性数据结结构。图作为一一种非线线性结构构，被广广泛应用用于多个个技术领领域。在在本章中中，主要

2、要是应用用图论的的理论知知识来讨讨论如何何在计算算机上表表示和处处理图，以及如如何利用用图来解解决一些些实际问问题。返回主目目录7.1图的定义义与基本本术语7.1.1图的定义义图（Graph）是一种种网状数数据结构构，其形形式化定定义如下下：Graph=（V，R）V=xxDataObjectR=VRVR=P（x，y）（x，yV）返回主目目录DataObject为一个个集合，该集合合中的所有元素素具有相同的特特性。V中的数据据元素通通常称为为顶点（vertex），VR是两个顶顶点之间间的关系系的集合合。P（x，y）表表示x和和y之间间有特定定的关联联属性P。弧：若VR，则表示从顶顶点x到顶点y的

3、一条弧（arc），并称称x为弧尾（tail）或起始点，称y为弧头（head）或终端点。有向图：若图中的的边是有有方向的的，称这这样的图图为有向图。返回主目目录无向图：若VR，必有VR，即VR是对称关关系，这这时以无无序对（x，y）来代替替两个有有序对，表示x和y之间的一一条边（edge），此时时的图称称为无向图。例如：下下图G1是有向图图，G2是无向图图2134G12145G23返回主目目录在图中，我们可可以将任任一顶点点看成是是图的第第一个顶顶点，同同理，对对于任一一顶点而而言，它它的邻接接点之间间也不存存在顺序序关系。为了操操作的方方便，我我们需要要将图中中的顶点点按任意意序列排排列起来来

4、。顶点在这个人为的随随意排列列中的位位置序号号称为顶点在图图中的位位置。图的基本本操作和和其它数数据结构构一样，也有创创建、插插入、删删除、查查找等。返回主目目录图的抽象象类型定定义：ADTGraph数据对象象V：一个集集合，该该集合中中的所有有元素具具有相同同的特性性。数据关系系R：R=VRVR=P（x，y）（x，yV）返回主目目录基本操作作：（1）GreateGraph(G)：创建图图G。（2）DestoryGraph(G)：销毁图图G。（3）LocateVertex(G,v)：确定顶点点v在图图G中的的位置。若图G中没有顶顶点v，则函数数值为“空”。（4）GetVertex(G,I)：取

5、取出图G中的第第i个顶顶点的值。若i图G中顶点数数，则函函数值为为“空”。返回主目目录（5）FirstAdjVertex(G,v)：求图图G中顶顶点v的的第一个邻接点点。若v无邻接接点或图图G中无无顶点v，则函函数值为为“空”。（6）NextAdjVertex(G,v,w)：已已知w是是图G中中顶点v的某个邻邻接点，求顶点点v的下下一个邻邻接点（紧跟在在w后面面）。若若w是v的最后后一个邻邻接点，则函数数值为“空”。（7）InsertVertex(G,u)：在在图G中中增加一一个顶点点u。返回主目目录（8）DeleteVertex（G，v）：删删除图G的顶点点v及与与顶点v相相关联的的弧。（9

6、）InsertArc（G，v，w）：在图图G中增增加一条条从顶点v到到顶点w的弧。（10）DeleteArc（G，v，w）：删除除图G中中从顶点点v到顶点w的弧。（11）TraverseGraph（G）：按照照某种次次序，对对图G的每个结结点访问问一次且且最多一一次。返回主目目录7.1.2基本术语语设用n表示图中中顶点的的个数，用e表示图中中边或弧弧的数目目，并且且不考虑虑图中每每个顶点点到其自自身的边边或弧。无向完全全图：有n（n-1）/2条边（图图中每个个顶点和和其余n-1个顶点都有边相相连）的无向向图为无无向完全全图。有向完全全图：有n（n-1）条边（图中每每个顶点点和其余余n-1个顶点

7、都有弧相相连）的有向向图为有有向完全全图。返回主目目录稀疏图：对于有很很少条边边的图（enlogn）称为稀稀疏图，反之称为为稠密图。子图：设有两个个图G=（V，E）和图G/=（V/，E/）,若V/V且E/E，则称图G/为G的子图。图G1和图G2的子图见见p155的图7.2所示。返回主目目录对于无向图G=（V，E），如果果边（v，v/）E，则称顶顶点v，v/互为邻接接点，即即v，v/相邻接。边（v，v/）依附于于顶点v和v/，或者说说边（v，v/）与顶点点v和v/相关联。对于有向图G=（V，A）而言，若弧A，则称顶顶点v邻接到顶顶点v/，顶点v/邻接自顶顶点v，或者说说弧与顶点v，v/相关联。邻

8、接点：返回主目目录度、入度度和出度度对于无向图而而言，顶点v的度是指和v相关联的的边的数数目，记作TD（v）。对于有向向图而言言，顶点v的度有出度和入度两部分：以顶点v为弧头的的弧的数数目称为该顶顶点的入度，记作ID（v），以顶点v为弧尾的的弧的数数目称为该顶顶点的出度，记作OD（v）则顶点v的度为：TD（v）= ID（v）+ OD（v）。返回主目目录一般地，若图G中有n个顶点，e条边或弧弧，则图图中顶点点的度与与边的关关系如下下：e=TD(Vi) 2ni=1返回主目目录权与网:在实际应应用中，有时图图的边或弧上上往往与具具有一定意义义的数有有关，即每一条边边都有与与它相关关的数，称为权，这些

9、权权可以表表示从一一个顶点点到另一一个顶点点的距离离或耗费费等信息息。我们们将这种带权权的图叫做赋权图或或网。图例见p156的图7.3所示。返回主目目录路径与回回路无向图G=（V，E）中中从顶点v到到v/的路径是一个顶顶点序列列vi 0，vi1，vi2，vin，其中（vij-1，vij）E，1jn。如果图G是有向图，则路径也是有向的，顶点点序列应应满足A，1jn。路径长度度：指路径径上经过过的弧或或边的数数目。返回主目目录回路或环环：在一个个路径中中，若其其第一个个顶点和和最后一一个顶点点是相同同的，即即v =v/，则称该该路径为为一个回路或环环。简单路径径：若表示路路径的顶顶点序列列中的顶顶

10、点各不相同同，则称这这样的路路径为简单路径径。简单回路路：除了第一个和和最后一一个顶点点外，其其余各顶顶点均不重复复出现的回路为为简单回路路。返回主目目录连通图连通图：在无向图图G=（V，E）中，若若从vi到vj有路径相相通，则则称顶点点vi与vj是连通的的。如果果对于图图中的任任意两个个顶点vi、vjV，vi，vj都是连通通的，则则称该无无向图G为连通通图。连通分量量：无向图图中的极大连通通子图称为该无无向图的的连通分分量。返回主目目录强连通图图：在有向向图G=（V，A）中，若对于于每对顶顶点vi、vjV且vivj，从vi到vj和vj到vi都有路径径，则称称该有向向图为强强连通图图。强连通分

11、分量：有向图的的极大强连连通子图图称作有向向图的强强连通分分量。图G1和图G3的连通分分量见p157的图7.4所示返回主目目录生成树一个连通通图的生生成树是是指一个个极小连通通子图，它含有有图中的的全部顶点点，但只有有足已构构成一棵棵树的n-1条条边。如图p157的图7.5所示。返回主目目录7.2图的存储储结构图的存储储结构方方法有：邻接矩矩阵表示示法；邻接表表；邻接多多重表；十字链链表返回主目目录邻接矩阵阵表示法法图的邻接接矩阵表表示法（AdjacencyMatrix）也称作数数组表示示法。它采用两个数组组来表示图图：一个个是用于于存储顶点点信息的一维数数组，另另一个是是用于存储图中中顶点之

12、之间关联联关系的二维数数组，这这个关联关系系数组被称为邻接矩阵阵。返回主目目录若G是一具有有n个顶点的的无权图图，G的邻接矩矩阵是具具有如下下性质的的nn矩阵A：Ai,j=若或（vi,vj)VR 0 反之G1和G2的邻接矩矩阵见p158的图7.6所示返回主目目录若图G是一个有有n个顶点的的网，则则它的邻邻接矩阵阵是具有有如下性性质的nn矩阵A：Ai,j=Wij 若或（vi,vj)VR 反之有向网及及其邻接接矩阵见见p158的图7.7所示。返回主目目录邻接矩阵阵表示法法的C语言类型型描述为为：#defineMAX_VERTEX_NUM10/*最多顶点点个数*/#defineINFINITY327

13、68/*最多顶点点个数*/typedefenumDG,DN,UDG,UDNGraphKind;/*图的种类类：DG表示有向向图, DN表示有向向网, UDG表示无向向图, UDN表示无向向网*/typedefcharVertexData;/*假设顶点点数据为为字符型型*/typedefstructArcNodeAdjTypeadj;/*对于无权权图，用用1或0表示是否否相邻；对带权权图，则则为权值值类型*/OtherInfoinfo; ArcNode;返回主目目录typedefstructVertexDatavexsMAX_VERTEX_NUM;/*顶点向量量*/ArcNodearcsMAX_

14、VERTEX_NUMMAX_VERTEX_NUM;/*邻接矩阵阵*/intvexnum,arcnum;/*图的顶点点数和弧弧数*/GraphKindkind;/*图的种类类标志*/ AdjMatrix;/*（AdjacencyMatrixGraph）*/返回主目目录邻接矩阵阵法的特特点：1.存储空间间：对于于无向图图而言，它的邻邻接矩阵阵是对称称矩阵，所以可可采用压压缩存储储法（下下三角），其存存储空间间只需n(n-1)/2。但对于于有向图图而言，因为它它的弧是是有方向向的，它它的邻接接矩阵不不一定是是对称矩矩阵，所所以需要要n2个存储空空间。2.便于运算算：采用邻接接矩阵表表示法，便于判判定

15、图中中任意两两个顶点点之间是是否有边边相连，即根据据Ai，j=0或1来判断。另外还还便于求求得各个个顶点的的度。返回主目目录对于无向图而言，其其邻接矩矩阵第i行元素之之和就是是图中第第i个顶点的的度：TD(vi)=Ai,j j=1n对于有向图而言，其其邻接矩矩阵第i行元素之之和就是是图中第第i个顶点的的出度，第i列元元素之和和就是图图中第i个顶点点的入度度。OD(vi)=Ai,j j=1nID(vi)=Aj,i j=1n顶点i的出度：顶点i的入度：返回主目目录采用邻接接矩阵存存储法表表示图，很便于于实现图图的一些些基本操操作，如如FirstAdjVertex（G，v）：（1）首先，由由Loca

16、teVertex（G，v）找找到v在在图中的的位置，即v在在一维数数组vexs中中的序号号i。（2）二维数组组arcs中第第i行上上第一个个adj域非零零的分量量所在的的列号j，便是是v的第第一个邻邻接点在在图G中中的位置置。（3）取出一维维数组vexsj中的数数据信息息，即与与顶点v邻接的的第一个个邻接点点的信息息。注意：稀疏图图不适于于用邻接接矩阵来来存储，因为这这样会造造成存储储空间的的浪费。返回主目目录用邻接矩矩阵法创创建有向向网的算算法如下下：intLocateVertex(AdjMatrix* G, VertexDatav)/*求顶点位位置函数数*/ intj=Error,k;fo

17、r(k=0;kvexnum;k+)if(G-vexsk=v) j=k;break; return(j);返回主目目录intCreateDN(AdjMatrix *G)/*创建一个个有向网网*/ inti,j,k,weight; VertexDatav1,v2;scanf(%d,%d,&G-arcnum,&G-vexnum);/*输入图的的顶点数数和弧数数*/for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)G-arcsij.adj=INFINITY;for(i=0;ivexnum;i+)scanf(%c,&G-vexsi);/*输入图的的顶点*/for(k=0;kar

18、cnum;k+)返回主目目录 scanf(%c,%c,%d,&v1,&v2,&weight);/*输入一条条弧的两两个顶点点及权值值*/i=LocateVex_M(G,v1);j=LocateVex_M(G,v2);G-arcsij.adj=weight;/*建立弧*/return(Ok); 分析：该算法法的时间间复杂度度为O（n2+en），其其中O（n2）时间耗耗费在对对二维数数组arcs的的每个分分量的arj域域初始化化赋值上上。O（en）的时时间耗费费在有向向网中边权权的赋值值上。返回主目目录邻接表表表示法邻接表（AdjacencyList）表示法法实际上上是图的的一种链链式存储储结构。

19、它的基本本思想是是只存有有关联的的信息，对于图图中存在在的边信信息则存存储，而而对于不不相邻接接的顶点点则不保保留信息息。在邻接接表中，对图中中的每个个顶点建建立一个个带头结结点的边边链表，每个边边链表的的头结点点又构成成一个表表头结点点表。这样，一一个n个顶点的的图的邻邻接表表表示由表头结点点表与边表两部分构构成。返回主目目录（1）表头结结点表：由所有表表头结点点以顺序序结构（向量）的形式式存储，以便可可以随机机访问任任一顶点点的单链链表。表头结点点有两部部分构成成，其中中数据域域（vexdata）用于存存储顶点点的名或或其它有有关信息息；链域域（firstarc）用于指指向链表表中第一一个

20、顶点点（即与与顶点vi邻接的第第一个邻邻接点）。表头结点点结构为为：vexdatafirstarc返回主目目录（2）边表：由表示示图中顶顶点间邻邻接关系系的n个边链表表组成。它由三三部分组组成，其中邻接接点域（adjvex）用于存存放与顶顶点vi相邻接的的顶点在在图中的的位置；链域（nextarc）用于指指向与顶顶点vi相关联的的下一条条边或弧弧的结点点；数据据域（info）用于存存放与边边或弧相相关的信信息（如如赋权图图中每条条边或弧弧的权值值等）。adjvexinfonextarc弧结点结结构为：返回主目目录图例 p161的图7.9所示是图图G1、G2的邻接表表表示法法返回主目目录邻接表存

21、存储结构构的形式式化说明明如下：#defineMAX_VERTEX_NUM10/*最多顶点点个数*/typedefenumDG,DN,UDG,UDNGraphKind;/*图的种类类*/typedefstructArcNodeintadjvex;/*该弧指向向顶点的的位置*/structArcNode*nextarc;/*指向下一一条弧的的指针*/OtherInfoinfo;/*与该弧相相关的信信息*/ ArcNode; 返回主目目录typedefstructVertexNodeVertexDatadata;/*顶点数据据*/ArcNode*firstarc;/*指向该顶顶点第一一条弧的的指针

22、*/ VertexNode; typedefstructVertexNodevertexMAX_VERTEX_NUM;intvexnum,arcnum;/*图的顶点点数和弧弧数*/GraphKindkind;/*图的种类类标志*/AdjList;/*基于邻接接表的图图(AdjacencyListGraph)*/返回主目目录存储空间间：对于有n个顶点，e条边的无无向图而而言，若采取取邻接表表作为存存储结构构，则需需要n个表头结结点和2e个表结点点。无向图的的度：在无向图图的邻接接表中，顶点vi的度恰好好就是第第i个边链表表上结点点的个数数。有向图的的度：在有向图图中，第第i个边链表表上顶点点的个

23、数数是顶点点vi的出度。要想求求得该顶顶点的入入度，则则必须遍遍历整个个邻接表表。在所所有单链链表中查查找邻接接点域的的值为i的结点点并计数数求和。返回主目目录由此可见见，对于于用邻接接表方式式存储的的有向图图，求顶顶点的入入度并不不方便，因此需需要有一一种解决决的方法法逆邻接表表法。对图中的的每一顶顶点vi建立一个个递邻接接表，即即对每个个顶点vi建立一个个所有以以顶点vi为弧头的的弧的表表，这样样求顶点点vi的入度即即是计算算逆邻接接表中第第i个顶点的的边链表表中结点点个数。图G1的逆邻接接表表示示法见p162的图7.10返回主目目录十字链表表十字链表(OrthogonalList)是有向

24、图图的另一一种链式式存储结结构。我我们也可可以把它它看成是是将有向向图的邻邻接表和和逆邻接接表结合合起来形形成的一一种链表表。有向图中中的每一一条弧对对应十字字链表中中的一个个弧结点，同时有有向图中中的每个个顶点在在十字链链表中对对应有一一个结点点，叫做做顶点结点点。这两类结结点的结结构见p162的图7.11所示。返回主目目录图G1的十字链链表表示示见p163的图7.12所示。1 2 1 3 4 1 1 3 2 4 3 4 1234返回主目目录建立一个个有向图图的十字字链表的的算法如如下：voidCrtOrthList（OrthListg）/*从终端输输入n个顶点的的信息和和e条弧的信信息，以

25、以建立一一个有向向图的十十字链表表*/ scanf(“%d,%d”,&n,&e);/*键盘输入入图的顶顶点个数数和弧的的个数*/for(i=0;in;i+)scanf(“%c”,g.vertexi.data）；g.vertexi.firstin=NULL；g.vertexi.firsout=NULL；返回主目目录for(k=0;ktailvex=i；p-headvex=j；p-tlink= g.vertexi.firstout；g.vertexi.firstout=p；p-hlink=g.vertexj.firstin；g.vertexj.firstin=p；/*CrtOrthList*/返回

26、主目目录十字链表表的优点点：在十字链表中既既能够很很容易地地找到以以vi为尾的弧弧，也能能够容易易地找到到以vi为头的弧弧，因此此对于有有向图，若采用用十字链链表作为为存储结结构，则则很容易易求出顶顶点vi的度。返回主目目录邻接多重重表邻接多重重表(Adjacency Multi_list)是无向图图的另外外一种存存储结构构。使用用邻接多多重表这这种存储储结构是是因为它能能够提供供更为方方便的边边处理信信息。邻接多重表是指将图中中关于一一条边的的信息用用一个结结点来表表示。邻接多重重表中的的边结点点结构和和顶点结结点结构构见p164的图7.13所示。返回主目目录邻接多重重表的结结构类型型说明如

27、如下：typedefstructEdgeNode intmark,ivex,jvex;structEdgeNode*ilink,*jlink;EdgeNode;typedef structVertexDatadata;EdgeNode*firstedge;VertexNode;返回主目目录typedef structVertexNodevertexMAX_VERTEX_NUM;intvexnum,arcnum;/*图的顶点点数和弧弧数*/GraphKindkind;/*图的种类类*/ AdjMultiList;/*基于图的的邻接多多重表表表示法(Adjacency Multi_list)*/图

28、G2的邻接多多重表见见p165的图7.14所示。返回主目目录7.4图的遍历历图的遍历历：从图中的某某个顶点点出发，按某种种方法对对图中的的所有顶顶点访问问且仅访访问一次次。为了保证证图中的各顶点点在遍历历过程中中访问且且仅访问问一次，需要为为每个顶顶点设一一个访问问标志，用以标标示图中中每个顶顶点是否否被访问问过，访访问标志志用数组组visitedn来表示。图的遍历历方法有有两种：深度优先先搜索和广度优先先搜索返回主目目录深度优先先搜索：深度优先先搜索（Depth_FirstSearch）是指按按照深度方向向搜索，它类似似于树的的先根遍遍历。深度优先先算法的的基本思思想是：（1）从图中中某个顶

29、顶点v0出发，首首先访问问v0。（2）找出刚刚访问过过的顶点点vi的第一个个未被访访问的邻邻接点，然后访访问该顶顶点。重重复此步步骤，直直到当前前的顶点点没有未未被访问问的邻接接点为止止。（3）返回前一一个访问问过的顶顶点，找找出该顶顶点的下下一个未未被访问问的邻接接点，访访问该顶顶点。转转2。返回主目目录采用递归归的形式式说明，则深度优优先搜索索连通子子图的的的基本思思想可表表示为：（1）访问出发发点v0。（2）依次以v0的未被访访问的邻邻接点为为出发点点，深度度优先搜搜索图，直至图图中所有有与v0有路径相相通的顶顶点都被被访问。若此时图图中还有有顶点未未被访问问，则另另选图中中一个未被访访

30、问的顶顶点作为为起始点点，重复复上述深深度优先先搜索过过程，直直至图中中所有顶顶点均被被访问过过为止。返回主目目录深度优先先搜索的的过程示示例见p167的7.15图所示。其中实箭箭头代表表访问方方向，虚虚箭头代代表回溯溯方向，箭头旁旁边的数数字代表表搜索顺顺序，A为起始顶顶点。8ADGBEHCFI1236710114155149131216访问序列列为：A、B、C、F、E、G、D、H、I。返回主目目录图的深度度优先搜搜索的算算法描述述如下：#define True1#define False0#define Error 1/*出错*/#define Ok 1intvisitedMAX_VERT

31、EX_NUM;/*访问标志志数组*/ 返回主目目录voidTraverseGraph(Graphg)/*对图g进行深度度优先搜搜索，Graph表示图的的一种存存储结构构，如数数组表示示法或邻邻接表等等*/ for(vi=0;vig.vexnum;vi+)visitedvi=False;/*访问标志志数组初初始*/for( vi=0;vig.vexnum;vi+)/*调用深度度遍历连连通子图图的操作作*/*若图g是连通图图，则此此循环只只执行一一次*/if(！visitedvi)DepthFirstSearch(g，vi)；/*TraverseGraph*/返回主目目录深度遍历历v0所在地连连通

32、子图图算法如如下：voidDepthFirstSearch（Graphg,int v0）/*深度遍历历v0所在的连连通子图图*/ visit（v0）；visitedv0=True；/*访问顶点点v0，并置访访问标志志数组相相应分量量值*/w=FirstAdjVertex(g,v0);while( w!=-1)/*邻接点存存在*/ if(!visitedw)DepthFirstSearch(g,w);/*递归调用用DepthFirstSearch*/w=NextAdjVertex(g,v0,w);/*找下一个个邻接点点*/ /*DepthFirstSearch*/返回主目目录上述算法法中对于Fi

33、rstAdjVertex（g，v0）以及NextAdjVertex（g，v0，w）并没有有具体实实现。因为对于于图的不不同存储储方法，两个操操作的实实现方法法不同，时间耗耗费也不不同。下面的算算法是在在邻接矩矩阵与邻邻接表方方式下实实现上面面算法的的功能。返回主目目录1）用邻接接矩阵方方式实现现深度优优先搜索索voidDepthFirstSearch(AdjMatrixg,int v0)/*图g为邻接矩阵阵类型AdjMatrix*/visit(v0);visitedv0=True;for(vj=0;vjadjvex)DepthFirstSearch（g，p-adjvex）；p=p-nextar

34、c；/*DepthFirstSearch*/返回主目目录分析算法法：以邻接接表作为为存储结结构，查查找每个个顶点的的邻接点点的时间间复杂度度为O(e)，其中e是无向图图中的边边数或有有向图中中弧数,则深度优优先搜索索图的时时间复杂杂度为O(n+e)。返回主目目录3）用非递递归过程程实现深深度优先先搜索voidDepthFirstSearch(Graph g,intv0)/*从v0出发深度度优先搜搜索图g*/InitStack(S);/*初始化空空栈*/Push(S, v0)；while( !Empty(S) v=Pop(S);if(!visited(v)/*栈中中可能有有重复结结点*/visi

35、t(v);visitedv=True;w=FirstAdj(g, v);/*求v的第一个个邻接点点*/while(w!=-1)if (!visited(w)Push(S,w);w=NextAdj(g,v,w);/*求v相对于w的下一个个邻接点点*/ 返回主目目录7.3.2广度优先先搜索广度优先先搜索（Breadth_First Search）是指按照广度度方向搜搜索，它类似似于树的的按层次次遍历。广度优先先搜索的的基本思思想是：（1）从图中某某个顶点点v0出发，首首先访问问v0。（2）依次访问问v0的各个未未被访问问的邻接接点。（3）分别从这这些邻接接点（端端结点）出发，依次访访问它们们的各个

36、个未被访访问的邻邻接点（新的端端结点）。返回主目目录访问时应应保证：如果Vi和Vk为当前端端结点，且Vi在Vk之前被访访问，则则Vi的所有未未被访问问的邻接接点应在在Vk的所有未未被访问问的邻接接点之前前访问。重复（3），直到到所有端端结点均均没有未未被访问问的邻接接点为止止。若此时还还有顶点点未被访访问，则则选一个个未被访访问的顶点作作为起始始点，重重复上述述过程，直至所所有顶点点均被访访问过为为止。返回主目目录广度优先先搜索过过程示例例见p169的图7.16所示。其中箭头头代表搜搜索方向向，箭头头旁边的的数字代代表搜索索顺序，A为起始顶顶点。ADGBEHCFI14657823访问序列列为：

37、A、B、E、D、C、G、F、H、I。返回主目目录广度优先先搜索连连通子图图的算法法如下：voidBreadthFirstSearch(Graphg,intv0)/*广度优先先搜索图图g中v0所在的连连通子图图*/ visit(v0); visitedv0=True;InitQueue(&Q);/*初始化空空队*/EnterQueue(&Q,v0)；/*v0进队*/while( !Empty(Q) DeleteQueue(&Q,&v);/*队头元素素出队*/w=FirstAdj(g,v);/*求v的第一个个邻接点点*/返回主目目录while(w!=-1)if (!visited(w) visit

38、(w);visitedw=True;EnterQueue(&Q,w);w=NextAdj(g,v,w);/*求v相对于w的下一个个邻接点点*/返回主目目录7.4图的连通通性问题题无向图的的连通分分量在对图遍遍历时，对于连通通图，无论是是广度优优先搜索索还是深深度优先先搜索，仅需要调调用一次次搜索过过程，即从任任一个顶顶点出发发，便可可以遍历历图中的的各个顶顶点。对于非连连通图，则需要多次调用搜索索过程，而每次次调用得得到的顶顶点访问问序列恰恰为各连连通分量量中的顶顶点集。调用搜索索过程的的次数就就是该图图连通分分量的个个数。返回主目目录例如：p171的图7.17(a)是一个非非连通图图，按照照

39、它的邻邻接表进进行深度度优先搜搜索遍历历，三次次调用深深度优先先搜索（DepthFirstSearch）过程得得到的访访问顶点点序列为为：1，2，4，3，95，6，78，10因此有三三个连通通分量。如p171的图7.17(c).返回主目目录最小生成成树在一个连通网的的所有生生成树中中，各边的代代价之和和最小的的那棵生生成树称称为该连连通网的的最小代代价生成成树（Minimum CostSpanningTree），简称称为最小生成成树。最小生成成树的重要性质质如下：设N=(V,E)是一连通通网，U是顶点集集V的一个非非空子集集。若（u ,v）是一条条具有最最小权值值的边，其中uU，vV-U，则存

40、在在一棵包包含边（u ,v）的最小小生成树树。返回主目目录用反证法来证明这这个最小小生成树树（MST）的性质质：假设不存在这这样一棵棵包含边边（u ,v）的最小小生成树树。任取取一棵最最小生成成树T，将（u ,v）加入T中。根据据树的性性质，此此时T中必形成成一个包包含（u ,v）的回路路，且回回路中必必有一条条边（u, v）的权值值大于或或等于（u ,v）的权值值。删除除（u ,v），则得得到一棵棵代价小小于等于于T的生成树树T，且T为一棵包包含边（u ,v）的最小小生成树树。这与与假设矛矛盾。返回主目目录一个连通通网的最最小生成成树算法法：普里姆算算法假设N=(V,E)是连通网网，TE为最

41、小生生成树中中边的集集合。（1）初始U=u0(u0V),TE=；（2）在所有uU,vV-U的边中选选一条代代价最小小的边（u0，v0）并入集集合TE，同时将将v0并入U；（3）重复（2），直直到U=V为止。此时，TE中必含有有n-1条边，则则T=（V，TE）为N的最小生生成树。返回主目目录普里姆算算法是逐逐步增加加U中的顶点点，可称称为“加点法”注意：选择最小小边时，可能有有多条同同样权值值的边可可供选择择，此时时任选其其一。为了实现现这个算算法需设设一个辅辅助数组组closedge，以记录录从U道V-U具有最小小代价的的边。对对每个顶顶点vV-U，在辅助助数组中中存在一一个分量量closed

42、gev，它包括括两个域域vex和lowcost，其中lowcost存储该边边上的权权，显然然有closedgev.lowcoast=Min(cost(u,v)| uU)返回主目目录普里姆算算法可描描述为：struct VertexDataadjvex;intlowcost; closedgeMAX_VERTEX_NUM;/*求最小生生成树时时的辅助助数组*/返回主目目录MiniSpanTree_Prim(AdjMatrixgn,VertexDatau)/*从顶点u出发，按按普里姆姆算法构构造连通网gn的最小生生成树，并输出出生成树树的每条条边*/k=LocateVertex(gn, u);cl

43、osedgek.lowcost=0;/*初始化，U=u*/for(i=0;ign.vexnum;i+)if( i!=k)/*对V-U中的顶点点i，初始化化closedgei*/closedgei.adjvex=u; closedgei.lowcost=gn.arcski.adj;for(e=1;e=gn.vexnum-1;e+)/*找n-1条边(n=gn.vexnum)*/ k0=Minium(closedge);/*closedgek0中存有当当前最小小边（u0,v0）的信息息*/返回主目目录u0=closedgek0.adjvex;/*u0U*/v0=gn.vexsk0/*v0V-U*/p

44、rintf(u0, v0);/*输出生成成树的当当前最小小边（u0,v0）*/closedgek0.lowcost=0;/*将顶点v0纳入U集合*/for(i=0;ivexnum;i+)/*在顶点v0并入U之后，更更新closedgei*/if( gn.arcsk0i.adjclosedgei.lowcost) closedgei.lowcost= gn.arcsk0i.adj;closedgei.adjvex=v0; 返回主目目录P173的图7.18(a)是一个连连通网，由普里里姆算法法构造最最小生成成树的过过程见图图7.18(b)(f)所示。算法中各各参量的的变化见见p173的表71。返回

45、主目目录2.克鲁斯卡卡尔算法法假设N=(V,E)是连通网网，将N中的边按按权值从从小到大大的顺序序排列；（1）将n个顶点看成成n个集合；（2）按权值值由小到大的的顺序选选择边，所选边边应满足足两个顶顶点不在在同一个个顶点集集合内，将该边边放到生生成树边边的集合合中。同同时将该该边的两两个顶点点所在的的顶点集集合合并并；（3）重重复（2），直直到所有有的顶点点都在同同一个顶顶点集合合内。返回主目目录克鲁斯卡卡尔算法法是逐步步增加生生成树的的边，故故称为“加边法”以p174的连通图图7.19(a)为例，说说明克鲁鲁斯卡尔尔算法的的执行过过程。返回主目目录7.5有向无环环图的应应用拓扑排序序（Top

46、ologicalSort）AOV-网：用顶点表表示活动动，用弧弧表示活活动间的的优先关关系的有有向无环环图，称为顶点点表示活活动的网网（ActivityOnVertexNetwork），简称称为AOV-网。如p175的表7-2课程关系系，用顶点点表示课课程，弧弧表示先先决条件件，则表表72可用一个个有向无无环图表表示。见图p175的图7.21。返回主目目录拓扑序列列：在有向向图G=（V，E）中，V中顶点的的线性序序列（vi1,vi1,vi3,，vin）称为拓扑序列列。此序列必必须满足足：对序序列中任任意两个个顶点vi、vj，在G中有一条条从vi到vj的路径，则在序序列中vi必排在vj之前。如p

47、175的图7.21的一个拓拓扑序列列为：C1,C2,C3,C4,C5,C8,C9,C7,C6。返回主目目录AOV-网的特性性如下：若vi为vj的先行活活动，vj为vk的先行活活动，则则vi必为vk的先行活活动，即即先行关关系具有有可传递递性。AOV-网的拓拓扑序列列不是唯唯一的。如p175的图7.21的另一个个拓扑序序列为：C1,C2,C3, C8, C4,C5, C9,C7,C6。返回主目目录求拓扑排排序的基基本思想想：（1）从有向向图中选选一个无无前驱的的顶点输输出；（2）将此顶顶点和以以它为起起点的弧弧删除；（3）重复（1）、（2），直到到不存在在无前驱驱的顶点点；（4）若此时时输出的顶

48、顶点数小小于有向向图中的的顶点数数，则说说明有向向图中存存在回路路，否则则输出的的顶点的的顺序即即为一个个拓扑序序列。例如p176的图7.22所示的AOV网，其其拓扑序序列为：v1,v6,v4,v3,v2,v5或v1, v3, v2, v6,v4, v5返回主目目录对于有向图的的不同存存储形式式，有不不同实现现的拓扑扑排序算算法。1）基于邻邻接矩阵阵表示的的存储结结构A为有向图图G的邻接矩矩阵，则则有（1）找G中无前驱驱的顶点点在A中找到值值全为0的列；（2）删除以以i为起点的的所有弧弧将矩阵中中i对应应的行全全部置为为0。返回主目目录算法步骤骤为：（1）取1作为第一一新序号号；（2）找一个个

49、未新编编号的、值全为为0的列j，若找到到则转（3）；否则则，若所所有的列列全部都都编过号号，拓扑扑排序结结束；若有列未未曾被编编号，则则该图中中有回路路；（3）输出列列号对应应的顶点点j，把新序序号赋给给所找到到的列；（4）将矩阵阵中j对应的行行全部置置为0;（5）新新序号加加1，转转（2）；返回主目目录2）基于邻邻接表的的存储结结构入度为零零的顶点点即没有有前趋的的顶点，因此我我们可以以附设一一个存放放各顶点点入度的的数组indegree ，于是有有（1）找G中无前驱驱的顶点点查找indegree i为零的顶顶点vi；（2）删除以以i为起点的的所有弧弧对链在顶顶点i后后面的所所有邻接接顶点k

50、，将对对应的indegreek减减1。为了避免免重复检检测入度度为零的的顶点，可以再再设置一一个辅助栈，若若某一顶顶点的入入度减为为0，则则将它入入栈。每每当输出出某一顶顶点时，便将它它从栈中中删除。返回主目目录拓扑排序序的实现现算法intTopoSort(AdjListG) Stack S;intindegreeMAX_VERTEX_NUM;inti,count, k;ArcNode *p;FindID(G,indegree);/*求各顶点点入度*/InitStack(&S);/*初始化辅辅助栈*/for(i=0;iadjvex;indegreek-;/*i号顶点的的每个邻邻接点的的入度减减

51、1*/if(indegreek=0)Push(&S, k);/*若入度减减为0，则入栈栈*/p=p-nextarc; /*while*/if(countG.vexnum)return(Error);/*该有向图图含有回回路*/elsereturn(Ok);返回主目目录求各顶点点入度的的函数void FindID(AdjListG,int indegreeMAX_VERTEX_NUM)/*求各顶点点的入度度*/ inti;ArcNode*p;for(i=0;iG.vexnum;i+)indegreei=0;for(i=0;iadjvex+;p=p-nextarc; /* for*/返回主目目录P

52、176的图7.22所示的AOV-网的邻接接表如图图p178的图7.23所示，用用拓扑排排序算法法求出的的拓扑序序列为：v6，v1，v3，v2，v4，v5。算法的时时间复杂杂度分析析：若有向无无环图有有n个顶点和和e条弧，则则在拓扑扑排序的的算法中中，for循环需要要执行n次，时间间复杂度度为O(n)；对于while循环，由由于每一一顶点必必定进一一次栈，出一次次栈，其其时间复复杂度为为O(e)；故该算算法的时间复杂杂度为O(n+e)。返回主目目录关键路径径AOE-网：在有向向图中，用顶点表表示事件件，用弧弧表示活活动，弧弧的权值值表示活活动所需需要的时时间。我们把用用这种方方法构造造的有向向无

53、环图图叫做边表示活活动的网网（Activity On EdgeNetwork）,简称AOE-网。AOE-网用在在工程计计划和管管理中，人们最关关心的是是：哪些活动动是影响响工程进进度的关关键活动动？至少需要要多长时时间能完完成整个个工程？返回主目目录源点：存在唯唯一的、入度为为零的顶顶点，叫叫源点。汇点：存在唯唯一的、出度为为零的顶顶点，叫叫汇点。关键路径径：从源点到到汇点的的最长路路径的长长度即为为完成整整个工程程任务所所需的时时间，该该路径叫叫做关键键路径。关键活动动：关键路路径上的的活动叫叫做关键键活动。在AOE-网中的基基本概念念：例如p179的图7.24所示的AOE-网。V0为源点，

54、表示整整个工程程可以开开始，v8为汇点，表示整整个工程程结束。返回主目目录几个重要要的定义义：事件vi的最早发发生时间间ve(i)：从源点点到顶点点vi的最长路路径的长长度，叫叫做事件件vi的最早发发生时间间。求ve(i)时可从源源点开始始，按拓拓扑顺序序向汇点点递推：ve(0)=0；ve(i)=Maxve(k)dut()T,1in-1;其中，T为所有以以i为头的弧弧的集合，dut（）表示与与弧对应的活活动的持持续时间间。返回主目目录事件vi的最晚发发生时间间vl(i)：在保证证汇点按按其最早早发生时时间发生生这一前前提下，事件vi的最晚发发生时间间。在求出ve(i)的基础上上，可从汇点点开始

55、，按逆拓拓扑顺序序向源点点递推，求出vl(i)：vl(n-1)=ve(n-1)；vl(i)=Minvl(k)dut()S,0in-2;其中，S为所有有以i为为尾的弧弧的的集合，dut（）表示示与弧对应应的活动动的持续续时间。返回主目目录活动ai的最早开开始时间间e(i)：如果活活动ai对应的弧弧为，则则e(i)等于从源源点到顶顶点j的的最长路路径的长长度，即即：e(i)=ve(j)活动ai的最晚开开始时间间l(i)：如果活活动ai对应的弧弧为，其其持续时时间为dut（）则有：l(i)=vl(k)-dut（）活动ai的松弛时时间（时时间余量量）：ai的最晚开开始时间间与ai的最早开开始时间间之差

56、：l(i)-e(i)。显然，松松弛时间间（时间间余量）为0的活动为为关键活活动。返回主目目录求关键路路径的基基本步骤骤：（1）对图中中顶点进进行拓扑扑排序，在排序序过程中中按拓扑扑序列求求出每个个事件的的最早发发生时间间ve(i)；（2）按逆拓拓扑序列列求每个个事件的的最晚发发生时间间vl(i)；（3）求出每每个活动动ai的最早开开始时间间e(i)和最晚发发生时间间l(i)；4)找找出e(i)=l(i)的活动ai，即为关关键活动动。返回主目目录修改后的的拓扑排排序算法法intveMAX_VERTEX_NUM;/*每个顶点点的最早早发生时时间*/intTopoOrder(AdjListG,Sta

57、ck* T)/*G为有向网网，T为返回拓拓扑序列列的栈，S为存放入入度为0的顶点的的栈*/int count,i,j,k;ArcNode*p;intindegreeMAX_VERTEX_NUM;/*各顶点入入度数组组*/StackS;InitStack(T);InitStack(&S);/*初始化栈栈T,S*/FindID(G,indegree);/*求各个顶顶点的入入度*/for(i=0;iG.vexnum;i+)if(indegreei=0)Push(&S,i);返回主目目录count=0;for(i=0;iadjvex;if(-indegreek=0)Push(&S,k);/*若顶点的的

58、入度减减为0，则入栈栈*/返回主目目录if(vej+p-weightvek)vek=vej+p-weight;p=p-nextarc;/*while*/ /*while*/if(countG.vexnum)return(Error);elsereturn(Ok); 返回主目目录求关键路路径的实实现算法法intCriticalPath(AdjListG)ArcNode*p;inti,j,k,dut,ei,li;chartag;intvlMAX_VERTEX_NUM;/*每个顶点点的最迟迟发生时时间*/StackT;if(!TopoOrder(G,&T)return(Error);for(i=0;

59、iadjvex;dut=p-weight;if(vlk-dutnextarc; /* while */ /* while*/for(j=0;jAdjvex;dut=p-weight;ei=vej;li=vlk-dut;返回主目目录tag=(ei=li)?*:;printf(%c,%c,%d,%d,%d,%cn,G.vertexj.data,G.vertexk.data,dut,ei,li,tag);/*输出关键键活动*/p=p-nextarc; /*while*/ /* for*/return(Ok); /*CriticalPath*/该算法的的时间复复杂度为为O(n+e)。用该算算法求p17

60、9的图7.24中AOE-网的关键键路径，结果如如p181的图7.25。返回主目目录7.6最短路径径求某一顶顶点到其其它各顶顶点的最最短路径径设有带权的有有向图D=(V,E)，D中的边权权为W(e)。已知知源点为为v0，求v0到其它各各顶点的的最短路路径。如p184的图7.26所示的带带权有向向图，其其源点v0到其它各各顶点的的最短路路径如p184的表73所示。返回主目目录用迪杰斯特特拉（Dijkstra）求最短路路径算法法基本思想想是：按按路径长度度递增的的顺序，逐个产产生各最最短路径径。首先引进进辅助向向量dist，它的每每一个分分量disti表示已经经找到的的且从开开始点v0到每一个个终点