《数据结构》课件第7章

第7章图7.1图的基本概念7.2图的存储结构7.3图的遍历7.4连通网的最小生成树7.5最短路径7.6拓扑排序本章小结习题七实训7-1图的创建与存储实训7-2最小生成树

【教学目标】通过对本章的学习，熟悉图的有关术语和概念，掌握图的两种存储结构，并能根据问题的要求选择合适的存储结构，熟练掌握图的两种遍历算法，理解求图的最小生成树的两种算法，理解求单源最短路径及拓扑排序的算法，并能运用这些算法解决实际问题。上一章已经学习了一种非线性结构——树，接下来将学习另一种更复杂的非线性结构——图。在树形结构中，数据元素之间有着明显的层次关系，并且每一层的数据元素可能和下一层的多个元素相关(即可以拥有多个孩子结点)，但却最多只能和上一层的一个数据元素相关(即最多只能拥有一个双亲结点)。而在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。也就是说在图形结构中，数据元素之间无明显的层次关系，元素间的关系是多对多的，而这种关系在现实世界中是大量存在的。因此，图的应用极为广泛，在计算机科学、物理、化学、语言学、逻辑学、通信工程等很多领域中的很多问题都可以用图来表示。本章首先介绍图的基本概念，然后介绍图的两种存储结构，最后介绍图的一些算法和应用。7.1图的基本概念7.1.1图的定义图7.1无向图及有向图(a)无向图；(b)有向图图(Graph)是由一个非空的顶点集合和一个描述顶点之间关系——边(或者弧)的集合组成。假设图7.1是城市交通示意图，分别用a,b,c,d,e表示城市中的五个地点，点之间的连线表示道路。如果道路可以双向行驶，则如图7.1(a)所示；如果只允许单向行驶，则如图7.1(b)所示。图7.1无向图及有向图(a)无向图；(b)有向图

图是一种网状数据结构，其形式化定义如下：Graph = (V，E)其中V表示图中顶点(Vetex)的集合，E表示V中顶点之间的关系，则图7.1(a)可以定义为

7.1(a) = (V,E)

V = {a,b,c,d,e}

E = {(a,b),(a,c),(a,d),(b,c),(b,d),(d,e)}而图7.1(b)可以定义为

7.1(b) = (V,E)

V = {a,b,c,d,e}

E = {〈a,b〉,〈a,c〉,〈a,d〉,〈b,c〉,〈b,d〉,〈d,e〉}其中无序对(a,b)表示a和b之间的一条边(edge)，此时的图称为无向图。有序对〈a,b〉表示从顶点a到顶点b的一条弧(arc)，并称a为弧尾(tail)或起始点，称b为弧头(head)或终端点，此时图中的边是有方向的，这样的图称为有向图。7.1.2图的基本术语有关图的一些基本术语可以定义如下。

1.邻接点与关联在无向图7.1(a)中，(a,b)是一条无向边，则称顶点a和顶点b互为邻接点。在有向图7.1(b)中，<a,b>是一条有向边，则称顶点a邻接于顶点b，顶点b邻接于顶点a，同时称弧<a,b>与顶点a,b相关联。

2.度、入度和出度对于无向图而言，顶点v的度是指和v相关联边的数目，记作TD(v)。例如：图7.1(a)中顶点a的度是3，c的度是2；在有向图中顶点v的度有出度和入度两部分，其中以顶点v为弧头的弧的数目成为该顶点的入度，记作ID(v)，以顶点v为弧尾的弧的数目称为该顶点的出度，记作OD(v)，则顶点v的度为TD(v) = ID(v) + OD(v)。例如：图7.1(b)中顶点b的入度ID(b) = 1，出度OD(b) = 2，顶点b的度TD(b) = ID(b) + OD(b) = 3。一般地，若图G中有n个顶点，e条边或弧，则图中顶点的度与边的关系如下式所示：

(7-1)即图的边数或弧数总和等于各顶点的度数之和的一半。

3.无向完全图和有向完全图图7.2无向完全图和有向完全图(a)无向完全图；(b)有向完全图例7.1足球欧洲杯小组赛，假设每组4个队，进行单循环，问每组共有多少场比赛？如果比赛还分主客场，又有多少场比赛呢？

解：用图7.2表示各队之间的比赛关系。图7.2(a)表示单循环情况，每队各进行3场比赛，即各顶点的度TD = 3。据式(7-1)可得：总比赛场数=(3×4)/2 = 6图7.2无向完全图和有向完全图(a)无向完全图；(b)有向完全图图7.2(b)表示分主客场时的比赛情况，假设用弧头代表主队，弧尾代表客队，每队主客各3场，即各顶点的度TD = ID + OD = 6，则总比赛场数 = (6 × 4)/2 = 12可以这样理解上面的两个图：每组共有n个队，每队有n-1个对手，所以比赛n(n-1)场。而如果不分主客场，则A—B和B—A是同一场比赛，所以比赛n(n-1)/2场。从以上的例子中可以看出，图7.2(a)的顶点数n和边数e满足下述关系：e = n(n-1)/2这样的无向图称为无向完全图。图7.2(b)的顶点数n和弧数e满足下述关系：e = n(n-1)这样的有向图称为有向完全图。

4.子图设有两个图G = (V，{E})和图G′= (V′，{E′}),若V′V且E′E，则称图G′为G的子图。图7.3(a)与(b)分别是7.1(a)与7.1(b)的子图。图7.3图7.1(a)及图7.1(b)的子图(a)图7.1(a)的子图；(b)图7.1(b)的子图

5.路径与路径长度在无向图G中，若存在一个顶点序列vp，vi1，vi2，…，vim，vq，使得(vp,vi1)，(vi1,vi2)，…，(vim,vq)均属于E(G)，则称顶点vp到vq存在一条路径。若G是有向图，则路径也是有向的，它由E(G)中的有向边〈<vp,vi1〉，〈vi1,vi2〉，…，〈vim,vq〉组成。路径长度定义为该路径上边或弧的数目。如图7.1(a)中a到e存在路径(a,b,d,e)，路径长度为3。

6.简单路径和简单回路若一条路径上的顶点序列均不重复出现，则称此路径为一条简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的路径称为简单回路或简单环。例如在图7.1(a)中，顶点序列{a,c,b,d,e}是从顶点a到顶点e的一条简单路径，其长度为4，顶点序列{a,d,e}是从顶点a到顶点e的另一条简单路径，其长度为2。而顶点序列{a,b,c,a}则是一个简单回路。

7.连通图和连通分量在无向图中，若从顶点vi到顶点vj有路径，则称vi和vj是连通的。如果图G中的任意两个顶点都是连通的，则称此无向图是连通图。无向图中的极大连通子图称为该无向图的连通分量。所谓极大连通子图是指如果再往该子图中加入原图的任何一个顶点，子图就不能连通。显然，连通图的连通分量只有一个，而非连通图则必有多个连通分量。例如，图7.1(a)是一个连通图，只有一个连通分量，就是它自身。而图7.4(a)所示的则是一个非连通图，它有两个连通分量，如图7.4(b)所示。图7.4非连通图及其连通分量(a)非连通图；(b)图(a)的两个连通分量

8.强连通图及强连通分量在有向图中，任意两顶点vi和vj都存在从vi到vj以及从vj到vi的路径，则称此图为强连通图；有向图的极大强连通子图称为该图的强连通分量。例如图7.5(a)就不是一个强连通图。它有三个强连通分量，如图7.5(b)所示。图7.5非强连通图及其强连通分量(a)非强连通图；(b)图(a)的三个强连通分量

9.权和网在一个图中，每条边可以标上具有某种含义的数值，该数值称为该边的权。边上带权的图称为网或带权图。网可分为有向网和无向网。网在实际应用中是大量存在的，如图7.6所示的是一个无向网，表示了5个居民点之间铺设煤气管道可能出现的铺设路线，边上的权表示铺设此路线的费用。图7.6无向网7.2图的存储结构由于图是一个比较复杂的非线性结构，因此图没有顺序存储的方式。但可以通过二维数组来表示元素间的关系。另外，由于图中任意两个顶点间都可能存在关系，因此也可以通过链式存储来表示相互之间的关系。所以图的存储方式有多种，这里只介绍两种基本的存储方式：邻接矩阵和邻接表。7.2.1邻接矩阵邻接矩阵(AdjacencyMatrix)是表示顶点之间相邻关系的矩阵。设G = (V,E)是具有n个顶点的图，顶点序号依次为1，2，3，…，n，则G的邻接矩阵是具有如下定义的n阶矩阵：

1，若图中存在边(vi,vj)或弧〈vi,vj〉A[i][j]=

0，若图中不存在边(vi,vj)或弧〈vi,vj〉A[i][j]=若G是网，则其邻接矩阵可表示为

weight，若图中存在边(vi,vj)或弧〈vi,vj〉，且其上的权值为weightA[i][j]=MAX，若图中不存在边(vi,vj)或弧〈vi,vj〉，

MAX是网中不存在的虚设最大权值例如图7.1(a)及图7.6的邻接矩阵如图7.7所示。A[i][j]=图7.7图7.1(a)及图7.6的邻接矩阵(a)图7.1(a)的邻接矩阵；(b)图7.6的邻接矩阵关于邻接矩阵的几点说明：

(1)对于无向图或无向网来说，它的邻接矩阵是一个对称矩阵，图7.1(a)及图7.6(b)的邻接矩阵都是对称的。

(2)可以方便地查找图中任一条边或边上的权值，只要A[i][j]为0或MAX就说明图中不存在以顶点vi或vj为顶点的边或弧。

(3)可以方便地查找图中任一顶点的度。对于无向图来说，vi的度就是第i行或第i列中非0或非MAX值的元素的个数。对于有向图来说，顶点vi的入度为第i列中非0或非MAX值的元素的个数，而出度为第i行中非0或非MAX值的元素的个数。邻接矩阵定义用C语言描述如下：#defineMAXLEN10 /*图中最大顶点数*/structvertex{ intnum; /*顶点标识，以整数为例*/

… /*顶点其他信息*/};typedefstruct{structvertexvexs[MAXLEN]; /*图中顶点数组*/intedges[MAXLEN][MAXLEN]; /*二维数组，表示顶点相邻关系，即图中的边*/intn,e; /*图中顶点数和边数*/}MGraph; /*定义邻接矩阵*/7.2.2邻接表邻接表(AdjacencyList)是图的一种链式存储结构。在邻接表中，对图中的每个顶点建立一个带头结点的边链表，如第i个边链表中的结点就表示依附于顶点vi的边(若是有向图，则表示以vi为弧尾的弧)。每个边链表的头结点又构成一个表头结点表。这样，一个有n个顶点的图的邻接表是由表头结点表与边链表两部分构成的。

1)表头结点表表示结点表由所有表头结点以顺序结构(向量)的形式存储，以便可以随机访问任一顶点的边链表。邻接表的表头结点和边链表结点结构如图7.8所示。表头结点由两部分构成，其中数据域(vexdata)用于存储顶点的名或其它有关信息；链域(firstarc)用于指向链表中第一个顶点(即与顶点vi邻接的第一个邻接点)。图7.8邻接表的表头结点和边链表结点

2)边链表第i个边链表中的结点则表示依附于顶点vi的边。边链表结点的数据域(adjvex)用于表示邻接点信息，链域(nextarc)用于指向下一个与顶点vi邻接的顶点。对于一个网，它的邻接表还应该在其边链表结点中增加一个存放权值的域。图7.1(a)的邻接表如图7.9所示(表中的1,2,3,4,5分别对应于图中的a,b,c,d,e五个顶点)。图7.9图7.1(a)的邻接表对于如图7.10所示的有向网，其邻接表如图7.11所示。图7.10有向网

图7.11图7.10的邻接表关于邻接表的几点说明：

(1)一个图的邻接矩阵的表示是唯一的，但其邻接表表示不唯一。这是因为，邻接表表示中各边结点的链接次序取决于建立邻接表的算法及边的输入次序。也就是说，在邻接表的每个线性链表中，各结点的顺序是任意的。为了编程的方便而把后输入的结点插入到先输入的结点之前，图7.11所示的邻接表就是这样得到的。

(2)由邻接表可知，对于无向图，第i个顶点vi的度，就是i号边链表中的结点个数。而在有向图中，i号边链表中的结点个数只是顶点vi的出度，而要求得到顶点vi的入度，则必须遍历整个邻接表，在所有边链表中查找邻接点域的值为i的结点并计数求和。所以，有时为了便于确定顶点vi的入度，可以建立一个逆邻接表，即对每个顶点vi建立一个所有以顶点vi为弧头的弧的表。图7.10的逆邻接表如图7.12所示。图7.12图7.10的逆邻接表图的邻接表存储结构用C语言描述如下：typedefstructnode{intadjvex;structnode*next;}EdgeNode; /*边链表结点*/typedefstructvnode{intvertex;EdgeNode*firstedge;}VertexNode; /*表头结点*/typedefVertexNodeAdjlist[MAXLEN];

/*表头结点表*/typedefstruct{Adjlistadjlist;intn,e;}ALGraph; /*定义邻接表*/7.3图的遍历所谓图的遍历是指从图的某一顶点出发，访问图中其余顶点，且使每个顶点仅被访问一次。图的遍历和树的遍历类似，只是更为复杂。在图的遍历中，由于图中的任一顶点都可能和其余顶点相邻接，因此在访问了某个顶点之后，又可能在沿着某条路径的遍历过程中，再次回到该顶点。因而必须对每一个已被访问的顶点做标记。为此，可以设一个辅助数组visited[n]，用以表示1～n个顶点是否被访问过。其数组每个元素的初值均为0，一旦顶点i被访问，则visited[i] = 1。图的遍历是图的基本操作之一，很多需要对图中每个顶点依次进行的操作都可以在遍历过程中来完成。图的遍历根据搜索顺序的不同，可分为深度优先搜索和广度优先搜索，它们对无向图和有向图都适用。7.3.1深度优先搜索深度优先搜索(Depth-FirstSearch)是指按照深度方向搜索，它类似于树的先根遍历，是树的先根遍历的推广。

1.深度优先搜索连通子图的基本思想

(1)从图中某个顶点v0出发，首先访问v0。

(2)找出刚访问过的顶点vi的第一个未被访问的邻接点，然后访问该顶点。以该顶点为新顶点，重复本步骤，直到当前的顶点没有未被访问的邻接点为止。

(3)返回前一个访问过的且仍有未被访问的邻接点的顶点，找出并访问该顶点的下一个未被访问的邻接点，然后执行步骤(2)。

2.采用递归的形式搜索连通子图的基本思想

(1)访问出发点v0。

(2)依次以v0的未被访问的邻接点为出发点，深度优先搜索图，直至图中所有与v0有路径相通的顶点都被访问。若此时图中还有顶点未被访问(非连通图的情况)，则另选图中一个未被访问的顶点作为起始点，重复上述深度优先搜索过程，直至图中所有顶点均被访问过为止。图7.13给出了一个深度优先搜索的过程图示，其中实箭头代表访问方向，虚箭头代表回溯方向，箭头旁边的数字代表搜索顺序，A为起始顶点。深度优先步骤结果为ABCFEGDHI。图7.13图的深度优先搜索过程图示图的深度优先搜索的结果不是唯一的。第一，它的遍历首先取决于从哪一个顶点开始，从不同的顶点开始进行遍历，其结果是不同的。第二，由图来建立邻接表时，邻接表不是唯一的，这也决定了进行遍历时的结果不同。

例7.2

利用邻接表，按深度优先搜索算法对图7.14所示无向图进行遍历。图7.14无向图及其邻接表假设遍历是从顶点1开始的。第一步，访问顶点1，然后找到顶点1所指的链表，该链表的第一个顶点是3，该顶点未被访问过，访问顶点3。(现在已经访问了1，3两个顶点。)第二步，访问顶点3所指向的链表的第一个顶点，该链表的第一个顶点为7，该顶点未被访问过，访问顶点7。(现在已经访问了1，3，7三个顶点。)第三步，访问顶点7所指向的链表的第一个顶点，该链表的第一个顶点为8，该顶点未被访问过，访问顶点8。(现在已经访问了1，3，7，8四个顶点。)第四步，访问顶点8所指向的链表的第一个顶点，该链表的第一个顶点为7，该顶点已被访问过，又访问该顶点所指向的下一个顶点6，该顶点未被访问过，访问顶点6。(现在已经访问了1，3，7，8，6五个顶点。)第五步，访问顶点6所指向的链表的第一个顶点，该链表的第一个顶点为8，该顶点已被访问过，又访问该顶点所指向的下一个顶点3，该顶点也被访问过，也就是说顶点6的所有邻接点都已被访问且链表已到了表尾，于是返回顶点6的上一个被访问的顶点8所指向的链表，而顶点8中的所有邻接点也已被访问，于是返回顶点8的上一个已访问的顶点7所指向的链表进行访问，而顶点7中的所有邻接点也已被访问，于是返回顶点7的上一个已访问的顶点3所指向的链表进行访问，而顶点3中的所有邻接点也已被访问，于是返回顶点3的上一个已访问的顶点1所指向的链表进行访问。第六步，在顶点1所指向的链表中，第一个未被访问的顶点为2，于是访问顶点2。(现在已经访问了1，3，7，8，6，2六个顶点。)第七步，访问顶点2所指向的链表的第一个未被访问的顶点，该顶点为5，访问顶点5。(现在已经访问了1，3，7，8，6，2，5七个顶点。)第八步，访问顶点5所指向的链表的第一个未被访问的顶点，该顶点为4，访问顶点4。(现在已经访问了1，3，7，8，6，2，5，4八个顶点。)现在所有的顶点都已被访问完毕，图的深度优先搜索完成。结果序列是(1，3，7，8，6，2，5，4)。实现深度优先搜索的递归函数用C语言描述如下：voidDepthFirstSearch(AdjListg,intv0)

/*图g为邻接表类型AdjList*/{ structedgenode*p;

/*p是指向边链表结点的指针*/

visit(v0);

/*访问v0*/

visited[v0]=1;

p=g.vertex[v0].firstarc;

/*找到v0的第一个邻接点p*/

while(p!=NULL) {

if(!visited[p->adjvex]) /*如果p尚未被访问*/ DepthFirstSearch(g,p->adjvex);

/*从p出发继续深度优先搜索*/ p=p->nextarc;

/*返回p的下一个表结点，继续深度优先搜索*/ }}图7.15图的广度优先搜索过程图示广度优先搜索(Breadth-FirstSearch)类似于树的层次遍历，是树的层次遍历的推广。广度优先搜索的基本思想是：

(1)从图中某个顶点v0出发，首先访问v0。

(2)依次访问v0的各个未被访问的邻接点。

(3)分别从这些邻接点(端结点)出发，依次访问它们的各个未被访问的邻接点(新的端结点)。访问时应保证：如果vi和vk为当前端结点，vi在vk之前被访问，则vi的所有未被访问的邻接点应在vk的所有未被访问的邻接点之前访问。重复(3)，直到所有端结点均没有未被访问的邻接点为止。图7.15给出了一个广度优先搜索的过程图示。广度优先搜索的结果是ABEDCGFHI。图7.15图的广度优先搜索过程图示7.4连通网的最小生成树连通网的最小生成树在许多领域里有着实际的应用，下面介绍生成树和最小生成树相关的概念及最小生成树的构造方法。7.4.1生成树及最小生成树的相关概念

(1)生成树。设G = (V，E)是一个连通的无向图，若G1是包含G中所有顶点的一个无回路的连通图，则称G1是G的一棵生成树。

(2)生成树的特点。有n个顶点的连通图的生成树，必然包含n个顶点和n-1条边。

(3)生成树代价。对于一个带权的图(网)，在一棵生成树中各条边的权值之和称为这棵生成树的代价。

(4)最小代价生成树。在一个连通网的所有生成树中，各边的代价之和最小的那棵生成树称为该连通网的最小代价生成树(MinimumCostSpanningTree)，简称为最小生成树(MST)。最小生成树的概念可以应用到许多实际问题中，例如要在n个居民点之间铺设煤气管道，而且每个居民点只需要有一条管道送气。可以用网来表示各种可能的情况，网的顶点代表居民点，网的边代表居民点之间可能铺设的管道，边上的权值则代表铺设煤气管道的造价。显然，由于各居民点间的距离和地理条件不同，造价就可能不同。怎样才能做到既要连通n个居民点又要总造价最低呢？这就是一个典型的图的最小生成树的问题。7.4.2最小生成树的构造方法图的生成树有很多，是不是用穷举的方法去找图的所有生成树，同时计算并比较它的各边上权值之和，从而决定最小生成树呢？显然，这种方法是不可取的。下面介绍两种行之有效的，也是最常用的构造最小生成树的方法：普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。

1.普里姆(Prim)算法普里姆(Prim)算法的基本思想如下：设N = (V,{E})是一连通网，U是顶点集V的一个非空子集，TE为最小生成树中边的集合。

(1)初始U={u0}(u0∈V),TE=φ；

(2)在所有u∈U,v∈V-U的边中选一条代价最小的边(u0，v0)并入集合TE，同时将v0并入U；

(3)重复(2)，直到U=V为止。此时，TE中必含有n-1条边，则T = (V，{TE})为N的最小生成树。可以看出，普利姆算法逐步增加U中的顶点，可称为“加点法”。

例7.3

对于如图7.16(a)所示连通网，求用普里姆算法求最小生成树的过程。图7.16用普里姆算法构造最小生成树的过程(a)一个连通网；(b)加入顶点2；(c)加入顶点4；(d)加入顶点6；(e)加入顶点3；(f)加入顶点5

解：以顶点1作为起点，求解过程如下：第一步，V = {1，2，3，4，5，6}，U = {}，TE = {}。从顶点1开始进行操作，则U={1}，V-U = {2，3，4，5，6}。找到一个顶点在U中，而另一个顶点在V-U中，且代价最小的边，可以分析这条边为(1，2)，然后将顶点2加入U中，边(1，2)加入TE中。所以现在U = {1，2}，TE = {(1，2)}。第二步，U = {1，2}，V-U = {3，4，5，6}。找到的边为(2，4)，所以现在U = {1，2，4}，TE = {(1，2)，(2，4)}。第三步，U = {1，2，4}，V-U = {3，5，6}。找到的边为(4，6)，所以现在U = {1，2，4，6}，TE = {(1，2)，(2，4)，(4，6)}。第四步，U = {1，2，4，6}，V-U = {3，5}。找到的边为(3，4)，所以现在U = {1，2，4，6，3}，TE = {(1，2)，(2，4)，(4，6)，(3，4)}。第五步，U = {1，2，4，6，3}，V-U = {5}。找到的边为(5，6)，所以现在U = {1，3，6，4，2，5}，TE = {(1，2)，(2，4)，(4，6)，(3，4)，(5，6)}。U = V，求最小生成树完成。最后所求的最小生成树的边为{(1，2)，(2，4)，(4，6)，(3，4)，(5，6)}。最小生成树是边的集合，可以用数组表示，用C语言描述如下：#defineMAXVEX30 /*最大顶点数*/#defineMAX1000 /*边不存在时设权为MAX*/typedefstruct{intfromVex; /*边起点*/intendVex; /*边终点*/intweight; /*边权值*/}EdgeSet[MAXVEX],Edge;

/*定义边集数组和边的类型*/EdgeSetaEdges; /*定义最小生成树变量*/假设图G = (V，E)中共有n个顶点，其最小生成树T = (U，TE)，以边集数组aEdges存储TE，则aEdges[k]表示向U中添加第k(k = 2～n)个顶点时TE中新增的边。普里姆算法的实质就是逐个修正aEdges[k](k=2~n)的信息，直到将第n个顶点添加到U中。如果以1号顶点作为起点，则普里姆算法描述如下。

(1)初始化：给边集数组aEdges[i](i = 2～n)赋初值，以1号顶点为起点，i号顶点为终点，如果边(1，i)不存在，则权为MAX。

(2) k = 2。

(3)在下标为k~n的边中找出权值最小的边，下标记录为m，该边的终点记录为j。

(4)如果m≠k，则将此边与下标为k的边进行交换，即完成向U中添加第k个顶点j。

(5)对尚未加入树的边aEdges[i](i = k + 1～n)进行调整：边aEdges[i]的终点为t，如果边(j，t)的权小于t到U中其他顶点的权，则更新aEdges[i]为边(j，t)。

(6) k++。

(7)返回(3)继续执行，直到n个顶点全部添加到U中。对应例7.3中用Prim算法求连通网的最小生成树的过程，边集数组aEdges的变化情况如图7.17所示。图7.17(b)～(f)分别对应生成边(1,2)、(2,4)、(4,6)、(4,3)、(6,5)的情况。图7.17Prim算法边集数组变化情况(a)初始状态;(b)k=2,m=2,j=2;(c)k=3,m=4,j=4;(d)k=4,m=6,j=6;(e)k=5,m=6,j=3;(f)k=6,m=6,j=5

2.克鲁斯卡尔(Kruskal)算法克鲁斯卡尔(Kruskal)算法的基本思想是：假设N=(V,{E})是连通网，将N中的边按权值从小到大的顺序排列。

(1)将n个顶点看成n个集合。

(2)按权值由小到大的顺序选择边，所选边应满足两个顶点不在同一个顶点集合内，即加入此边后不会在生成树中产生回路，将该边放到生成树边的集合中。同时将该边的两个顶点所在的顶点集合合并。

(3)重复(2)，直到所有的顶点都在同一个顶点集合内。可以看出，克鲁斯卡尔算法逐步增加生成树的边，与普里姆算法相比，可称为“加边法”。例7.4

对于如图7.18(a)所示连通网，求用克鲁斯卡尔算法求最小生成树的过程。

解：求解过程如下：第一步，首先比较图中所有的边的权值，找到最小的权值的边(4，6)，加入到生成树的边集中。TE={(4，6)}。第二步，比较图中其余边的权值，找到最小的权值的边(2，4)，且加入此边后不会使TE产生回路，TE={(4，6)，(2，4)}。第三步，比较图中其余边的权值，找到最小的权值的边(3，4)，且加入此边后不会使TE产生回路，TE={(4，6)，(2，4)，(3，4)}。第四步，比较图中其余边的权值，找到最小的权值的边(5，6)，且加入此边后不会使TE产生回路，TE={(4，6)，(2，4)，(3，4)，(5，6)}。第五步，比较图中其余边的权值，找到最小的权值的边(2，5)，但加入此边后将使TE产生回路，舍弃之，再找另一条最小权值的边。现在有两条边(4，5)和(1，2)满足条件，首先来观察(4，5)，发现加入此边后将使已生成的生成树产生回路，故将边(4，5)舍弃。而加入边(1，2)以后将不会使生成树产生回路，所以将边(1，2)加入到生成树的边集中。TE = {(4，6)，(2，4)，(3，4)，(5，6)，(1，2)}。图7.18克鲁斯卡尔算法构造最小生成树的过程(a)一个连通网；(b)加入边(4，6)；(c)加入边(2，4)；(d)加入边(3，4)；(e)加入边(5，6)；(f)加入边(1，2)现在所产生的最小生成树中已经有了n-1条边，求最小生成树的过程完成。最后所求得的最小生成树的边为{(1，2)，(2，4)，(4，6)，(3，4)，(5，6)}。可以看出，这个结果和普里姆算法所得到的结果相同。7.5最短路径7.5.1最短路径的概念在一个图中，从一个顶点到另一个顶点如果存在路径，则称该路径长度为路径上的边的数目，如果两顶点间存在多条路，则所谓最短路径自然是指路径最短的一条。对于一个网来说，路径的长度是指路径上各边的权值之和，相应地，最短路径也就是指路径上各边权值之和最小的一条路径。在实际生活中经常遇到这样的问题，从A城到B城有若干条通路，可以用一张带权图来表示，其中的权是经过各条路线所需费用。一个旅客要从A城到B城，如果他希望尽可能减少转车次数，这就是求图中A点到B点的最短路径问题，即求边数最少的路径。而如果旅客希望尽可能节约费用，就成了带权图中求最短路径问题，此时所找的路径是从A点到B点所经各条边上权值之和最小者。本节所讨论的是带权有向图(有向网)的最短路径问题。通常称有向路径上的第一个顶点为源点，称最后一个顶点为终点。从某个源点到其他各顶点的最短路径又称为单源最短路径。单源最短路径的问题是：给定一个带权图G = (V，E)和图中的一个源点V0，分别求出从V0到图G中其他每个顶点的最短路径长度，即路径上权值的总和。7.5.2求单源最短路径的方法怎样求一个源点到其余各个顶点的最短路径呢？下面介绍迪杰斯特拉(Dijkstra)算法。此算法的基本思想是：把图中所有顶点分成两组，第一组包括已确定最短路径的顶点，第二组包括尚未确定最短路径的顶点，按最短路径长度递增的顺序逐个把第二组的顶点加入到第一组中去，直到从源点出发的可以到达的所有顶点都已包括在第一组中。在此过程中，总保持从源点到第一组各顶点的最短路径长度都不大于从源点到第二组的任何顶点的最短路径长度。

例7.5

如图7.19(a)所示有向网，用迪杰斯特拉算法求解顶点1到其余各顶点的最短路径。图7.19带权有向图中单源最短路径(a)带权有向图；(b)以顶点1为源点的最短路径解：求最短路径的过程如表7-1所示。表7-1用迪杰斯特拉算法求单源最短路径的过程第一步，列出从顶点1到其它顶点的路径长度，它们分别为∞，10，∞，30，100。从中选取路径长度最小的顶点3(从源点到顶点3的最短路径为10)。第二步，找到顶点3以后，再观察从源点经过顶点3到达各个顶点的路径是否比第一步所找到的路径要小。可以发现，源点到顶点4的路径更新为60(1，3，4)。其余的路径则没变。然后，从已更新的路径中找出路径长度最小的顶点5(从源点到顶点5的最短路径为30)。第三步，找到顶点3、5以后，即可将源点到顶点4的路径更新为50(1，5，4)、到顶点6的路径更新为90(1，5，6)，并从已更新的路径中找出路径长度最小的顶点4。第四步，找到顶点3，5，4以后，将源点到顶点6的路径更新为60(1，3，4，6)，从已更新的路径中找出路径长度最小的顶点6。第五步，找到顶点3，5，4，6以后，现在只剩下一个顶点2没有找到最短路径了。而即使经过顶点3，5，4，6，从顶点1到顶点2仍无路径，从源点到顶点2的最短路径为∞，此时选取最后一个顶点2。所有的最短路径均已找到。最终求出的单源最短路径如图7.19(b)所示。7.6拓扑排序拓扑排序是图中重要的运算之一。在实际中的应用很广泛，例如一项工程往往可以分解为一些具有独立性的子工程，这些子工程称为“活动”。每个活动在进行时间上有着一定的相互制约的关系。也就是说，有些活动必须在其他有关活动完成之后才能开始，即某项活动的实施必须以另一项活动的完成为前提。用顶点表示活动，用弧表示活动间的优先关系的有向无环图，称为顶点表示活动的网(ActivityOnVertexNetwork)，简称为AOV网。在AOV网中，若从顶点vi到顶点vj之间存在一条有向路径，则称vi是vj的前驱，vj是vi的后继。若〈i,j〉是AOV网中的弧，则称vi是vj的直接前驱，vj是vi的直接后继。例如，一个软件专业的学生必须学习一系列基本课程(如表7-2所示)，其中有些课程是基础课，如“高等数学”，它不需要先修其它课程，而另一些课程必须在先学完某些课程之后才能开始学习。如通常在学完“程序设计基础”和“离散数学”之后才开始学习“数据结构”等等。在此，每一门课程是一项活动，可以用图7.20所示的AOV网来表示各课程及其之间的关系。表7-2软件专业学生必修课程课程编号课程名称先决条件C1高等数学无C2程序设计基础无C3离散数学C1，C2C4数据结构C2，C3C5汇编语言C2C6编译技术C4，C5C7操作系统C4，C9C8普通物理C1C9计算机原理C8在AOV网中，不应该出现有向环，因为存在环意味着某项活动应以自己为先决条件。显然，这是荒谬的，若设计出这样的流程图，工程便无法进行。而对程序的数据流图来说，则表明存在一个死循环。因此，对给定的AOV网应首先判定网中是否存在环。检测的办法是对有向图构造其顶点的拓扑序列，若网中所有顶点都在它的拓扑序列中，则AOV网中必定不存在环。在有向图G = (V，{E})中，V中顶点的线性序列称为拓扑序列，序列必须满足如下条件：对序列中任意两个顶点vi、vj，在G中有一条从vi到vj的路径，则在序列中vi必排在vj之前。例如，图7.20的一个拓扑序列为：C1，C2，C3，C4，C5，C8，C9，C6，C7。图7.20表示课程之间优先关系的有向无环图一个AOV网的拓扑排序序列并不是唯一的，例如，图7.20的另一个拓扑序列为：C1，C8，C9，C2，C5，C3，C4，C6，C7。由于AOV图中的路径表示的是活动之间的制约关系，因此对于图中没有路径相连的两个顶点，则它们在拓扑排序的序列中出现的先后就没有要求。例如，上例第一个序列中C2先于C9，第二个则反之。无前驱的顶点不受任何制约，而对于某个有前驱的顶点来说，如果其前驱已经活动执行，则相应的制约关系自动解除。这就是拓扑排序的基本思想。拓扑排序思想描述如下：图7.21有向图(1)从有向图中选一个无前驱的顶点(即入度为0的顶点)输出。

(2)将此顶点和以它为起点的弧删除。

(3)重复(1)、(2)，直到不存在无前驱的顶点。

(4)若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在回路，否则输出顶点的顺序即为一个拓扑序列。图7.21有向图

例7.6

求图7.21所示有向图的一个拓扑序列。求它的拓扑序列的过程如图7.22所示。第一步，选取入度为0的顶点2，删除顶点2以及相关联的弧〈2，1〉，〈2，3〉，得到第一个拓扑序列顶点2。第二步，选取入度为0的顶点1，删除顶点1以及相关联的弧〈1，4〉，〈1，3〉，得到二个拓扑序列顶点2，1。图7.22拓扑排序过程(a)输出顶点2；(b)输出顶点1；(c)输出顶点3；(d)输出顶点5；(e)输出顶点4第三步，选取入度为0的顶点3，删除顶点3以及相关联的弧〈3，5〉，得到三个拓扑序列顶点2，1，3。第四步，选取入度为0的顶点5，删除顶点5以及相关联的弧〈5，4〉，〈5，6〉，得到第四个拓扑序列顶点2，1，3，5。第五步，选取入度为0的顶点4，删除顶点4以及相关联的弧〈4，6〉，得到五个拓扑序列顶点2，1，3，5，4。第六步，最后选取仅剩下的最后一个顶点6，拓扑排序结束。得到有向图7.21的一个拓扑序列(2，1，3，5，4，6)。本章小结本章首先介绍了图的概念和特性以及与图有关的一些基本术语。图是一种比较复杂的非线性结构，所以图没有顺序存储方式，可以通过二维数组及链式存储来表示图中各顶点和边之间的相互关系。本章中主要介绍了两种存储方式，即邻接矩阵和邻接表。图的遍历是图的最基本也是最重要的操作，常用的遍历算法有深度优先搜索和广度优先搜索两种。求最小生成树、最短路径以及拓扑排序的算法是本章的难点，本章通过举例介绍了求最小生成树的两种常用算法，即Prim算法和Kruskal算法，以及求最短路径和拓扑排序的算法。习题七一、单项选择题

1.一个有n个顶点的无向图最多有________条边。

A. n B. n(n-1)

C. n(n-1)/2

D. 2n

2.一个有4个顶点的无向完全图有________条边。

A. 6 B. 12

C. 16

D. 20

3.一个有5个顶点的连通图至少有________条边。

A. 3

B. 4 C. 5 D. 6

4.________的邻接矩阵是对称矩阵。

A. 有向图 B.无向图 C. AOV网

5.邻接表是图的一种________。

A.顺序存储结构 B.链接存储结构

C.索引存储结构D.散列存储结构

6.采用邻接表存储的图的深度优先遍历算法类似于二叉树的________。

A.前序遍历 B.中序遍历

C.后序遍历 D.按层遍历

7.采用邻接表存储的图的广度优先遍历算法类似于二叉树的________。

A.前序遍历 B.中序遍历

C.后序遍历 D.按层遍历

8.任何一个无向连通图________最小生成树。Ａ.只有一棵 B.有一棵或多棵

C.一定有多棵 D.可能不存在

9.一个图的________表示法是唯一的，而________表示法是不唯一的。

A.三元组 B.邻接矩阵

C.邻接表 D.索引

二、简答题

1.对图7.23所示有向图，回答下列问题：

(1)该图是强连通图吗？若不是，则给出其强连通分量。

(2)请给出从顶点1到顶点3的所有的简单路径。

(3)请给出顶点1的度、入度和出度。

(4)请给出其邻接矩阵、邻接表及逆邻接表。

2.对图7.24所示无向图，分别给出它从顶点1出发进行深度和广度遍历得到的顶点序列。图7.23有向图

图7.24求遍历序列

3.对图7.25所示无向图，分别画出按普里姆算法和克鲁斯卡尔算法得到最小生成树的过程。

4.对图7.26所示有向图，利用迪杰斯特拉算法，求从顶点1到其余各顶点的最短路径。图7.25求最小生成树图7.26求最短路径5.对图7.27所示有向图，求拓扑序列。图7.27求拓扑序列实训7-1图的创建与存储【实训目的】

1.加深对图及其存储结构等基本概念的理解。

2.掌握图的创建及使用邻接矩阵和邻接表存储的算法。【实训内容】对于图7.1(a)所示无向图，分别构造相应的邻接矩阵和邻接表，并输出。【实训要求】

1.设计一个程序实现上述过程。

2.从键盘输入无向图的顶点和边。【算法分析】不考虑顶点其他信息，仅以数字1，2，…代表图中顶点。建立邻接表时，为插入方便，在边链表中采取前接法，即后输入的相邻结点接在先输入结点之前。所建立的邻接表与边输入顺序有关。由于是无向图，邻接矩阵为对称矩阵，而建立邻接表时要分别以边的两个顶点作为起点修改边链表。【程序清单】#include<stdio.h>#defineMAXLEN10typedefstruct{intvexs[MAXLEN];intedges[MAXLEN][MAXLEN];intn,e;}MGraph; /*定义邻接矩阵*/typedefstructnode{intadjvex;structnode*next;}EdgeNode;typedefstructvnode{intvertex;EdgeNode*firstedge;}VertexNode;typedefVertexNodeAdjlist[MAXLEN];typedefstruct{Adjlistadjlist;intn,e;}ALGraph; /*定义邻接表*/

/*建立无向图邻接矩阵*/voidCreateMGraph(MGraph*G,intv,inte,intbegin[],intend[]){inti,j,k;intch1,ch2;G->n=v;G->e=e;for(i=1;i<=G->n;i++)/*初始化顶点表，顶点编号从1开始*/G->vexs[i]=i;for(i=1;i<=G->n;i++)／*初始化邻接矩阵*/for(j=1;j<=G->n;j++)G->edges[i][j]=0;for(k=1;k<=G->e;k++){ /*根据边信息修改邻接矩阵*/i=begin[k];j=end[k];G->edges[i][j]=1;G->edges[j][i]=1;}printf("邻接矩阵为：\n");for(i=1;i<=G->n;i++){ /*输出邻接矩阵*/for(j=1;j<=G->n;j++)printf("%d",G->edges[i][j]);printf("\n");}}/*建立邻接表*/voidCreateGraphAL(ALGraph*G,intv,inte,intbegin[],intend[]){inti,j,k;

EdgeNode*s;G->n=v;G->e=e;for(i=1;i<=G->n;i++){ /*初始化表头结点表*/G->adjlist[i].vertex=i;G->adjlist[i].firstedge=NULL;}

for(k=1;k<=G->e;k++){ /*以边的一端为起点修改边链表*/i=begin[k];j=end[k];s=(EdgeNode*)malloc(sizeof(EdgeNode));

/*新建边链表结点*/s->adjvex=j;s->next=G->adjlist[i].firstedge;

/*前插法将新结点插入边链表*/G->adjlist[i].firstedge=s;}for(k=1;k<=G->e;k++){

/*以边的另一端为起点修改边链表*/

i=end[k];j=begin[k];s=(EdgeNode*)malloc(sizeof(EdgeNode));s->adjvex=j;s->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=s;}printf("邻接表如下：\n");for(i=1;i<=G->n;i++){ /*输出邻接表*/printf("%d",G->adjlist[i].vertex);s=G->adjlist[i].firstedge;while(s!=NULL){printf("->%d",s->adjvex);s=s->next;}printf("\n");}}main(){MGraph*s=(MGraph*)malloc(sizeof(MGraph));ALGraph*g=(ALGraph*)malloc(sizeof(ALGraph));intv,e;/*顶点数、边数*/intbegin[MAXLEN],end[MAXLEN];

/*各边起点及终点*/inti;printf(“请输入顶点数和边数(输入格式为：顶点数边数)：\n");scanf("%d%d",&v,&e);for(i=1;i<=e;i++){printf("请输入每条边对应的两个顶点的序号(输入格式为：ij)\n");scanf("%d%d",&begin[i],&end[i]);}CreateMGraph(s,v,e,begin,end);CreateGraphAL(g,v,e,begin,end);}实训7-2最 小 生 成 树【实训目的】

1.利用图解决实际生活中一些具体的问题。图7.28居民点示意图2.掌握最小生成树算法。图7.28居民点示意图

2.掌握最小生成树算法。【实训内容】假设要在n个居民点之间铺设煤气管道，图7.28画出了各个居民点之间可能的铺设路线，边上的权值代表了铺设此条路线的所需费用。现要求编程求出一种既可以使煤气到达各个居民点之间，又可以使总的造价