《第7章--图-数据结构-c语言描述课件.ppt》由会员分享，可在线阅读，更多相关《第7章--图-数据结构-c语言描述课件.ppt（137页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第7章章图图7.1图的定义与基本术语图的定义与基本术语7.2图的存储结构图的存储结构7.3图的遍历图的遍历7.4图的应用图的应用7.5总结与提高总结与提高3/29/20231图结构与表结构和树结构的不同表现在结点之图结构与表结构和树结构的不同表现在结点之间的关系上，线性表中结点之间的关系是一对一的；间的关系上，线性表中结点之间的关系是一对一的；树是按分层关系组织的结构，树结构之间是一对多；树是按分层关系组织的结构，树结构之间是一对多；对于图结构，图中顶点之间的关系可以是多对多，对于图结构，图中顶点之间的关系可以是多对多，即一顶点和其它顶点间的关系是任意的，可以有关即一顶点和其它顶点间的关系是
2、任意的，可以有关也可以无关。因此，图也可以无关。因此，图G 树树T L，图是一种比较，图是一种比较复杂的非线性数据结构。复杂的非线性数据结构。图作为一种非线性结构，被广泛应用于多个技术图作为一种非线性结构，被广泛应用于多个技术领域。在本章中，主要是应用图论的理论知识来讨论领域。在本章中，主要是应用图论的理论知识来讨论如何在计算机上表示和处理图，以及如何利用图来解如何在计算机上表示和处理图，以及如何利用图来解决一些实际问题。决一些实际问题。3/29/202327.1图的定义与基本术语图的定义与基本术语7.1.1图的定义图的定义图（图（Graph）是一种网状数据结构，其形式化定）是一种网状数据结构
3、，其形式化定义如下：义如下：Graph=（V，R）V=xxDataObjectxDataObjectR=VRVR=xPyP（x x，y y）（x x，yVyV）3/29/20233 DataObject DataObject为一个集合，该集合中的为一个集合，该集合中的所有元素所有元素具有具有相同的特性相同的特性。V中的数据元素通常称为中的数据元素通常称为顶点顶点（vertex），），VR是两个顶点之间的关系的集合。是两个顶点之间的关系的集合。P P（x x，y y）表示）表示x x和和y y之间有特定的关联属性之间有特定的关联属性P P。弧弧：若若VR，则则表表示示从从顶顶点点x到到顶顶点点y
4、的的一一条条弧弧（arc），并并称称x为为弧弧尾尾（tail）或或起起始始点点，称称y为为弧头弧头（head）或）或终端点终端点。有有向向图图：若若图图中中的的边边是是有有方方向向的的，称称这这样样的的图图为为有有向图向图。3/29/20234在图中，我们可以将任一顶点看成是图的第一在图中，我们可以将任一顶点看成是图的第一个顶点，同理，对于任一顶点而言，它的邻接点之个顶点，同理，对于任一顶点而言，它的邻接点之间也不存在顺序关系。为了操作的方便，我们需要间也不存在顺序关系。为了操作的方便，我们需要将图中的顶点按任意序列排列起来。将图中的顶点按任意序列排列起来。顶点顶点在这个在这个人人为的随意排列
5、中的位置序号称为为的随意排列中的位置序号称为顶点在图中的位置。顶点在图中的位置。图的基本操作和其它数据结构一样，也有创图的基本操作和其它数据结构一样，也有创建、插入、删除、查找等。建、插入、删除、查找等。3/29/20236图的抽象类型定义：图的抽象类型定义：ADTGraph数据对象数据对象V：一个集合，该集合中的所有元素具有相：一个集合，该集合中的所有元素具有相同的特性。同的特性。数据关系数据关系R：R=VRVR=P（x，y）（x，yV）3/29/20237基本操作基本操作：（1）CreateGraph（G）操作前提：已知图操作前提：已知图G不存在不存在操作结果：创建图操作结果：创建图G。（
6、2）DestoryGraph（G）操作前提：已知图操作前提：已知图G存在；存在；操作结果：销毁图操作结果：销毁图G。（3）LocateVertex（G，v）操作前提：已知图操作前提：已知图G存在，顶点存在，顶点v值合法；值合法；操作结果：若顶点操作结果：若顶点v在图在图G中存在，则返回顶点中存在，则返回顶点v在图在图G中的位中的位置。若图置。若图G中没有顶点中没有顶点v，则函数返回值为，则函数返回值为“空空”。（4）GetVertex（G，i）操作前提：已知图操作前提：已知图G存在；存在；操作结果：返回图操作结果：返回图G中的第中的第i个顶点的值。若个顶点的值。若i大于图大于图G中顶点中顶点数
7、，则函数返回值为数，则函数返回值为“空空”。3/29/20238（9）InsertArc（G，v，w）操作前提：已知图操作前提：已知图G存在，存在，v值，值，w值合法；值合法；操作结果：在图操作结果：在图G中增加一条从顶点中增加一条从顶点v到顶点到顶点w的弧。的弧。（10）DeleteArc（G，v，w）操作前提：已知图操作前提：已知图G存在，存在，v值，值，w值合法，存在弧值合法，存在弧(v,w)；操作结果：删除图操作结果：删除图G中从顶点中从顶点v到顶点到顶点w的弧。的弧。（11）TraverseGraph（G）操作前提：已知图操作前提：已知图G存在；存在；操作结果：按照某种次序，对图操作
8、结果：按照某种次序，对图G的每个顶点访问一次且仅的每个顶点访问一次且仅访问一次。访问一次。3/29/2023107.1.2基本术语基本术语设用设用n表示图中顶点的个数，用表示图中顶点的个数，用e表示图中边或表示图中边或弧的数目，并且不考虑图中每个顶点到其自身的边弧的数目，并且不考虑图中每个顶点到其自身的边或弧。或弧。无向完全图无向完全图：有有n（n-1）/2条边条边（图中每个顶点和（图中每个顶点和其余其余n-1个顶点个顶点都有边相连都有边相连）的无向图为无向完全图）的无向图为无向完全图。有向完全图有向完全图：有有n（n-1）条边（图中每个顶点和其条边（图中每个顶点和其余余n-1个顶点个顶点都有
9、弧相连都有弧相连）的有向图为有向完全图）的有向图为有向完全图。3/29/202311AACACDCDAB（a）G1的子图ABCEDEABCEDBA（b）G2的子图3/29/202313度、入度和出度度、入度和出度对于对于无向图而言，无向图而言，顶点顶点v的度的度是是指和指和v相关联的边的相关联的边的数目数目，记作，记作TD（v）。对于有向图而言，对于有向图而言，顶点顶点v的度有的度有出度出度和和入度入度两部分：两部分：以以顶点顶点v为弧头的弧的数目为弧头的弧的数目称为该顶点的称为该顶点的入度入度，记，记作作ID（v），以，以顶点顶点v为弧尾的弧的数目为弧尾的弧的数目称为该顶点称为该顶点的的出度
10、出度，记作，记作OD（v）则顶点则顶点v的度为：的度为：TD（v）=ID（v）+OD（v）。）。3/29/202315一般地，若图一般地，若图G中有中有n个顶点，个顶点，e条边或弧，则图条边或弧，则图中顶点的度与边的关系如下：中顶点的度与边的关系如下：e=TD(Vi)2ni=13/29/20231616图7.3 赋权图示例56616651234192111331418653/29/202318路径与回路路径与回路无向图无向图G=G=（V V，EE）中从）中从顶点顶点v v到到v v/的的路径路径是一个顶是一个顶点序列点序列v vi 0i 0，v vi1i1，v vi2i2，v vinin，其中
11、（，其中（v vij-1ij-1，v vijij）EE，1jn1jn。如果图如果图G G是是有向图有向图，则，则路径路径也是也是有向有向的，顶点序列应的，顶点序列应满足满足vAA，1jn1jn。路径长度路径长度：指路径上经过的弧或边的数目。：指路径上经过的弧或边的数目。3/29/202319回路或环回路或环：在一个路径中，若其第一个顶点和最后：在一个路径中，若其第一个顶点和最后一个顶点是相同的，即一个顶点是相同的，即v=vv=v/，则称该路径为一个，则称该路径为一个回回路或环路或环。简单路径：简单路径：若表示路径的顶点序列中的顶点若表示路径的顶点序列中的顶点各不相各不相同同，则称这样的路径为，
12、则称这样的路径为简单路径简单路径。简单回路：简单回路：除了除了第一个和最后一个顶点外，其余各第一个和最后一个顶点外，其余各顶点顶点均不重复出现均不重复出现的回路为的回路为简单回路简单回路。3/29/202320连通图连通图连通图：连通图：在无向图在无向图G=G=（V V，EE）中，若从）中，若从v vi i到到v vj j有路有路径相通，则称顶点径相通，则称顶点v vi i与与v vj j是连通的。如果对于图中的是连通的。如果对于图中的任意两个顶点任意两个顶点v vi i、v vj jVV，v vi i，v vj j都是连通的，则称该都是连通的，则称该无向图无向图G G为连通图。为连通图。连通
13、分量连通分量：无向图中的：无向图中的极大连通子图极大连通子图称为该无向图的称为该无向图的连通分量。连通分量。3/29/202321强连通图强连通图：在有向图：在有向图G=G=（V V，AA）中，若对于每对）中，若对于每对顶点顶点v vi i、v vj jVV且且v vi ivvj j，从，从vivi到到v vj j和和v vj j到到v vi i都有路径，都有路径，则称该有向图为强连通图。则称该有向图为强连通图。强连通分量：强连通分量：有向图的有向图的极大强连通子图极大强连通子图称作有向图称作有向图的强连通分量的强连通分量。图图G1和图和图G3的连通分量见的连通分量见p157的图的图7.4所示
14、所示3/29/2023227.2图的存储结构图的存储结构图的存储结构方法有：图的存储结构方法有：邻接矩阵表示法；邻接矩阵表示法；邻接表；邻接表；邻接多重表；邻接多重表；十字链表十字链表3/29/202324邻接矩阵表示法邻接矩阵表示法图的邻接矩阵表示法图的邻接矩阵表示法（AdjacencyMatrix）也称作也称作数组表示法数组表示法。它采用它采用两个数组两个数组来表示图：一个是用于来表示图：一个是用于存储顶点信存储顶点信息息的一维数组，另一个是用于的一维数组，另一个是用于存储图中顶点之间关存储图中顶点之间关联关系联关系的二维数组，这个的二维数组，这个关联关系数组关联关系数组被称为被称为邻接邻
15、接矩阵矩阵。3/29/202325若若G是一具有是一具有n个顶点的无权图，个顶点的无权图，G的邻接矩阵是具的邻接矩阵是具有如下性质的有如下性质的nn矩阵矩阵A：Ai,j=1若若或或（vi,vj)VR20反之反之G1和和G2的邻接矩阵的邻接矩阵A1=01100000000110003/29/202326若图若图G是一个有是一个有n个顶点的网，则它的邻接矩阵是具个顶点的网，则它的邻接矩阵是具有如下性质的有如下性质的nn矩阵矩阵A：Ai,j=Wij若若或（或（vi,vj)VR反之反之有向网及其邻接矩阵有向网及其邻接矩阵3/29/2023286978254551V1V6V5V4V2V3v1v2v3v4
16、v5v65748 95 65 2 1 v1v2v3v4v5v6(a)有向网N(b)有向网N的邻接矩阵3/29/202329typedefstructVertexDatavexsMAX_VERTEX_NUM;/*顶点向量*/ArcNodearcsMAX_VERTEX_NUMMAX_VERTEX_NUM;/*邻接矩阵*/intvexnum,arcnum;/*图的顶点数和弧数*/GraphKindkind;/*图的种类标志*/AdjMatrix;/*（AdjacencyMatrixGraph）*/3/29/202331邻接矩阵法的特点：邻接矩阵法的特点：1.存储空间：对于无向图而言，它的邻接矩阵是对
17、存储空间：对于无向图而言，它的邻接矩阵是对称矩阵，所以可采用压缩存储法（下三角），其存称矩阵，所以可采用压缩存储法（下三角），其存储空间只需储空间只需n(n-1)/2。但对于有向图而言，因为它的。但对于有向图而言，因为它的弧是有方向的，它的邻接矩阵不一定是对称矩阵，弧是有方向的，它的邻接矩阵不一定是对称矩阵，所以需要所以需要n2个存储空间。个存储空间。2.便于运算：便于运算：采用邻接矩阵表示法，便于判定图采用邻接矩阵表示法，便于判定图中任意两个顶点之间是否有边相连，即根据中任意两个顶点之间是否有边相连，即根据Ai，j=0或或1来判断。另外还便于求得各个顶点的度。来判断。另外还便于求得各个顶点的
18、度。3/29/202332对于对于无向图无向图而言，其邻接矩阵第而言，其邻接矩阵第i行元素之和就行元素之和就是图中第是图中第i个顶点的度：个顶点的度：TD(vi)=Ai,jj=1n对对于于有有向向图图而而言言，其其邻邻接接矩矩阵阵第第i行行元元素素之之和和就就是是图图中中第第i个个顶顶点点的的出出度度，第第i i列列元元素素之之和和就就是是图图中中第第i i个顶点的入度。个顶点的入度。OD(vi)=Ai,jj=1nID(vi)=Aj,ij=1n顶点顶点i的出度：的出度：顶点顶点i的入度：的入度：3/29/202333采用邻接矩阵存储法表示图，很便于实现图的一些采用邻接矩阵存储法表示图，很便于实
19、现图的一些基本操作，如基本操作，如FirstAdjVertexFirstAdjVertex（G G，v v）：）：（1）首先，由首先，由LocateVertexLocateVertex（G G，v v）找到）找到v v在图中在图中的位置，即的位置，即v v在一维数组在一维数组vexsvexs中的序号中的序号i i。（2）二维数组二维数组arcsarcs中第中第i i行上第一个行上第一个adjadj域非零的分域非零的分量所在的列号量所在的列号j j，便是，便是v v的第一个邻接点在图的第一个邻接点在图G G中的位中的位置。置。（3）取出一维数组取出一维数组vexsjvexsj中的数据信息，即与顶
20、中的数据信息，即与顶点点v v邻接的第一个邻接点的信息。邻接的第一个邻接点的信息。注意注意：稀疏图不适于用邻接矩阵来存储，因为这样：稀疏图不适于用邻接矩阵来存储，因为这样会造成存储空间的浪费。会造成存储空间的浪费。3/29/202334用邻接矩阵法创建有向网的算法如下：用邻接矩阵法创建有向网的算法如下：intLocateVertex(AdjMatrix*G,VertexDatav)/*求顶点位置函数求顶点位置函数*/intj=Error,k;for(k=0;kvexnum;k+)if(G-vexsk=v)j=k;break;return(j);3/29/202335intCreateDN(Ad
21、jMatrix*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;karcnum;k+)3/29/202336scanf(%c,%c,%d,&v1,&v2,&weight);/*输入一条弧
22、的两个顶点及权值输入一条弧的两个顶点及权值*/i=LocateVex_M(G,v1);j=LocateVex_M(G,v2);G-arcsij.adj=weight;/*建立弧建立弧*/return(Ok);分析分析：该算法的时间复杂度为：该算法的时间复杂度为O O（n n2 2+en+en），其中），其中 O O（n n2 2）时间耗费在对二维数组）时间耗费在对二维数组arcsarcs的每个分量的的每个分量的arjarj域初始化赋值上。域初始化赋值上。O O（enen）的时间耗费在有向网中）的时间耗费在有向网中边权的赋值上。边权的赋值上。3/29/202337邻接表表示法邻接表表示法邻接表（
23、邻接表（AdjacencyList）表示法实际上是图的一种）表示法实际上是图的一种链式存储结构。链式存储结构。它的基本思想是只存有关联的信息，它的基本思想是只存有关联的信息，对于图中存在的边信息则存储，而对于不相邻接的对于图中存在的边信息则存储，而对于不相邻接的顶点则不保留信息顶点则不保留信息。在邻接表中，对图中的每个顶。在邻接表中，对图中的每个顶点建立一个带头结点的边链表，每个边链表的头结点建立一个带头结点的边链表，每个边链表的头结点又构成一个表头结点表。点又构成一个表头结点表。这样，一个这样，一个n个顶点的图的邻接表表示由个顶点的图的邻接表表示由表头结点表表头结点表与与边表边表两部分构成。
24、两部分构成。3/29/202338（1）表头结点表：）表头结点表：由所有表头结点以顺序结构（向由所有表头结点以顺序结构（向量）的形式存储，以便可以随机访问任一顶点的单链量）的形式存储，以便可以随机访问任一顶点的单链表。表。表头结点有两部分构成，其中数据域表头结点有两部分构成，其中数据域（vexdata）用于存储顶点的名或其它有关信息；链）用于存储顶点的名或其它有关信息；链域（域（firstarc）用于指向链表中第一个顶点（即与顶）用于指向链表中第一个顶点（即与顶点点vi邻接的第一个邻接点）。邻接的第一个邻接点）。表头结点结构为：表头结点结构为：vexdatafirstarc3/29/20233
25、9（2）边表：由表示图中顶点间邻接关系的）边表：由表示图中顶点间邻接关系的n个边链个边链表组成。它由三部分组成，表组成。它由三部分组成，其中邻接点域其中邻接点域（adjvex）用于存放与顶点）用于存放与顶点vi相邻接的顶点在图中相邻接的顶点在图中的位置；链域（的位置；链域（nextarc）用于指向与顶点）用于指向与顶点vi相关联相关联的下一条边或弧的结点；数据域（的下一条边或弧的结点；数据域（info）用于存放）用于存放与边或弧相关的信息（如赋权图中每条边或弧的权与边或弧相关的信息（如赋权图中每条边或弧的权值等）。值等）。adjvexinfonextarc弧结点结构为：弧结点结构为：3/29/
26、202340图例图例图图G1、G2的邻接表表示法的邻接表表示法1234ABCD3241（a）G1的邻接表表示法122341245533ABECD12345（b）G2的邻接表表示法3/29/202341邻接表存储结构的形式化说明如下：邻接表存储结构的形式化说明如下：#defineMAX_VERTEX_NUM10/*最多顶点个数最多顶点个数*/typedefenumDG,DN,UDG,UDNGraphKind;/*图的种类图的种类*/typedefstructArcNodeintadjvex;/*该弧指向顶点的位置该弧指向顶点的位置*/structArcNode*nextarc;/*指向下一条弧的
27、指针指向下一条弧的指针*/OtherInfoinfo;/*与该弧相关的信息与该弧相关的信息*/ArcNode;3/29/202342typedefstructVertexNodeVertexDatadata;/*顶点数据顶点数据*/ArcNode*firstarc;/*指向该顶点第一条弧的指针指向该顶点第一条弧的指针*/VertexNode;typedefstructVertexNodevertexMAX_VERTEX_NUM;intvexnum,arcnum;/*图的顶点数和弧数图的顶点数和弧数*/GraphKindkind;/*图的种类标志图的种类标志*/AdjList;/*基于邻接表的图
28、基于邻接表的图(AdjacencyListGraph)*/3/29/202343存储空间：存储空间：对于有对于有n个顶点，个顶点，e条边的无向图而言条边的无向图而言，若采取邻接表作为存储结构，则需要若采取邻接表作为存储结构，则需要n个表头结点个表头结点和和2e个表结点个表结点。无向图的度：无向图的度：在无向图的邻接表中，顶点在无向图的邻接表中，顶点vi的度恰的度恰好就是第好就是第i个边链表上结点的个数。个边链表上结点的个数。有向图的度：有向图的度：在有向图中，第在有向图中，第i个边链表上顶点的个边链表上顶点的个数是顶点个数是顶点vi的出度。要想求得该顶点的入度，则的出度。要想求得该顶点的入度，
29、则必须遍历整个邻接表。在所有单链表中查找邻接点必须遍历整个邻接表。在所有单链表中查找邻接点域的值为域的值为i i的结点并计数求和。的结点并计数求和。3/29/202344由此可见，对于用邻接表方式存储的有向图，求顶由此可见，对于用邻接表方式存储的有向图，求顶点的入度并不方便，因此需要有一种解决的方法点的入度并不方便，因此需要有一种解决的方法逆邻接表法逆邻接表法。对图中的每一顶点对图中的每一顶点vi建立一个递邻接表，即对每个顶建立一个递邻接表，即对每个顶点点vi建立一个所有以顶点建立一个所有以顶点vi为弧头的弧的表，这样求为弧头的弧的表，这样求顶点顶点vi的入度即是计算逆邻接表中第的入度即是计算
30、逆邻接表中第i个顶点的边链表个顶点的边链表中结点个数中结点个数。图图G1的逆邻接表表示法见的逆邻接表表示法见p162的图的图7.103/29/202345十字链表十字链表十字十字链表链表(OrthogonalList)是有向图的另一种是有向图的另一种链式存储结构。我们也可以把它看成是将有向图的链式存储结构。我们也可以把它看成是将有向图的邻接表和逆邻接表结合起来形成的一种链表。邻接表和逆邻接表结合起来形成的一种链表。有向图中的每一条弧对应十字链表中的一个有向图中的每一条弧对应十字链表中的一个弧弧结点结点，同时有向图中的每个顶点在十字链表中对应，同时有向图中的每个顶点在十字链表中对应有一个结点，叫
31、做有一个结点，叫做顶点结点顶点结点。这两类结点的结构见图所示。这两类结点的结构见图所示。3/29/202346tailvexheadvexhlinktlinktailvex表示弧尾顶点在图中的位置headvex表示弧头顶点在图中的位置hlink指向与此弧的弧头相同的下一条弧tlink指向与此弧的弧尾相同的下一条弧（a）十字链表弧结点结构示意datafirstinfirstoutdata域用于存储与顶点有关的信息如顶点的名字等firstin域（链域）用于指向以该顶点作为弧头的第一个弧顶点firstout域（链域）用于指向以该顶点作为弧尾的第一个弧顶点（b）十字链表顶点结点结构示意图7.10 图的
32、十字链表弧结点、顶点结点结构图3/29/202347图图G1的十字链表表示的十字链表表示12 1341 ACBD3412343/29/202348建立一个有向图的十字链表的算法如下：建立一个有向图的十字链表的算法如下：void CrtOrthList（OrthList g）/*从从终终端端输输入入n个个顶顶点点的的信信息息和和e条条弧弧的的信信息息，以以建建立立一一个个有有向向图图的的十十字字链链表表*/scanf(“%d,%d”,&n,&e);/*键盘输入图的顶点个数和弧的个数键盘输入图的顶点个数和弧的个数*/for(i=0;in;i+)scanf(“%c”,g.vertexi.data）；
33、）；g.vertexi.firstin=NULL；g.vertexi.firsout=NULL；3/29/202349for(k=0;ktailvex=i；p-headvex=j；p-tlink=g.vertexi.firstout；g.vertexi.firstout=p；p-hlink=hlink=g.vertexj.firstin.firstin；g.vertexj.firstin=p.firstin=p；/*CrtOrthList*/3/29/202350十字链表的优点十字链表的优点：在十字在十字链表中既能够很容易地找到以链表中既能够很容易地找到以vi为尾的为尾的弧，也能够容易地找到以
34、弧，也能够容易地找到以vi为头的弧，因此对于有为头的弧，因此对于有向图，若采用十字链表作为存储结构，则很容易求向图，若采用十字链表作为存储结构，则很容易求出顶点出顶点vi的度。的度。3/29/202351邻接多重表邻接多重表 邻接多重表邻接多重表(AdjacencyMulti_list)是无向图的是无向图的另外一种存储结构。使用邻接多重表这种存储结构另外一种存储结构。使用邻接多重表这种存储结构是是因为它能够提供更为方便的边处理信息因为它能够提供更为方便的边处理信息。邻接邻接多重表多重表是是指将图中关于一条边的信息用一指将图中关于一条边的信息用一个结点来表示个结点来表示。邻接多重表中的边结点结构
35、和顶点结点结构邻接多重表中的边结点结构和顶点结点结构3/29/202352markivexilinkjvexjlink标志域：可用以标记该条边是否被搜索过ivex和jvex：为该边依附的两个顶点在图中的位置ilink（链域）：用于指向下一条依附于顶点ivex的边jlink（链域）：用于指向下一条依附于顶点jvex的边（a）邻接多重表中边结点的结构datafirstedgedata域用于存储与顶点有关的信息，如顶点的名字firstdege域（链域）用于指向第一条依附于该顶点的边（b）邻接多重表中顶点结点的结构 图7.12 邻接多重表的结点结构3/29/202353邻接多重表的结构类型说明如下：邻
36、接多重表的结构类型说明如下：typedefstructEdgeNodeintmark,ivex,jvex;structEdgeNode*ilink,*jlink;EdgeNode;typedefstructVertexDatadata;EdgeNode*firstedge;VertexNode;3/29/202354typedefstructVertexNodevertexMAX_VERTEX_NUM;intvexnum,arcnum;/*图的顶点数和弧数图的顶点数和弧数*/GraphKindkind;/*图的种类图的种类*/AdjMultiList;/*基于图的邻接多重表表示法基于图的邻接多
37、重表表示法(AdjacencyMulti_list)*/图图G2的邻接多重表见图所示。的邻接多重表见图所示。3/29/202355ABDC121 432353452E图7.13 无向图的邻接多重表表示3/29/2023567.4图的遍历图的遍历图的遍历图的遍历：从：从图中的某个顶点出发，按某种方法对图中的某个顶点出发，按某种方法对图中的所有顶点访问且仅访问一次。图中的所有顶点访问且仅访问一次。为了保证图中为了保证图中的各顶点在遍历过程中访问且仅的各顶点在遍历过程中访问且仅访问一次，需要为每个顶点设一个访问标志，用以访问一次，需要为每个顶点设一个访问标志，用以标示图中每个顶点是否被访问过，访问标
38、志用数组标示图中每个顶点是否被访问过，访问标志用数组visitedn来表示来表示。图的遍历方法有两种：图的遍历方法有两种：深度优先搜索深度优先搜索和和广度优先搜索广度优先搜索3/29/202357深度优先搜索：深度优先搜索：深度优先搜索深度优先搜索（Depth_FirstSearch）是指按照）是指按照深度深度方向搜索方向搜索，它类似于树的先根遍历。，它类似于树的先根遍历。深度优先算法的基本思想是：深度优先算法的基本思想是：（1）从图中某个顶点）从图中某个顶点v0出发，首先访问出发，首先访问v0。（2）找出刚访问过的顶点）找出刚访问过的顶点vi的第一个未被访问的邻的第一个未被访问的邻接点，然后
39、访问该顶点。重复此步骤，直到当前的接点，然后访问该顶点。重复此步骤，直到当前的顶点没有未被访问的邻接点为止。顶点没有未被访问的邻接点为止。（3）返回前一个访问过的顶点，找出该顶点的下一返回前一个访问过的顶点，找出该顶点的下一个未被访问的邻接点，访问该顶点。转个未被访问的邻接点，访问该顶点。转2。3/29/202358采用递归的形式说明，采用递归的形式说明，则深度优先搜索连通子图的则深度优先搜索连通子图的的基本思想可表示为：的基本思想可表示为：（1）访问出发点访问出发点v0。（2）依次）依次以以v0的未被访问的邻接点为出发点，深度的未被访问的邻接点为出发点，深度优先搜索图，直至图中所有与优先搜索
40、图，直至图中所有与v0有路径相通的顶点有路径相通的顶点都被访问。都被访问。若此时图中还有顶点未被访问，则另选图中一若此时图中还有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述深度优先个未被访问的顶点作为起始点，重复上述深度优先搜索过程，直至图中所有顶点均被访问过为止。搜索过程，直至图中所有顶点均被访问过为止。3/29/202359深度优先搜索的过程示例见深度优先搜索的过程示例见p167的的7.15图所示图所示。其中实箭头代表访问方向，虚箭头代表回溯方向，其中实箭头代表访问方向，虚箭头代表回溯方向，箭头旁边的数字代表搜索顺序，箭头旁边的数字代表搜索顺序，A为起始顶点。为起始顶点。
41、8ADGBEHCFI1236710114155149131216访问序列为：访问序列为：A、B、C、F、E、G、D、H、I。3/29/202360图的深度优先搜索的算法描述如下：图的深度优先搜索的算法描述如下：#defineTrue1#defineFalse0#defineError1/*出错出错*/#defineOk1intvisitedMAX_VERTEX_NUM;/*访问标志数组访问标志数组*/3/29/202361voidTraverseGraphTraverseGraph(Graphg)/*对对图图g进进行行深深度度优优先先搜搜索索，Graph表表示示图图的的一一种种存存储储结结构构
42、，如如数数组组表表示法或邻接表等示法或邻接表等*/for(vi=0;vig.vexnum;vi+)visitedvi=False;/*访问标志数组初始访问标志数组初始*/for(vi=0;vig.vexnum;vi+)/*调用深度遍历连通子图的操作调用深度遍历连通子图的操作*/*若图若图g是连通图，则此循环只执行一次是连通图，则此循环只执行一次*/if(！visitedvi)DepthFirstSearch(g，vi)；/*TraverseGraphTraverseGraph*/3/29/202362深度遍历深度遍历v0所在地连通子图算法如下：所在地连通子图算法如下：voidDepthFirs
43、tSearch（Graphg,intv0）/*深度遍历深度遍历v0所在的连通子图所在的连通子图*/visit（v0）；）；visitedv0=True；/*访问顶点访问顶点v0，并置访问标志数组相应分量值，并置访问标志数组相应分量值*/w=FirstAdjVertex(g,v0);while(w!=-1!=-1)/*邻接点存在邻接点存在*/if(!visitedw)DepthFirstSearch(g,w);/*递归调用递归调用DepthFirstSearch*/w=NextAdjVertex(g,v0,w);/*找下一个邻接点找下一个邻接点*/*DepthFirstSearch*/3/29/
44、202363上述算法中上述算法中对于对于FirstAdjVertex（g，v0）以及）以及NextAdjVertex（g，v0，w）并没有具体实现。）并没有具体实现。因为对于图的不同因为对于图的不同存储方法，两个操作的实现方法不同，时间耗费也存储方法，两个操作的实现方法不同，时间耗费也不同。不同。下面的算法是在邻接矩阵与邻接表方式下实现上面下面的算法是在邻接矩阵与邻接表方式下实现上面算法的功能。算法的功能。3/29/2023641）用邻接矩阵方式实现深度优先搜索）用邻接矩阵方式实现深度优先搜索voidDepthFirstSearch(AdjMatrixg,intv0)/*图图g为为邻接矩阵类型
45、邻接矩阵类型AdjMatrix*/visit(v0);visitedv0=True;for(vj=0;vjadjvex)DepthFirstSearch（g，p-adjvex）；）；p=p-nextarc-nextarc；/*DepthFirstSearch*/3/29/202366分析算法分析算法：以邻接表作为存储结构，查找每个顶点：以邻接表作为存储结构，查找每个顶点的邻接点的时间复杂度为的邻接点的时间复杂度为O(e)，其中其中e是无向图中是无向图中的边数或有向图中弧数的边数或有向图中弧数,则深度优先搜索图的时间则深度优先搜索图的时间复杂度为复杂度为O(n+e)。3/29/2023673）用
46、非递归过程实现深度优先搜索）用非递归过程实现深度优先搜索voidDepthFirstSearch(Graphg,intv0)/*从从v0出发深度优先搜索图出发深度优先搜索图g*/InitStack(S);/*初始化空栈初始化空栈*/Push(S,v0)；while(!Empty(S)v=Pop(S);if(!visited(v)/*if(!visited(v)/*栈中可能有重复结点栈中可能有重复结点*/*/visit(v);visitedv=True;w=FirstAdj(g,v);/*求求v的第一个邻接点的第一个邻接点*/while(w!=-1)if(!visited(if(!visited
47、(w)Push(S,)Push(S,w););w=NextAdj(g,=NextAdj(g,v,w);/*求求v相对于相对于w的下一个邻接点的下一个邻接点*/3/29/2023687.3.2广度优先搜索广度优先搜索广度优先搜索广度优先搜索（Breadth_FirstSearch）是指）是指按照广按照广度方向搜索度方向搜索，它类似于树的按层次遍历，它类似于树的按层次遍历。广度优先搜索的基本思想是：广度优先搜索的基本思想是：（1）从图中某个顶点从图中某个顶点v0出发，首先访问出发，首先访问v0。（2）依次访问依次访问v0的各个未被访问的邻接点。的各个未被访问的邻接点。（3）分别从这些邻接点（端结点
48、）出发，依次访问分别从这些邻接点（端结点）出发，依次访问它们的各个未被访问的邻接点（新的端结点）。它们的各个未被访问的邻接点（新的端结点）。3/29/202369 访问时应保证：如果访问时应保证：如果Vi和和Vk为当前端结点，且为当前端结点，且Vi在在Vk之前被访问，则之前被访问，则Vi的所有未被访问的邻接点的所有未被访问的邻接点应在应在Vk的所有未被访问的邻接点之前访问。重复的所有未被访问的邻接点之前访问。重复（3），直到所有端结点均没有未被访问的邻接点），直到所有端结点均没有未被访问的邻接点为止。为止。若此时还有顶点未被访问，则选一个未被访问若此时还有顶点未被访问，则选一个未被访问的顶点作
49、为起始点，重复上述过程，直至所有顶点的顶点作为起始点，重复上述过程，直至所有顶点均被访问过为止。均被访问过为止。3/29/202370广度优先搜索过程示例见广度优先搜索过程示例见p169的图的图7.16所示。所示。其中其中箭头代表搜索方向，箭头旁边的数字代表搜索顺序，箭头代表搜索方向，箭头旁边的数字代表搜索顺序，A为起始顶点。为起始顶点。ADGBEHCFI14657823访问序列为：访问序列为：A、B、E、D、C、G、F、H、I。3/29/202371广度优先搜索连通子图的算法如下：广度优先搜索连通子图的算法如下：voidBreadthFirstSearch(Graphg,intv0)/*广度
50、优先搜索图广度优先搜索图g中中v0所在的连通子图所在的连通子图*/visit(v0);visitedv0=True;InitQueue(&Q);/*初始化空队初始化空队*/EnterQueue(&Q,v0)；/*v0进队进队*/while(!Empty(Q)DeleteQueue(&Q,&v);/*队头元素出队队头元素出队*/w=FirstAdj(g,v);/*求求v的第一个邻接点的第一个邻接点*/3/29/202372while(w!=-1)-1)if(!visited(if(!visited(w)visit(visit(w);visited);visitedw=True;=True;Ent