零基础学数据结构第10章课件

《零基础学数据结构第10章课件》由会员分享，可在线阅读，更多相关《零基础学数据结构第10章课件（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.

24、2.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;typedefstruc

28、tVNode/*头结点的类型定义头结点的类型定义*/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是两个指针是两个指针域，分别指向以该顶点为弧头和弧尾的第一个弧度结点。域，分别指向以该顶点为弧头和弧尾的第一个弧度结点。有向图有向

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

35、uctVNode/*顶点结点的类型定义顶点结点的类型定义*/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;/*图的顶点数目与边的数目图的顶点数目与边的数目*/AdjMultiGrap

39、h;10.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+)

42、visitedv=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)函函数数，因因为为一一旦旦某某个个顶顶点点被被标标志志为为已已被被访访问问，就就不不再再从从它它出出发发进进行行搜搜索索。因因此此，遍遍历历图图的的过过程程实实质质上上是是对对每每个个顶顶点点查查找找其其邻邻接接点点的的过过程程。其其时时间间耗耗费费取取决决于于所所采采用用的的存存储储结结构构。当当用用二二维维数数组组表表示示邻邻接接矩矩阵阵作作为为图图的的存存储储结结构构时时，查查找找每每个个顶顶点点的的邻邻接接点点所所需需时时间间为为

44、O(n2)，其其中中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(

48、next-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图的广度优先遍历的算法实现图的广度优

51、先遍历的算法实现与深度优先搜索类似，在图的广度优先的遍历过程中也需要一个与深度优先搜索类似，在图的广度优先的遍历过程中也需要一个访问标志数组访问标志数组visitedMaxSize，用来表示顶点是否被访问过。初，用来表示顶点是否被访问过。初始时，将图中的所有顶点的标志数组始时，将图中的所有顶点的标志数组visitedvi都初始化为都初始化为0，表，表示顶点未被访问。从第示顶点未被访问。从第1个顶点个顶点v0出发，访问该顶点并将标志数组置出发，访问该顶点并将标志数组置为为1。然后将。然后将v0入队，当队列不为空时，将队头元素（顶点）出队，入队，当队列不为空时，将队头元素（顶点）出队，依次访问该顶

52、点的所有邻接点，同时将标志数组对应位置为依次访问该顶点的所有邻接点，同时将标志数组对应位置为1，并将，并将其邻接点依次入队。依次类推，直到图中的所有顶点都已被访问过。其邻接点依次入队。依次类推，直到图中的所有顶点都已被访问过。10.3图的遍历图的遍历图的广度优先搜索遍历的算法实现如下。图的广度优先搜索遍历的算法实现如下。voidBFSTraverse(AdjGraphG)/*从第从第1个顶点出发，按广度优先非递归遍历图个顶点出发，按广度优先非递归遍历图G*/intv,front,rear;ArcNode*p;intqueueMaxSize;/*定义一个队列定义一个队列Q*/front=rear

53、=-1;/*初始化队列初始化队列Q*/for(v=0;vG.vexnum;v+)/*初始化标志位初始化标志位*/visitedv=0;v=0;visitedv=1;/*设置访问标志为设置访问标志为1，表示已经被访问过，表示已经被访问过*/Visit(G.vertexv.data);rear=(rear+1)%MaxSize;10.3图的遍历图的遍历queuerear=v;/*v入队列入队列*/while(frontadjvex=0)/*如果该顶点未被访问过如果该顶点未被访问过*/visitedp-adjvex=1;Visit(G.vertexp-adjvex.data);rear=(rear+

54、1)%MaxSize;queuerear=p-adjvex;p=p-nextarc;/*p指向下一个邻接点指向下一个邻接点*/10.3图的遍历图的遍历10.3.3 图的遍历应用举例【例【例10_3】编写一个算法，要求对图】编写一个算法，要求对图10.18中的无向图中的无向图G6进行进行深度优先搜索遍历和广度优先搜索遍历（假设图采用邻接表存储）。深度优先搜索遍历和广度优先搜索遍历（假设图采用邻接表存储）。10.4图的连通性问题图的连通性问题10.4.1 无向图的连通分量与最小生成树在对无向图进行遍历时，对于连通图，仅需从图的任何一个顶在对无向图进行遍历时，对于连通图，仅需从图的任何一个顶点出发，

55、进行深度优先搜索或广度优先搜索，就可访问到图中的所点出发，进行深度优先搜索或广度优先搜索，就可访问到图中的所有顶点。对于非连通图，则需从多个顶点出发进行搜索，而每一次有顶点。对于非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。各个连通分量中的顶点集。10.4图的连通性问题图的连通性问题图图10.3中的非连通图中的非连通图G3的邻接表如图的邻接表如图10.21所示。图所示。图G3是非连通图且有是非连通图且有3个连通分量，因此在对图个连通分量，因此在对图G3进行

56、深度优先遍历时，需要从图的至少进行深度优先遍历时，需要从图的至少3个顶个顶点（顶点点（顶点a、顶点、顶点g和顶点和顶点i）出发，才能完成对图中的每个顶点的访问。对）出发，才能完成对图中的每个顶点的访问。对图图G3进行深度遍历，经过进行深度遍历，经过3次递归调用得到的次递归调用得到的3个序列分别为：（个序列分别为：（1）a、b、c、d、m、e、f；（；（2）g、h；（；（3）i、j、k、l。这。这3个顶点集分别加上依个顶点集分别加上依附于这些顶点的边，就构成了非连通图附于这些顶点的边，就构成了非连通图G3的两个连通分量，如图的两个连通分量，如图10.3（b）所示。所示。10.4图的连通性问题图的

57、连通性问题设设E（G）为为连连通通图图G中中所所有有边边的的集集合合，则则从从图图中中任任一一顶顶点点出出发发遍遍历历图图时时，必必定定将将E(G)分分成成两两个个集集合合T（G）和和B（G），其其中中T（G）是是遍遍历历图图过过程程中中经经过过的的边边的的集集合合，B（G）是是剩剩余余边边的的集集合合。显显然然，T（G）和和图图G中中所所有有顶顶点点一一起起构构成成连连通通图图G的的极极小小连连通通子子图图，根根据据10.1节节的的定定义义，它它是是连连通通图图的的一一棵棵生生成成树树。由由深深度度优优先先搜搜索索得得到到的的为为深深度度优优先先生生成成树树对对于于连连通通图图，由由广广度度

58、优优先先搜搜索索得得到到的的为为广广度度优优先先生生成成树树。图图10.22就就是是对对应应图图G6的的深深度度优优先先生生成成树树和广度优先生成树。和广度优先生成树。10.4图的连通性问题图的连通性问题对对于于非非连连通通图图，从从某某一一个个顶顶点点出出发发，对对图图进进行行深深度度优优先先搜搜索索遍遍历历或或者者广广度度优优先先搜搜遍遍历历，按按照照访访问问路路径径会会得得到到若若干干棵棵生生成成树树，这这些些生生成成树树放放在在一一起起就就构构成成了了森森林林。对对图图G3进进行行深深度度优优先先搜搜索索得得到到的的森森林林如图如图10.23所示。所示。10.4图的连通性问题图的连通性

59、问题10.4.2 最小生成树许多应用问题都是一个求无向连通图的最小生成树问题。假设要许多应用问题都是一个求无向连通图的最小生成树问题。假设要在在n个城市之间铺设光缆，主要目标是要使这个城市之间铺设光缆，主要目标是要使这n个城市的任意两个个城市的任意两个之间都可以通信，且使铺设光缆的总费用最低。之间都可以通信，且使铺设光缆的总费用最低。在每两个城市之间都可以铺设光缆，在每两个城市之间都可以铺设光缆，n个城市之间，最多可能铺个城市之间，最多可能铺设设n(n-1)/2条光缆，但铺设光缆的费用很高，且各个城市之间铺设条光缆，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，那么，如何在这些可能的

60、线路中选择光缆的费用不同，那么，如何在这些可能的线路中选择n-1条，以使条，以使总的费用最少呢？总的费用最少呢？10.4图的连通性问题图的连通性问题用连通网来表示用连通网来表示n个城市及个城市及n个城市间可能铺设的光缆，其中网的个城市间可能铺设的光缆，其中网的顶点表示城市，边表示两个城市之间的光缆线路，赋予边的权值表顶点表示城市，边表示两个城市之间的光缆线路，赋予边的权值表示相应的造价。对于示相应的造价。对于n个顶点的连通网可以建立许多不同的生成树，个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，我们要选择一条这样一每一棵生成树都可以是一个通信网。现在，我们要选择

61、一条这样一棵生成树，也就是使总的造价最少。这个问题就是构造连通网的最棵生成树，也就是使总的造价最少。这个问题就是构造连通网的最小代价生成树（小代价生成树（minimumcostspanningtree）(简称为最小生简称为最小生成树成树)问题。其中一棵生成树的代价就是树上所有边的代价之和。代问题。其中一棵生成树的代价就是树上所有边的代价之和。代价在网中通过权值来表示，一个生成树的代价就是生成树各边的代价在网中通过权值来表示，一个生成树的代价就是生成树各边的代价之和。价之和。最小生成树有多种算法，其中大多数算法都利用了最小生成树的最小生成树有多种算法，其中大多数算法都利用了最小生成树的简称为简称

62、为MST性质：性质：假设一个连通网假设一个连通网N=(V,E)，V是顶点的集合，是顶点的集合，E是边的集合，是边的集合，V有有一个非空子集一个非空子集U。如果。如果(u,v)是一条具有最小权值的边，其中，是一条具有最小权值的边，其中，uU，vV-U，那么一定存在一棵包含边，那么一定存在一棵包含边(u,v)的最小生成树。的最小生成树。10.4图的连通性问题图的连通性问题下面用反证法证明以上下面用反证法证明以上MST性质。性质。假设所有的最小生成树都不存在这样的一条边假设所有的最小生成树都不存在这样的一条边(u,v)。设。设T是连通是连通网网N中的一棵最小生成树，如果将边中的一棵最小生成树，如果将

63、边(u,v)加入到加入到T中，根据生成树中，根据生成树的定义，的定义，T一定出现包含一定出现包含(u,v)的回路。另外的回路。另外T中一定存在一条边中一定存在一条边(u,v)的权值大于或等于的权值大于或等于(u,v)的权值，如果删除边的权值，如果删除边(u,v)，则得到一棵代价小于或等于则得到一棵代价小于或等于T的生成树的生成树T。T是包含边是包含边(u,v)的最小的最小生成树，这与假设矛盾。由此，性质得证。生成树，这与假设矛盾。由此，性质得证。10.4图的连通性问题图的连通性问题普里姆（普里姆（prim）算法和克鲁斯卡尔（）算法和克鲁斯卡尔（kruskal）算法就是利用）算法就是利用MST性

64、质构造的最小生成树算法。性质构造的最小生成树算法。1普里姆算法普里姆算法假设假设N=V,E是连通网，是连通网，TE是是N的最小生成树边的集合。执行以的最小生成树边的集合。执行以下操作：下操作：（1）初始时，令）初始时，令U=u0(u0V)，TE=。（2）对于所有的边）对于所有的边uU，vV-U的边的边(u,v)E，将一条代价最，将一条代价最小的边小的边(u0,v0)放到集合放到集合TE中，同时将顶点中，同时将顶点v0放进集合放进集合U中。中。（3）重复执行步骤（）重复执行步骤（2），直到），直到U=V为止。为止。这时，边集合这时，边集合TE一定有一定有n-1条边，条边，T=V,TE就是连通网就

65、是连通网N的最的最小生成树。小生成树。10.4图的连通性问题图的连通性问题例如，图例如，图10.24就是利用普里姆算法构造最小生成树的过程。就是利用普里姆算法构造最小生成树的过程。10.4图的连通性问题图的连通性问题初初始始时时，集集合合U=a，集集合合V-U=b,c,d,e,f，边边集集合合为为。只只有有一一个个元元素素aU，将将a从从U中中取取出出，比比较较顶顶点点a与与集集合合V-U中中顶顶点点构构成成的的代代价价最最小小边边，在在(a,b)、(a,c)、(a,d)中中，(a,c)的的权权值值最最小小，故故将将顶顶点点c加加入入到到集集合合U中中，边边(a,c)加加入入到到TE中中，此此

66、时时有有U=a,c，V-U=b,d,e,f，TE=(a,c)。目目前前集集合合U的的元元素素与与集集合合V-U的的元元素素构构成成的的所所有有边边为为(a,b)、(a,d)、(b,c)、(c,d)、(c,e)和和(c,f)，其其中中代代价价最最小小的的边边为为(c,f)，故故把把顶顶点点f加加入入到到集集合合U中中，边边(c,f)加加 入入 到到 TE中中，此此 时时 有有 U=a,c,f，V-U=b,d,e，TE=(a,c),(c,f)。依次类推，直到所有的顶点都加入到。依次类推，直到所有的顶点都加入到U中。中。10.4图的连通性问题图的连通性问题为实现这个算法需附设一个辅助数组为实现这个算法需附设一个辅助数组closeedgeMaxSize，以，以记录记录U到到V-U最小代价的边。对于每个顶点最小代价的边。对于每个顶点vV-U，在辅助数组中，在辅助数组中存在一个相应分量存在一个相应分量closeedgev，它包括两个域，它包括两个域adjvex和和lowcost，其中，其中，adjvex域用来表示该边中属于域用来表示该边中属于U中的顶点，中的顶点，lowcost域存储该边对应的权值