零基础学数据结构第10章.ppt

《零基础学数据结构第10章.ppt》由会员分享，可在线阅读，更多相关《零基础学数据结构第10章.ppt（93页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第10章章图图图图(graph)是是一一种种比比线线性性表表、树树更更为为复复杂杂的的数数据据结结构构。在在线线性性表表中中，数数据据元元素素之之间间呈呈线线性性关关系系，即即每每个个元元素素只只有有一一个个直直接接前前驱驱和和一一个个直直接接后后继继。图图的的应应用用领领域域十十分分广广泛泛，如如化化学学分分析析、工工程程设设计计、遗遗传传学学、人人工工智智能能等等。本本章章主主要要介介绍绍图图的的定定义义、图图的的存存储储结结构构、图图的的遍遍历历、最小生成树、关键路径和最短路径。最小生成树、关键路径和最短路径。本章重点：本章重点：1 1、图的定义及性质、图的定义及性质 2 2、图的邻接

2、矩阵和邻接表表示、图的邻接矩阵和邻接表表示 3 3、图的各种遍历、图的各种遍历 4 4、最小生成树、最小生成树 5 5、关键路径、关键路径 6 6、最短路径、最短路径10.1图的定义与相关概念图的定义与相关概念图图G也是由数据元素集合也是由数据元素集合V与边的集合与边的集合E构成的。在图中，数据元构成的。在图中，数据元素通常称为顶点（素通常称为顶点（Vertex）。其中，顶点集合）。其中，顶点集合V不能为空，边表示不能为空，边表示顶点之间的关系。顶点之间的关系。若若E，则，则表示从顶点表示从顶点x到顶点到顶点y存在一条弧存在一条弧（Arc），），x称为弧尾（称为弧尾（tail）或起始点（）或起

3、始点（initialnode），），y称为弧称为弧头（头（head）或终端点（）或终端点（terminalnode）。这样的图被称为有向图）。这样的图被称为有向图（digraph）。）。如果如果E且有且有E，即，即E是对称的，则用无序对是对称的，则用无序对(x,y)代替有序对代替有序对和和，表示，表示x与与y之间存在一条边之间存在一条边（edge），这样的图称为无向图（），这样的图称为无向图（undigraph）。如图）。如图10.1所示。所示。10.1图的定义与相关概念图的定义与相关概念图图G的形式化定义为：的形式化定义为：G=(V,E)，其中，其中，V=x|x数据元素集数据元素集合合，E=

4、|Path(x,y)/(xV,yV)。Path(x,y)表示表示的意义或信息。的意义或信息。在图在图10.1中，有向图中，有向图G1可以表示为可以表示为G1=(V1,E1)，其中，顶点的，其中，顶点的集合为集合为V1=a,b,c,d，边的集合为，边的集合为E1=,。无向图。无向图G2可可以表示为以表示为G2=(V2,E2)，其中，顶点的集合为，其中，顶点的集合为V2=a,b,c,d，边的集，边的集合为合为E2=(a,b),(a,c),(a,d),(b,c),(c,d)。10.1图的定义与相关概念图的定义与相关概念1邻接点邻接点对于无向图对于无向图G=(V,E)，若边，若边(vi,vj)E，则称

5、，则称vi和和vj互为邻接点互为邻接点（adjacent），即），即vi和和vj相邻接。边相邻接。边(vi,vj)依附于顶点依附于顶点vi和和vj，或，或者说者说(vi,vj)与顶点与顶点vi、vj相关联。对于有向图相关联。对于有向图G=(V,A)，若弧，若弧A，则称顶点，则称顶点vi邻接到顶点邻接到顶点vj，顶点，顶点vj邻接自顶点邻接自顶点vi。弧。弧和顶点和顶点vi、vj相关联。相关联。无向图无向图G2的边的集合为的边的集合为E=(a,b),(a,c),(a,d),(b,c),(c,d)，顶点顶点a和和b互为邻接点，边互为邻接点，边(a,b)依附于顶点依附于顶点a和和b。顶点。顶点c和和

6、d互为邻互为邻接点，边接点，边(c,d)依附于顶点依附于顶点c和和d。有向图。有向图G1的弧的集合为的弧的集合为A=,，顶点，顶点a邻接到邻接到顶点顶点b，弧，弧与顶点与顶点a和和b相关联。顶点相关联。顶点c邻接自顶点邻接自顶点d，弧，弧与顶点与顶点d和和c相关联。相关联。10.1图的定义与相关概念图的定义与相关概念2顶点的度顶点的度对于无向图，顶点对于无向图，顶点v的度是指与的度是指与v相关联的边的数目，记作相关联的边的数目，记作TD(v)。对于。对于有向图，以顶点有向图，以顶点v为弧头的数目称为顶点为弧头的数目称为顶点v的入度的入度(indegree)，记作，记作ID(v)。以顶点。以顶点

7、v为弧尾的数目称为为弧尾的数目称为v的出度的出度(outdegree)，记作，记作OD(v)。顶点。顶点v的度的度(degree)为为TD(v)=ID(v)+OD(v)。无向图无向图G2中顶点中顶点a的度为的度为3，顶点，顶点b的度为的度为2，顶点，顶点c的度为的度为3，顶点，顶点d的度的度为为2。有向图。有向图G1的弧的集合为的弧的集合为A=,，顶点，顶点a、b、c和和d的入度分别为的入度分别为1、2、2和和1，顶点，顶点a、b、c和和d的出度分别为的出度分别为2、1、2和和1，顶点，顶点a、b、c和和d的度分别为的度分别为3、3、4和和2。若图的顶点的个数为若图的顶点的个数为n，边数或弧数

8、为，边数或弧数为e，顶点，顶点vi的度记作的度记作TD(vi)，则顶，则顶点的度与弧或者边数满足关系：点的度与弧或者边数满足关系：e=10.1图的定义与相关概念图的定义与相关概念3路径路径无向图无向图G中，从顶点中，从顶点v到顶点到顶点v的路径（的路径（path）是从）是从v出发，经出发，经过一系列的顶点序列到达顶点过一系列的顶点序列到达顶点v。如果。如果G是有向图，则路径也是有向是有向图，则路径也是有向的，路径的长度是路径上弧或边的数目。第一个顶点和最后一个顶的，路径的长度是路径上弧或边的数目。第一个顶点和最后一个顶点相同的路径称为回路或环（点相同的路径称为回路或环（cycle）。序列中顶点

9、不重复出现的路）。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点外，其他顶点不径称为简单路径。除了第一个顶点和最后一个顶点外，其他顶点不重复出现的回路，称为简单回路或简单环。重复出现的回路，称为简单回路或简单环。在图在图10.1所示的有向图所示的有向图G1中，顶点序列中，顶点序列adca构成了一构成了一个简单回路。在无向图个简单回路。在无向图G2中，从顶点中，从顶点a到顶点到顶点c所经过的路径为所经过的路径为a，d和和c（或（或a、b、c）。）。10.1图的定义与相关概念图的定义与相关概念4子图子图假设存在两个图假设存在两个图G=V,E和和G=V,E，若，若G的顶点和关系

10、都是的顶点和关系都是V的子集，即有的子集，即有VV，EE，则，则G为为G的子图。如图的子图。如图10.2所示。所示。10.1图的定义与相关概念图的定义与相关概念5连通图和强连通图连通图和强连通图对于无向图对于无向图G，如果从顶点，如果从顶点vi到顶点到顶点vj存在路径，则称存在路径，则称vi到到vj是连通是连通的。如果对于图中任意两个顶点的。如果对于图中任意两个顶点vi、vjV，vi和和vj都是连通的，则称都是连通的，则称G是连通图（是连通图（connectedgraph）。无向图中的极大连通子图称为连通）。无向图中的极大连通子图称为连通分量。无向图分量。无向图G3与连通分量如图与连通分量如图

11、10.3所示。所示。10.1图的定义与相关概念图的定义与相关概念对于有向图对于有向图G，如果对每一对顶点，如果对每一对顶点vi和和vj，且，且vivj，从，从vi到到vj和和vj到到vi都存在路径，则都存在路径，则G为强连通图。有向图中的极大强连通子图称为为强连通图。有向图中的极大强连通子图称为有向图的强连通分量。有向图有向图的强连通分量。有向图G4与强连通分量如图与强连通分量如图10.4所示。所示。10.1图的定义与相关概念图的定义与相关概念6完全图完全图若图的顶点数目是若图的顶点数目是n，图的边（弧）的数目是，图的边（弧）的数目是e。若不存在顶点到。若不存在顶点到自身的边或弧，即若存在自身

12、的边或弧，即若存在，则有，则有vivj。对于无向图，边数。对于无向图，边数e的取值范围为的取值范围为0n(n-1)/2。将具有。将具有n(n-1)/2条边的无向图称为完全条边的无向图称为完全图（图（completedgraph）或无向完全图。对于有向图，弧数）或无向完全图。对于有向图，弧数e的取值的取值范围是范围是0n(n-1)。将具有。将具有n(n-1)条弧的有向图称为有向完全图。条弧的有向图称为有向完全图。10.1图的定义与相关概念图的定义与相关概念7稀疏图和稠密图稀疏图和稠密图具有具有enlogn条弧或边的图，称为稀疏图。反之，称为稠密图。条弧或边的图，称为稀疏图。反之，称为稠密图。8生

13、成树生成树一个连通图的生成树是一个极小连通子图，它含有图的全部顶点，但一个连通图的生成树是一个极小连通子图，它含有图的全部顶点，但只有足以构成一棵树的只有足以构成一棵树的n-1条边。如果在该生成树中添加一条边，则条边。如果在该生成树中添加一条边，则一定会在图中出现一个环。一棵具有一定会在图中出现一个环。一棵具有n个顶点的生成树仅有个顶点的生成树仅有n-1条边，如条边，如果少于果少于n-1条边，则该图是非连通的。多于条边，则该图是非连通的。多于n-1条边，则一定有环的出条边，则一定有环的出现。反过来，具有现。反过来，具有n-1条边的图不一定能构成生成树。一个图的生成树条边的图不一定能构成生成树。

14、一个图的生成树不一定是唯一的。图不一定是唯一的。图10.5是无向图是无向图G5中最大连通分量的一棵生成树。中最大连通分量的一棵生成树。10.1图的定义与相关概念图的定义与相关概念9网网在图的边或弧上，有时标有与它们相关的数，这种与图的边或弧相关在图的边或弧上，有时标有与它们相关的数，这种与图的边或弧相关的数称作权（的数称作权（weight）。这些权可以表示从一个顶点到另一个顶点的）。这些权可以表示从一个顶点到另一个顶点的距离或代价。这种带权的图称作网（距离或代价。这种带权的图称作网（network）。一个网如图）。一个网如图10.6所所示。示。10.1图的定义与相关概念图的定义与相关概念10.

15、1.3 10.1.3 图的抽象数据类型图的抽象数据类型1数据对象集合数据对象集合图的数据对象为图的各个顶点和边的集合。图中的顶点是没有先后次图的数据对象为图的各个顶点和边的集合。图中的顶点是没有先后次序的。图分为有向图和无向图，图中结点之间的关系用弧或边表示，通序的。图分为有向图和无向图，图中结点之间的关系用弧或边表示，通过弧或边相连的顶点相邻接或相关联。过弧或边相连的顶点相邻接或相关联。图中顶点之间是多对多的关系，即任何一个顶点可以有与之邻接或关图中顶点之间是多对多的关系，即任何一个顶点可以有与之邻接或关联的顶点。联的顶点。10.1图的定义与相关概念图的定义与相关概念2基本操作集合基本操作集

16、合（1）CreateGraph(&G)：图的创建。根据顶点和边或弧构造一个图：图的创建。根据顶点和边或弧构造一个图G。（3）DestroyGraph(&T)：销毁图的操作。如果图：销毁图的操作。如果图G存在，则将图存在，则将图G销毁。销毁。（4）LocateVertex(G,v)：返回顶点：返回顶点v在图的位置。在图在图的位置。在图G中查找顶点中查找顶点v，如，如果找到该顶点，返回顶点在图果找到该顶点，返回顶点在图G中的位置。中的位置。（5）GetVertex(G,i)：返回图：返回图G中序号中序号i对应的值。对应的值。i是图是图G某个顶点的序号，某个顶点的序号，返回图返回图G中序号中序号i对

17、应的值。对应的值。（6）FirstAdjVertex(G,v)：返回：返回v的第一个邻接顶点。在图的第一个邻接顶点。在图G中查找中查找v的第一的第一个邻接顶点，并将其返回。如果在个邻接顶点，并将其返回。如果在G中没有邻接顶点，则返回中没有邻接顶点，则返回-1。10.1图的定义与相关概念图的定义与相关概念（7）NextAdjVertex(G,v,w)：返回：返回v的下一个邻接顶点。在图的下一个邻接顶点。在图G中查找中查找v的下一个邻接的下一个邻接顶点，即顶点，即w的第一个邻接顶点，找到返回其值，否则，返回的第一个邻接顶点，找到返回其值，否则，返回-1。（8）InsertVertex(&G,v)：

18、图的顶点插入操作。在图：图的顶点插入操作。在图G中增加新的顶点中增加新的顶点v，并将图的顶，并将图的顶点数增点数增1。（9）DeleteVertex(&G,v)：图的顶点删除操作。将图：图的顶点删除操作。将图G中的顶点中的顶点v及相关联的弧删除。及相关联的弧删除。（10）InsertArc(&G,v,w)：图的弧插入操作。在图：图的弧插入操作。在图G中增加弧中增加弧。对于无向图，。对于无向图，还要插入弧还要插入弧。（11）DeleteArc(&G,v,w)：图的弧删除操作。在图：图的弧删除操作。在图G中删除弧中删除弧。对于无向图，。对于无向图，还要删除弧还要删除弧。（12）DFSTravers

19、eGraph(G)：图的深度遍历操作。从图中的某个顶点出发，对图进行：图的深度遍历操作。从图中的某个顶点出发，对图进行深度遍历。深度遍历。（13）BFSTraverseGraph(G)：图的广度遍历操作。从图中的某个顶点出发，对图进行：图的广度遍历操作。从图中的某个顶点出发，对图进行广度遍历。广度遍历。10.2图的存储结构图的存储结构10.2.1 邻接矩阵（数组表示法）1什么是图的邻接矩阵什么是图的邻接矩阵图的邻接矩阵可利用两个数组实现：一个一维数组用来存储图中的图的邻接矩阵可利用两个数组实现：一个一维数组用来存储图中的顶点信息；另一个二维数组用来存储图中的顶点之间的关系，该二维顶点信息；另一

20、个二维数组用来存储图中的顶点之间的关系，该二维数组被称为邻接矩阵。如果图是一个无权图，则邻接矩阵表示为：数组被称为邻接矩阵。如果图是一个无权图，则邻接矩阵表示为：对于带权图，有对于带权图，有10.2图的存储结构图的存储结构在图在图10.1中，两个图弧和边的集合分别为中，两个图弧和边的集合分别为A=,和和E=(a,b),(a,c),(a,d),(b,c),(c,d)。它们的邻接矩阵表示如图。它们的邻接矩阵表示如图10.7所示。所示。带权图的邻接矩阵表示如图带权图的邻接矩阵表示如图10.8所示。所示。10.2图的存储结构图的存储结构图的邻接矩阵存储结构描述如下：图的邻接矩阵存储结构描述如下：#de

21、fineINFINITY65535/*65535被认为是一个无穷大的值被认为是一个无穷大的值*/#defineMaxSize50/*最大顶点个数最大顶点个数*/typedefenumDG,DN,UG,UNGraphKind;/*图的类型图的类型*/typedefstructVRTypeadj;/*对于无权图，用对于无权图，用1表示相邻，表示相邻，0表示不相邻表示不相邻*/InfoPtr*info;/*与弧或边的相关信息与弧或边的相关信息*/ArcNode,AdjMatrixMaxSizeMaxSize;typedefstruct/*图的类型定义图的类型定义*/VertexTypevexMaxS

22、ize;/*用于存储顶点用于存储顶点*/AdjMatrixarc;/*邻接矩阵，存储边或弧的信息邻接矩阵，存储边或弧的信息*/intvexnum,arcnum;/*顶点数和边（弧）的数目顶点数和边（弧）的数目*/GraphKindkind;/*图的类型图的类型*/MGraph;其中，数组其中，数组vex用于存储图中的顶点信息，如用于存储图中的顶点信息，如a、b、c、d，arcs用于存储图中用于存储图中顶点信息。顶点信息。10.2图的存储结构图的存储结构2邻接矩阵应用举例邻接矩阵应用举例【例例10_1】试编写一个算法，采用邻接矩阵创建一个如图试编写一个算法，采用邻接矩阵创建一个如图10.8所所示

23、的有向网示的有向网G。分析：主要考察图的邻接矩阵表示与算法实现。图的创建包括两分析：主要考察图的邻接矩阵表示与算法实现。图的创建包括两个部分：一个是创建顶点，顶点信息可存储到一个向量（一维数组）个部分：一个是创建顶点，顶点信息可存储到一个向量（一维数组）中；一个是创建弧的信息，包括弧的相关顶点和权值，可存储到二中；一个是创建弧的信息，包括弧的相关顶点和权值，可存储到二维数组中，其中，二维数组的两个下标分别表示两个相关顶点在矩维数组中，其中，二维数组的两个下标分别表示两个相关顶点在矩阵中的行号和列号，权值存入到数组中。阵中的行号和列号，权值存入到数组中。10.2图的存储结构图的存储结构10.2.

24、2 邻接表邻接表（邻接表（adjacencylist）是图的一种链式存储方式。采用邻接表）是图的一种链式存储方式。采用邻接表表示图一般需要两个表结构：边表和表头结点表。表示图一般需要两个表结构：边表和表头结点表。边表：在邻接表中，对图中的每个顶点都建立一个单链表，第边表：在邻接表中，对图中的每个顶点都建立一个单链表，第i个个单链表中的结点表示依附于顶点单链表中的结点表示依附于顶点vi的边（对有向图来说是以顶点的边（对有向图来说是以顶点vi为为尾的弧），这种链表称为边表，其中结点称为弧结点，弧结点由尾的弧），这种链表称为边表，其中结点称为弧结点，弧结点由3个个域组成：邻接点域（域组成：邻接点域（

25、adjvex）、数据域（）、数据域（info）和指针域）和指针域（nextarc）。其中，邻接点域表示与相应的表头顶点邻接点的位置，）。其中，邻接点域表示与相应的表头顶点邻接点的位置，数据域存储与边或弧的信息，指针域用来指示下一个边或弧的结点。数据域存储与边或弧的信息，指针域用来指示下一个边或弧的结点。10.2图的存储结构图的存储结构表头结点表：在每个链表前面设置一个头结点，除了设有存储各表头结点表：在每个链表前面设置一个头结点，除了设有存储各个顶点信息的数据域（个顶点信息的数据域（data）外，还设有指向链表中第一个结点的）外，还设有指向链表中第一个结点的链域（链域（firstarc），我们

26、把这种表称为表头结点表，相应地，结点称），我们把这种表称为表头结点表，相应地，结点称为表头结点。通常情况下，表头结点采用顺序存储结构实现，这样为表头结点。通常情况下，表头结点采用顺序存储结构实现，这样可以随机地访问任意顶点。可以随机地访问任意顶点。边表结点和表头结点的结构如图边表结点和表头结点的结构如图10.10所示。所示。10.2图的存储结构图的存储结构图图10.1所示的图所示的图G1和和G2用邻接表表示如图用邻接表表示如图10.11所示。所示。图图10.8所示的带权图的邻接表如图所示的带权图的邻接表如图10.12所示。所示。10.2图的存储结构图的存储结构图的邻接表存储结构描述如下：图的邻

27、接表存储结构描述如下：#defineMaxSize50/*最大顶点个数最大顶点个数*/typedefenumDG,DN,UG,UNGraphKind;/*图的类型：有向图、有向图的类型：有向图、有向网、无向图和无向网网、无向图和无向网*/typedefstructArcNode/*边结点的类型定义边结点的类型定义*/intadjvex;/*弧指向的顶点的位置弧指向的顶点的位置*/InfoPtr*info;/*与弧相关的信息与弧相关的信息*/structArcNode*nextarc;/*指示下一个与该顶点相邻接的顶点指示下一个与该顶点相邻接的顶点*/ArcNode;typedefstructV

28、Node/*头结点的类型定义头结点的类型定义*/VertexTypedata;/*用于存储顶点用于存储顶点*/ArcNode*firstarc;/*指示第一个与该顶点邻接的顶点指示第一个与该顶点邻接的顶点*/VNode,AdjListMaxSize;10.2图的存储结构图的存储结构typedefstruct/*图的类型定义图的类型定义*/AdjListvertex;intvexnum,arcnum;/*图的顶点数目与弧的数目图的顶点数目与弧的数目*/GraphKindkind;/*图的类型图的类型*/AdjGraph;如果无向图如果无向图G中有中有n个顶点和个顶点和e条边，则图采用邻接表表示，

29、需要条边，则图采用邻接表表示，需要n个头结点和个头结点和2e个表结点。在个表结点。在e远小于远小于n(n-1)/2时，采用邻接表存储表时，采用邻接表存储表示显然要比采用邻接矩阵表示更能节省空间。示显然要比采用邻接矩阵表示更能节省空间。10.2图的存储结构图的存储结构有有时时为为了了便便于于求求某某个个顶顶点点的的入入度度，需需要要建建立立一一个个有有向向图图的的逆逆邻邻接接链链表表，也也就就是是为为每每个个顶顶点点vi建建立立一一个个以以vi为为弧弧头头的的链链表表。在在邻邻接接表表中中，边边表表结结点点的的邻邻接接点点域域的的值值为为i的的个个数数，就就是是顶顶点点vi的的入入度度。因因此此

30、如如果果要要求求某某个个顶顶点点的的入入度度，则则需需要要对对整整个个邻邻接接表表进进行行遍遍历历。图图10.1所示的有向图所示的有向图G1的逆邻接链表如图的逆邻接链表如图10.13所示。所示。10.2图的存储结构图的存储结构【例例10_2】编写一个创建如图编写一个创建如图10.1所示的无向图（假设采用邻接表表示图所示的无向图（假设采用邻接表表示图）。）。分析：主要考察图的邻接表存储结构。图的创建包括两个部分：创建表头分析：主要考察图的邻接表存储结构。图的创建包括两个部分：创建表头结点和边表结点。其中，表头结点利用一个数组实现，数组包括两个域：一结点和边表结点。其中，表头结点利用一个数组实现，

31、数组包括两个域：一个保存顶点的值；一个是指针，用于指向与顶点相关联的顶点对应结点。代个保存顶点的值；一个是指针，用于指向与顶点相关联的顶点对应结点。代码如下：码如下：for(i=0;ivexnum;i+)/*将顶点存储在表头结点中将顶点存储在表头结点中*/scanf(%s,G-vertexi.data);G-vertexi.firstarc=NULL;/*将相关联的顶点置为空将相关联的顶点置为空*/10.2图的存储结构图的存储结构10.2.3 十字链表十字链表（十字链表（orthogonallist）是有向图的另一种链式存储结构，）是有向图的另一种链式存储结构，它可以看作是将有向图的邻接表与逆

32、邻接链表结合起来的得到的一它可以看作是将有向图的邻接表与逆邻接链表结合起来的得到的一种链表。在十字链表中，对应于有向图中每一条弧有一个结点，对种链表。在十字链表中，对应于有向图中每一条弧有一个结点，对应于每个顶点也有一个结点，这些结点的结构如图应于每个顶点也有一个结点，这些结点的结构如图10.15所示。所示。弧结点包含弧结点包含5个域：尾域个域：尾域tailvex、头域、头域headvex、infor域和两个域和两个指针域指针域hlink、tlink。其中，尾域。其中，尾域tailvex用于表示弧尾顶点在图中用于表示弧尾顶点在图中的位置，头域的位置，头域headvex表示弧头顶点在图中的位置，

33、表示弧头顶点在图中的位置，info域表示弧域表示弧的相关信息，指针域的相关信息，指针域hlink指向弧头相同的下一个条弧，指向弧头相同的下一个条弧，tlink指向弧指向弧尾相同的下一条弧。尾相同的下一条弧。10.2图的存储结构图的存储结构顶点结点包含顶点结点包含3个域：个域：data域和域和firstin、firstout域，其中，域，其中，data域域存储与顶点相关的信息，如顶点的名称，存储与顶点相关的信息，如顶点的名称，firstin和和firstout是两个指针是两个指针域，分别指向以该顶点为弧头和弧尾的第一个弧度结点。域，分别指向以该顶点为弧头和弧尾的第一个弧度结点。有向图有向图G1的

34、十字链表存储表示如图的十字链表存储表示如图10.16所示。所示。10.2图的存储结构图的存储结构有向图的十字链表存储结构描述如下：有向图的十字链表存储结构描述如下：#defineMaxSize50/*最大顶点个数最大顶点个数*/typedefstructArcNode/*弧结点的类型定义弧结点的类型定义*/intheadvex,tailvex;/*弧的头顶点和尾顶点位置弧的头顶点和尾顶点位置*/InfoPtr*info;/*与弧相关的信息与弧相关的信息*/struct*hlink,*tlink;/*指示弧头和弧尾相同的结点指示弧头和弧尾相同的结点*/ArcNode;typedefstructV

35、Node/*顶点结点的类型定义顶点结点的类型定义*/VertexTypedata;/*用于存储顶点用于存储顶点*/ArcNode*firstin,*firstout;/*分别指向顶点的第一条入弧和出弧分别指向顶点的第一条入弧和出弧*/VNode;typedefstruct/*图的类型定义图的类型定义*/VNodevertexMaxSize;intvexnum,arcnum;/*图的顶点数目与弧的数目图的顶点数目与弧的数目*/OLGraph;10.2图的存储结构图的存储结构10.2.4 10.2.4 邻接多重链表邻接多重链表邻接多重链表（邻接多重链表（adjacencymultilist）是无向

36、图的另一种链式）是无向图的另一种链式存储结构。在无向图的邻接表存储表示中，虽然很容易求得顶点和存储结构。在无向图的邻接表存储表示中，虽然很容易求得顶点和边的各种信息，但是对于每一条边（边的各种信息，但是对于每一条边（vi，vj）都有两个结点，分别在）都有两个结点，分别在第第i个和第个和第j个链表中，这给图的某些操作带来不变，例如，要删除一个链表中，这给图的某些操作带来不变，例如，要删除一条边，此时需要找到表示同一条边的两个顶点。因此，在进行这一条边，此时需要找到表示同一条边的两个顶点。因此，在进行这一类操作时，采用邻接多重链表比较合适，邻接多重链表是将图的一类操作时，采用邻接多重链表比较合适，

37、邻接多重链表是将图的一条边用一个结点表示。它的结点结构如图条边用一个结点表示。它的结点结构如图10.17所示。所示。10.2图的存储结构图的存储结构无向图无向图G2的多重链表如图的多重链表如图10.18所示。所示。10.2图的存储结构图的存储结构无向图的多重链表存储结构描述如下：无向图的多重链表存储结构描述如下：#defineMaxSize50/*最大顶点个数最大顶点个数*/typedefstructEdgeNode/*边结点的类型定义边结点的类型定义*/intmark,ivex,jvex;/*访问标志和边的两个顶点位置访问标志和边的两个顶点位置*/InfoPtr*info;/*与边相关的信息

38、与边相关的信息*/struct*ilink,*jlink;/*指示与边顶点相同的结点指示与边顶点相同的结点*/EdgeNode;typedefstructVNode/*顶点结点的类型定义顶点结点的类型定义*/VertexTypedata;/*用于存储顶点用于存储顶点*/EdgeNode*firstedge;/*指向依附于顶点的第一条边指向依附于顶点的第一条边*/VexNode;typedefstruct/*图的类型定义图的类型定义*/VexNodevertexMaxSize;intvexnum,edgenum;/*图的顶点数目与边的数目图的顶点数目与边的数目*/AdjMultiGraph;10

39、.3图的遍历图的遍历与树的遍历类似，我们希望从图中某一顶点出发访遍图中其余顶与树的遍历类似，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。这一过程就叫做图的遍历点，且使每一个顶点仅被访问一次。这一过程就叫做图的遍历（traversinggraph）。）。10.3.1 图的深度优先搜索1什么是图的深度搜索什么是图的深度搜索图的深度优先搜索（图的深度优先搜索（depth_firstsearch）遍历类似于树的先）遍历类似于树的先根遍历，是树的先根遍历的推广。图的深度优先遍历的思想是：假根遍历，是树的先根遍历的推广。图的深度优先遍历的思想是：假设初始状态是图中所有顶点未曾被

40、访问，从图中某个顶点设初始状态是图中所有顶点未曾被访问，从图中某个顶点v0出发，出发，访问顶点访问顶点v0。然后依次从。然后依次从v0的未被访问的邻接点出发深度优先遍历的未被访问的邻接点出发深度优先遍历图，直至图中所有和图，直至图中所有和v0有路径相通的顶点都被访问到；若此时图中有路径相通的顶点都被访问到；若此时图中还有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，还有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复执行上述过程，直到图中所有的顶点都被访问过。重复执行上述过程，直到图中所有的顶点都被访问过。10.3图的遍历图的遍历图图的的深深度度优优先先搜搜索索遍遍历历过过程

41、程如如图图10.18所所示示。实实箭箭头头表表示示访访问问顶顶点的方向，虚箭头表示回溯，数字表示访问或回溯的次序。点的方向，虚箭头表示回溯，数字表示访问或回溯的次序。10.3图的遍历图的遍历2图的深度优先搜索遍历的算法实现图的深度优先搜索遍历的算法实现图的深度优先遍历（邻接表实现）的算法描述如下。图的深度优先遍历（邻接表实现）的算法描述如下。intvisitedMaxSize;/*访问标志数组访问标志数组*/voidDFSTraverse(AdjGraphG)/*从第从第1个顶点起，深度优先搜索遍历图个顶点起，深度优先搜索遍历图G*/intv;for(v=0;vG.vexnum;v+)visi

42、tedv=0;/*访问标志数组初始化为未被访问访问标志数组初始化为未被访问*/for(v=0;v=0;w=NextAdjVertex(G,G.vertexv.data,G.vertexw.data)if(!visitedw)DFS(G,w);/*递归调用递归调用DFS对对v的尚未访的尚未访问的序号为问的序号为w的邻接顶点的邻接顶点*/10.3图的遍历图的遍历如如果果该该图图是是一一个个无无向向连连通通图图或或者者该该图图是是一一个个强强连连通通图图，则则只只需需要要调调 用用 一一 次次 DFS(G,v)就就 可可 以以 遍遍 历历 整整 个个 图图，否否 则则 需需 要要 多多 次次 调调

43、用用DFS(G,v)。在在 遍遍 历历 图图 时时，对对 图图 中中 的的 每每 个个 顶顶 点点 至至 多多 调调 用用 一一 次次DFS(G,v)函函数数，因因为为一一旦旦某某个个顶顶点点被被标标志志为为已已被被访访问问，就就不不再再从从它它出出发发进进行行搜搜索索。因因此此，遍遍历历图图的的过过程程实实质质上上是是对对每每个个顶顶点点查查找找其其邻邻接接点点的的过过程程。其其时时间间耗耗费费取取决决于于所所采采用用的的存存储储结结构构。当当用用二二维维数数组组表表示示邻邻接接矩矩阵阵作作为为图图的的存存储储结结构构时时，查查找找每每个个顶顶点点的的邻邻接接点点所所需需时时间间为为O(n2

44、)，其其中中n为为图图中中的的顶顶点点数数。当当以以邻邻接接表表作作为为图图的的存存储储结结构构时时，查查找找邻邻接接点点的的时时间间为为O(e)，其其中中，e为为无无向向图图边边的的数数目目或或有有向向图图弧弧的的数数目目。由由此此，当当以以邻邻接接表表作作为为存存储储结结构构时时，深深度度优优先先搜搜索索遍遍历图的时间复杂度为历图的时间复杂度为O(n+e)。10.3图的遍历图的遍历另一种写法是：另一种写法是：voidDFS(AdjGraphG,intv)/*从顶点从顶点v出发递归深度优先搜索遍历图出发递归深度优先搜索遍历图G*/ArcNode*p;visitedv=1;/*访问标志设置为已

45、访问访问标志设置为已访问*/Visit(G.vertexv.data);/*访问第访问第v个顶点个顶点*/p=G.vertexv.firstarc;/*取取v的边表头指针，的边表头指针，p指向指向v的邻接点的邻接点*/while(p)/*依次搜索依次搜索v的邻接点的邻接点*/if(!visitedp-adjvex)/*若若v尚未被访问尚未被访问*/DFS(G,p-adjvex);/*以以v的邻接点纵深搜索的邻接点纵深搜索*/p=p-nextarc;/*找找v的下一个邻接点的下一个邻接点*/10.3图的遍历图的遍历以邻接表作为存储结构，查找以邻接表作为存储结构，查找v的第一个邻接点的算法实现如下

46、。的第一个邻接点的算法实现如下。intFirstAdjVertex(AdjGraphG,VertexTypev)/*返回顶点返回顶点v的第一个邻接顶点的序号的第一个邻接顶点的序号*/ArcNode*p;intv1;v1=LocateVertex(G,v);/*v1为顶点为顶点v在图在图G中的序号中的序号*/p=G.vertexv1.firstarc;if(p)/*如果顶点如果顶点v的第一的第一个邻接点存在，返回邻接点的序号，否则返回个邻接点存在，返回邻接点的序号，否则返回-1*/returnp-adjvex;elsereturn-1;10.3图的遍历图的遍历以邻接表作为存储结构，查找以邻接表作

47、为存储结构，查找v的相对于的相对于w的下一个邻接点的算法实现如下。的下一个邻接点的算法实现如下。intNextAdjVertex(AdjGraphG,VertexTypev,VertexTypew)/*返回返回v的相对于的相对于w的下一个邻接顶点的序号的下一个邻接顶点的序号*/ArcNode*p,*next;intv1,w1;v1=LocateVertex(G,v);/*v1为顶点为顶点v在图在图G中的序号中的序号*/w1=LocateVertex(G,w);/*w1为顶点为顶点w在图在图G中的序号中的序号*/for(next=G.vertexv1.firstarc;next;)if(next

48、-adjvex!=w1)next=next-nextarc;p=next;/*p指向顶点指向顶点v的邻接顶点的邻接顶点w的结点的结点*/if(!p|!p-nextarc)/*如果如果w不存在或不存在或w是最后一个邻接点，是最后一个邻接点，则返回则返回-1*/return-1;elsereturnp-nextarc-adjvex;/*返回返回v的相对于的相对于w的下一个邻的下一个邻接点的序号接点的序号*/10.3图的遍历图的遍历10.3.2 图的广度优先搜索1什么是图的广度优先搜索遍历什么是图的广度优先搜索遍历图的广度优先搜索图的广度优先搜索(breadth_firstsearch)遍历类似于树

49、的层次遍历类似于树的层次遍历过程。图的广度优先搜索遍历的思想是：从图的某个顶点遍历过程。图的广度优先搜索遍历的思想是：从图的某个顶点v出发，出发，在访问了在访问了v之后依次访问之后依次访问v的各个未曾访问过的邻接点，然后分别从的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问他们的邻接点，并使这些邻接点出发依次访问他们的邻接点，并使“先被访问的顶点的先被访问的顶点的邻接点邻接点”先于先于“后被访问的顶点的邻接点后被访问的顶点的邻接点”被访问，直至图中所有被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有顶点未被访已被访问的顶点的邻接点都被访问到。若此时图中还有顶点未被

50、访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中的所有顶点都被访问到为止。直至图中的所有顶点都被访问到为止。10.3图的遍历图的遍历 例如，图例如，图G6的广度优先搜索遍历的过程如图的广度优先搜索遍历的过程如图10.19所示。其中，所示。其中，箭头表示广度遍历的方向，旁边的数字表示遍历的次序。箭头表示广度遍历的方向，旁边的数字表示遍历的次序。因此，图因此，图G6的广度优先搜索遍历序列为的广度优先搜索遍历序列为a、b、c、d、e、f、g、h、i。10.3图的遍历图的遍历2图的广度优先遍历的算法实现图的广度优先遍历的