1、1 1第 8 章 图8.1图的基本概念图的基本概念8.2图的设计和实现图的设计和实现8.3图的遍历图的遍历8.4最小生成树最小生成树8.5最短路径最短路径8.6本章小结本章小结2 2图是又一种非线性数据结构。在图结构中，数据元素之间的关系是多对多的，即图中每一个数据元素可以和图中任意别的数据元素相关。图用于表示数据元素之间存在的网状结构关系。本章首先介绍有关图的一些基本概念和图的基本操作，然后讨论图的存储结构以及图基本操作的算法实现，最后讨论了图的最小生成树和最短路径问题。图的最小生成树和图的最短路径是图的两种最主要的应用。3 3 8.1.1 图的基本概念图是由顶点集合及顶点间的关系集合组成的
2、一种数据结构。图G的定义是：G(V，E)式中V x|x某个数据元素集合E(x，y)|x，yV或E x，-y|x，yV并且Path(x，-y)其中，Path(x，y)表示从 x到 y的一条单向通路，即Path(x，y)是有方向的。8.1 图的基本概念图的基本概念4 4图有许多复杂结构，本课程只讨论最基本的图，因此，本章讨论的图中不包括图8-1所示两种形式的图。图8-1(a)中有从自身到自身的边存在，称为带自身环的图，图8-1(b)中从顶点B到顶点D有两条无向边，称为多重图。我们首先给出图的基本术语。为方便术语解释，图8-给出了4个典型图例。5 5 图 8-1 带自身环的图和多重图(a)带自身环的
3、图；(b)多重图6 6图 8-2 四个图例(a)G1；(b)G2；(c)G3；(d)G47 7(1)顶点和边：图中的结点称作顶点，图中的第i个顶点记做vi。两个顶点vi和vj相关联称作顶点vi和vj之间有一条边，图中的第k条边记做ek，ek(vi，vj)或vi，vj。(2)有向图和无向图：在有向图中，顶点对x，y是有序的，顶点对x，y称为从顶点x到顶点y的一条有向边，因此，x，y与y，x是两条不同的边。有向图中的顶点对x，y用一对尖括号括起来，x是有向边的始点，y是有向边的终点，有向图中的边也称作弧；在无向图中，顶点对(x，y)是无序的，顶点对(x，y)称为与顶点x和顶点y相关联的一条边，这条
4、边没有特定的方向，因此，(x，y)与(y，x)是同一条边。8 8图8-给出的4个图例中，图G1和G2是无向图。G1的顶点集合为V(G1)0，1，2，3，边集合为E(G1)(0，1)，(0，2)，(0，3)，(1，2)，(1，3)，(2，3)；图G3和G4是有向图，G3的顶点集合为V(G3)0，1，2，边集合为E(G3)0，1，l，0，1，2。对于有向边，边的方向用箭头画出，箭头从有向边的始点指向有向边的终点。(3)完全图：在有n个顶点的无向图中，若有n(n-1)/2条边，即任意两个顶点之间有且只有一条边，则称此图为无向完全图。图8-(a)所示的G1就是无向完全图；在有n个顶点的有向图中，若有n
5、(n-1)条边，即任意两个顶点之间有且只有方向相反的两条边，则称此图为有向完全图。图8-(d)所示的G4就是有向完全图。9 9(4)邻接顶点：在无向图G中，若(u，v)是E(G)中的一条边，则称u和v互为邻接顶点，并称边(u，v)依附于顶点u和v。在图8-(a)所示的无向图G1中，顶点0的邻接顶点有顶点1，2和3；在有向图G中，若u，v是E(G)中的一条边，则称顶点u邻接到顶点v，顶点v邻接自顶点u，并称边u，v与顶点u和顶点v相关联。在图8-(c)所示的有向图G3中，顶点1因边1，2邻接到顶点2。10 10(5)顶点的度：顶点v的度是与它相关联的边的条数，记作TD(v)。对于有向图，顶点的度
6、等于该顶点的入度和出度之和，即TD(v)ID(v)OD(v)。其中，顶点v的入度ID(v)是以v为终点的有向边的条数；顶点v的出度OD(v)是以v为始点的有向边的条数。在图8-(c)所示的有向图G3中，顶点1的入度ID(1)1，顶点1的出度OD(1)2，所以，顶点1的度TD(v)ID(v)OD(v)123。对于无向图，顶点的度等于该顶点的入度或出度，即TD(v)ID(v)OD(v)。11 11(6)路径：在图G(V，E)中，若从顶点vi出发有一组边可到达顶点vj，则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径。在图8-2(b)所示的图G2中，从顶点0到顶点3的路径为0，1，3。(
7、7)权：有些图的边附带有数据信息，这些附带的数据信息称为权。第i条边的权用符号wi表示。权可以表示实际问题中从一个顶点到另一个顶点的距离、花费的代价、所需的时间等等。带权的图也称作网络或网。图8-3就是带权图，其中，图8-3(a)是一个工程的施工进度图，图8-3(b)是一个交通网络图。12 12图 8-3 带权图(a)施工进度图；(b)交通网络图13 13(8)路径长度：对于不带权的图，一条路径的路径长度是指该路径上的边的条数；对于带权的图，一条路径的路径长度是指该路径上各个边权值的总和。在图8-(b)所示的无向图G2中，路径0，1，3的路径长度为2；在图8-3(a)所示的带权图中，路径1，3
8、，6，7的路径长度为16。(9)子图：设有图G1V1，E1和图G2V2，E2，若V2V1且E2E1，则称图G2是图G1的子图。14 14(10)连通图和连通分量：在无向图中，若从顶点vi到顶点vj有路径，则称顶点vi和顶点vj是连通的。如果图中任意一对顶点都是连通的，则称该图是连通图。非连通图的最大连通子图称作连通分量。图8-2中的无向图G1和G2都是连通图。(11)生成树：一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边。(12)简单路径和回路：若路径上各顶点v1，v2，vm互不重复，则称这样的路径为简单路径；若路径上第一个顶点v1与最后一个顶点vm
9、重合，则称这样的路径为回路或环。15 158.1.2 图的抽象数据类型1.数据集合图的数据集合由一组顶点集合vi和一组边ej集合组成。当为带权图时每条边上权wj构成权集合wj。2.操作集合(1)初始化Initiate(G，n)：初始化图G，n为顶点个数。(2)插入顶点 InsertVertex(G，vertex)：在图G中插入顶点vertex。(3)插入边InsertEdgeG，-v1，v2，weight)：在图G中插入边，边的权值为weight。(4)删除边DeleteEdge(G，v1，v2)：在图G中删除边。16 16(5)第一个邻接顶点GetFirstVex(G，v)：在图G中寻找顶点
10、v的第一个邻接顶点。注：图中每个顶点的若干个邻接顶点之间是没有先后次序的，但对于一个具体的图，一旦该图建立完毕，则图中每一个顶点的所有邻接顶点之间就有次序之分。(6)下一个邻接顶点GetNextVex(G，int v1，v2)：在图G中寻找顶点v1的邻接顶点v2的下一个邻接顶点。(7)深度优先遍历DepthFirstSearch(G)：深度优先遍历图G。(8)广度优先遍历BroadFirstSearch(G)：广度优先遍历图G。和树的遍历类同，图的遍历也是访问图中的每一个顶点且每个顶点只被访问一次。17 17从图的定义可知，图的信息包括两部分，图中顶点的信息和描述顶点之间关系的边的信息。顶点信
11、息的描述问题是一个简单的表存储结构问题，可采用第2章讨论的顺序表或链表存储。8.2 图的设计和实现图的设计和实现18 18 对于一个有n个顶点的图，由于每个顶点都可能和其他n-1个顶点成为邻接顶点，所以边之间的关系的描述问题实际上是一个nn矩阵的计算机存储表示问题。图的存储结构主要是图中边的存储结构。图的存储结构主要有邻接矩阵和邻接表两种。一旦确定了图的存储结构，即可具体设计和实现图的抽象数据类型。19 198.2.1 图的邻接矩阵存储结构我们首先定义邻接矩阵。假设图G(V，E)有n个顶点，即Vv0，v1，vn-1，E可用如下形式的矩阵A描述，对于A中的每一个元素aij，满足：由于矩阵A中的元
12、素aij表示了顶点vi和顶点vj之间边的关系，或者说，A中的元素aij表示了顶点vi和顶点vj(0jn-1)的邻接关系，所以矩阵A称作邻接矩阵。2020在图的邻接矩阵存储结构中，顶点信息使用一维数组存储，边信息的邻接矩阵使用二维数组存储。图8-4(a)是一个无向图，图8-4(b)是该图的邻接矩阵存储结构，其中，V表示了图的顶点集合，A表示了图的邻接矩阵。无向图的邻接矩阵一定是对称矩阵。21 21 图 8-4 无向图及其邻接矩阵(a)无向图；(b)邻接矩阵2222图8-5(a)是一个有向图，图8-5(b)是对应的邻接矩阵存储结构，其中，V表示了图的顶点集合，A表示了图的邻接矩阵。有向图的邻接矩阵
13、一般是非对称矩阵。2323图 8-5 有向图及其邻接矩阵(a)有向图；(b)邻接矩阵2424对于带权图，邻接矩阵A定义为：其中，wij0。(有一种特殊的带权图允许wij为负值，这里不做讨论。)根据不同的应用问题，邻接矩阵A也可定义为：2525邻接矩阵A还可定义为(本书带权图的邻接矩阵使用此定义)：图8-6(a)是一个带权图，图8-6(b)是对应的邻接矩阵存储结构，其中，V表示了图的顶点集合，A表示了图的邻接矩阵。对于带权图，邻接矩阵第i行中所有0aij的元素个数等于第i个顶点的出度，邻接矩阵第j列中所有0aij的元素个数等于第j个顶点的入度。2626 图 8-6 带权图及其邻接矩阵(a)带权图
14、；(b)邻接矩阵27278.2.2 图的邻接表存储结构图的邻接矩阵存储结构的主要特点是把图的边信息存储在一个nn矩阵中，其中n为图中的顶点个数。当这个nn矩阵是稠密矩阵时，图的邻接矩阵存储结构是最常用也是最高效的存储结构。但当图的边数少于顶点个数且顶点个数值较大时，nn矩阵的存储问题就变成了稀疏矩阵的存储问题，此种情况时邻接表就是一种较邻接矩阵更为有效的存储结构。图8-7(a)是一个有向图，图8-7(b)是该有向图的邻接表存储结构。2828图 8-7 有向图及其邻接表(a)有向图；(b)邻接表2929图8-7(b)中行数组的data域存储图的顶点信息，adj域为该顶点的邻接顶点单链表的头指针。
15、第i行单链表中的dest域存储所有起始顶点为vi的邻接顶点vj，因第i行单链表表示的边的所有起始顶点均为vi，所以不需要再另外存储。next域为下一个结点的指针域。如果是带权图，单链表中需再增加cost域，第i行单链表中的dest域值为j的cost域中存储边的权值wij。对比图8-7(b)和第5章的图5-6 行指针数组结构的三元组链表，可以发现，两者讲述的是同一种存储结构。3030当图中顶点数目较小且边较多时，采用图的邻接矩阵存储结构效率较高；当图中顶点数目较大且边的数目远小于相同顶点的完全图的边数时，采用图的邻接表存储结构效率较高。另外，图的存储结构还有十字链表存储结构等。图的十字链表存储结
16、构原理和第5章的图5-7 所示的三元组十字链表存储结构的原理完全相同，此处不再赘述。31 318.2.3 邻接矩阵存储结构下图的操作实现邻接矩阵存储结构下图的顶点信息存储在一个顺序表中，图的边信息存储在一个二维数组中。邻接矩阵的存储结构以及图的各种操作实现算法设计如下：include SeqList.h-/*包含顺序表头文件*/typedef struct-SeqList Vertices;-/*存放顶点的顺序表*/-int edgeMaxVerticesMaxVertices;/*存放边的邻接矩阵*/-int numOfEdges;3232-/*边的条数*/AdjMWGraph;-/*图的结
17、构体定义*/void Initiate(AdjMWGraph*G，int n)-/*初始化*/-int i，j;-for(i 0;i n;i)-for(j 0;j edgeij 0;-else G-edgeij MaxWeight;-G-numOfEdges 0;-/*边的条数置为0*/-ListInitiate(&G-Vertices);-/*顺序表初始化*/3434 void InsertVertex(AdjMWGraph*G，DataType vertex)/*在图G中插入顶点vertex*/-ListInsert(&G-Vertices，G-Vertices.size，vertex);
18、-/*顺序表尾插入*/void InsertEdge(AdjMWGraph*G，int v1，int v2，int weight)3535/*在图G中插入边，边的权为weight*/-if(v1 G-Vertices.size|v2 G-Vertices.size)-printf(参数v1或v2越界出错!n);-exit(1);-3636-G-edgev1v2 weight;-G-numOfEdges;void DeleteEdge(AdjMWGraph*G，int v1，int v2)/*在图G中删除边*/-if(v1 G-Vertices.size|v2 G-Vertices.size|v
19、1 v2)-3737-printf(参数v1或v2越界出错!n);-exit(1);-G-edgev1v2 MaxWeight;-G-numOfEdges-;3838 int GetFirstVex(AdjMWGraph G，int v)/*在图G中寻找序号为v的顶点的第一个邻接顶点*/*如果这样的邻接顶点存在则返回该邻接顶点的序号，否则返回-1*/-int col;-if(v G.Vertices.size)-3939-printf(参数v1越界出错!n);-exit(1);-for(col 0;col 0&G.edgevcolMaxWeight)return col;-return-1;4
20、040 int GetNextVex(AdjMWGraph G，int v1，int v2)/*在图G中寻找v1顶点的邻接顶点v2的下一个邻接顶点*/*如果这样的邻接顶点存在则返回该邻接顶点的序号，否则返回-1*/*这里v1和v2都是相应顶点的序号*/41 41-int col;-if(v1 G.Vertices.size|v2 G.Vertices.size)-printf(参数v1或v2越界出错!n);-exit(1);-for(col v21;col 0&G.edgev1col MaxWeight)return col;-return-1;以图8-8所示的有向带权图为例编写测试上述图操作
21、函数的程序。4343 图 8-8 有向带权图4444设计 设上述图操作的函数存放在文件AdjMGraph.h中。为方便以后设计测试程序时调用方便，我们把创建图的过程单独设计为一个函数。图的创建函数设计如下：typedef struct-int row;-/*行下标*/-int col;-/*列下标*/-int weight;-/*权值*/4545 RowColWeight;-/*边信息结构体定义*/void CreatGraph(AdjMWGraph*G，DataType V，int n，RowColWeight E，int e)/*在图G中插入n个顶点信息V和e条边信息E*/-int i，k
22、;-Initiate(G，n);-/*顶点顺序表初始化*/4646-for(i 0;i n;i)-InsertVertex(G，Vi);-/*顶点插入*/-for(k 0;k e;k)-InsertEdge(G，Ek.row，Ek.col，Ek.weight);-/*边插入*/测试程序设计如下：-include include 4747 typedef char DataType;-define MaxSize 100 define MaxVertices 10 define MaxEdges 100 define MaxWeight 10000 include AdjMGraph.h inc
23、lude AdjMGraphCreate.h void main(void)4848-AdjMWGraph g1;-DataType a A，B，C，D，E;-RowColWeight rcw 0，1，10，0，4，20，1，3，30，2，1，40，3，2，50;-int n 5，e 5;-int i，j;-CreatGraph(&g1，a，n，rcw，e);-printf(顶点集合为：-);4949-for(i 0;i g1.Vertices.size;i)-printf(%c-，g1.Vertices.listi);-printf(n);-printf(权值集合为：n);-for(i 0;
24、i g1.Vertices.size;i)-for(j 0;j g1.Vertices.size;j)-printf(%5d，g1.edgeij);-printf(n);-5050 程序运行输出结果如下：顶点集合为：-A-B-C-D-E权值集合为：-0-10-10000-10000-20-10000-0-10000-30-10000-10000-40-0-10000-10000-10000-10000-50-0-10000-10000-10000-10000-10000-051 518.3.1 图的深度和广度优先遍历算法和树的遍历操作类同，图的遍历操作的定义是访问图中的每一个顶点且每个顶点只被
25、访问一次。图的遍历方法主要有两种：一种是深度优先搜索遍历，另一种是广度优先搜索遍历。8.3 图的遍历图的遍历5252 图的深度优先搜索遍历类同于树的先根遍历，图的广度优先搜索遍历类同于树的层序遍历。图的遍历算法设计需要考虑三个问题：(1)图的特点是没有首尾之分，所以算法的参数要指定访问的第一个顶点。(2)对图的遍历路径有可能构成一个回路，从而造成死循环，所以算法设计要考虑遍历路径可能出现的死循环问题。(3)一个顶点可能和若干个顶点都是邻接顶点，要使一个顶点的所有邻接顶点按照某种次序被访问。5353对于连通图，从初始顶点出发一定存在路径和图中的所有其他顶点相连，所以对于连通图从初始顶点出发一定可
26、以遍历该图。图的深度优先遍历算法是遍历时深度优先的算法，即在图的所有邻接顶点中每次都在访问完当前顶点后首先访问当前顶点的第一个邻接顶点，这样的算法是一个递归算法。连通图的深度优先搜索遍历递归算法为：(1)访问顶点v并标记顶点v为已访问；(2)查找顶点v的第一个邻接顶点w；(3)若顶点v的邻接顶点w存在，则继续执行，否则算法结束；5454(4)若顶点w尚未被访问，则深度优先搜索递归访问顶点w；(5)查找顶点v的w邻接顶点的下一个邻接顶点w，转到步骤(3)。上述递归算法属于回溯算法，当寻找顶点v的邻接顶点w成功时继续进行，当寻找顶点v的邻接顶点w失败时回溯到上一次递归调用的地方继续进行。对于图8-
27、8所示的有向连通图，若顶点A为初始访问的顶点，则深度优先搜索遍历的顶点访问顺序是：-A B D C E5555图的广度优先遍历算法是一个分层搜索的过程，和树的层序遍历算法类同，图的广度优先搜索遍历算法也需要一个队列以保持访问过的顶点的顺序，以便按顺序访问这些顶点的邻接顶点。连通图的广度优先搜索遍历算法为：(1)访问初始顶点v并标记顶点v为已访问；(2)顶点v入队列；(3)当队列非空时则继续执行，否则算法结束；(4)出队列取得队头顶点u；(5)查找顶点u的第一个邻接顶点w；(6)若顶点u的邻接顶点w不存在，则转到步骤(3)，否则执行后序语句：5656 若顶点w尚未被访问，则访问顶点w并标记顶点w
28、为已访问；顶点w入队列；查找顶点u的w邻接顶点后的下一个邻接顶点w，转到步骤(6)。对于图8-8所示的有向连通图，若顶点A为初始访问的顶点，则广度优先搜索遍历的顶点访问顺序是：-A B E D C5757对于连通图，从图的任意一个顶点开始深度或广度优先遍历一定可以访问图中的所有顶点，但对于非连通图，从图的任意一个顶点开始深度或广度优先遍历并不能访问图中的所有顶点。对于非连通图，从图的任意一个顶点开始深度或广度优先遍历只能访问和初始顶点连通的所有顶点。对于非连通图，当我们把每一个顶点都作为一次初始顶点进行深度或广度优先遍历搜索，并根据顶点的访问标记来判断是否需要访问该顶点，就一定可以访问非连通图
29、中的所有顶点。58588.3.2 图的深度和广度优先遍历算法设计和实现设图采用邻接矩阵存储结构，邻接矩阵存储结构下图的操作实现函数(如第一个邻接顶点函数GetFirstVex(G，v)和下一个邻接顶点函数GetNextVex(G，v，w)已经提供。为方便后边测试程序的设计且不失一般性，我们这里假设图的顶点信息为字母类型，并假设对顶点信息的访问为输出该顶点字母，实际应用中对顶点的访问可以是任意一个函数。图的深度优先遍历函数实现如下：-DepthFSearch(AdjMWGraph G，int v，int visited)5959/*连通图G以v为初始顶点序号的深度优先遍历*/*数组visited
30、标记了相应顶点是否已访问过，0表示未访问，1表示已访问*/-int w;-printf(%c-，G.Vertices.listv);-/*输出顶点字母*/-visitedv 1;-w GetFirstVex(G，v);-while(w!-1)-6060-if(!visitedw)DepthFSearch(G，w，visited);-w GetNextVex(G，v，w);-61 61 void DepthFirstSearch(AdjMWGraph G)/*非连通图G的深度优先遍历*/-int i;-int*visited (int*)malloc(sizeof(int)*G.Vertices
31、.size);-for(i 0;i G.Vertices.size;i)-visitedi 0;6262-for(i 0;i G.Vertices.size;i)-if(!visitedi)DepthFSearch(G，i，visited);-free(visited);图的广度优先遍历函数实现如下：-include SeqCQueue.h-/*包括顺序循环队列*/void BroadFSearch(AdjMWGraph G，int v，int visited)6363/*连通图G以v为初始顶点序号的广度优先遍历*/*数组visited标记了相应顶点是否已访问过，0表示未访问，1表示已访问*/
32、-DataType u，w;-SeqCQueue queue;-printf(%c-，G.Vertices.listv);-/*输出顶点字母*/-visitedv 1;6464-QueueInitiate(&queue);-QueueAppend(&queue，v);-while(QueueNotEmpty(queue)-QueueDelete(&queue，&u);-w GetFirstVex(G，u);-while(w!-1)-6565-if(!visitedw)-printf(%c-，G.Vertices.listw);-/*输出顶点字母*/-visitedw 1;-QueueAppen
33、d(&queue，w);-w GetNextVex(G，u，w);6666-void BroadFirstSearch(AdjMWGraph G)/*非连通图G的广度优先遍历*/-int i;-int*visited (int*)malloc(sizeof(int)*G.Vertices.size);6767-for(i 0;i G.Vertices.size;i)-visitedi 0;-for(i 0;i G.Vertices.size;i)-if(!visitedi)BroadFSearch(G，i，visited);-free(visited);6868以图8-8所示的带权有向图为例编
34、写测试上述图的深度优先和广度优先遍历函数的程序。设计 设图的基本操作函数存放在文件AdjMGraph.h中，上述图的深度优先和广度优先遍历函数存放在文件AdjMGraphTraverse.h中，因顺序循环队列中保存的是顶点序号，所以定义int为DataType。测试程序设计如下：-include include include 6969 typedef int DataType;-/*顺序循环队列中保存顶点序号*/define MaxSize 100 define MaxVertices 10 define MaxEdges 100 define MaxWeight 10000 define
35、MaxQueueSize 100 include AdjMGraph.h7070 include AdjMGraphCreate.h include AdjMGraphTraverse.h void main(void)-AdjMWGraph g1;71 71-DataType a A，B，C，D，E;-RowColWeight rcw 0，1，10，0，4，20，1，3，30，2，1，40，3，2，50;-int n 5，e 5;-CreatGraph(&g1，a，n，rcw，e);7272-printf(深度优先搜索序列为：);-DepthFirstSearch(g1);-printf(n
36、广度优先搜索序列为：);-BroadFirstSearch(g1);程序运行输出结果如下：-深度优先搜索序列为：A-B-D-C-E-广度优先搜索序列为：A-B-E-D-C73738.4.1 最小生成树的基本概念一个有n个顶点的连通图的生成树是原图的极小连通子图，它包含原图中的所有n个顶点，并且有保持图连通的最少的边。8.4 最最 小小 生生 成成 树树7474由生成树的定义可知：(1)若在生成树中删除一条边就会使该生成树因变成非连通图而不再满足生成树的定义；(2)若在生成树中增加一条边就会使该生成树中因存在回路而不再满足生成树的定义；(3)一个连通图的生成树可能有许多。使用不同的寻找方法可以得
37、到不同的生成树。另外，从不同的初始顶点出发也可以得到不同的生成树。图8-9给出了一个无向图和它的两棵不同的生成树。7575 图 8-9 无向图和它的不同的生成树(a)无向图；(b)生成树1；(c)生成树27676从生成树的定义显然可以证明，对于有n个顶点的无向连通图，无论它的生成树的形状如何，一定有且只有n-1条边。如果无向连通图是一个带权图，那么它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小代价生成树，简称最小生成树。许多应用问题都是一个求无向连通图的最小生成树问题。例如要在n个城市之间铺设光缆，铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同。7777 一个目
38、标是要使这n个城市的任意两个之间都可以直接或间接通信，另一个目标是要使铺设光缆的总费用最低。解决这个问题的方法就是在由n个城市顶点、(n-1)!条不同费用的边构成的无向连通图中找出最小生成树，该最小生成树的方案就可以达到既满足使这n个城市的任意两个之间都可以直接或间接通信的目标，又可以满足使铺设光缆的总费用最低的目标。7878从最小生成树的定义可知，构造有n个顶点的无向连通带权图的最小生成树必须满足以下三条：(1)构造的最小生成树必须包括n个顶点；(2)构造的最小生成树中有且只有n-1条边；(3)构造的最小生成树中不存在回路。构造的最小生成树的方法有许多种，典型的构造方法有两种，一种称作普里姆
39、(Prim)算法，另一种称作克鲁斯卡尔(Kruskal)算法。79798.4.2 普里姆算法假设G(V，E)为一个带权图，其中V为网中顶点的集合，E为带权图中带权边的集合。设置两个新的集合U和T，其中U用于存放带权图G的最小生成树的顶点的集合，T用于存放带权图G的最小生成树的带权边的集合。普里姆算法的思想是：令集合U的初值为Uu0(即假设构造最小生成树时均从顶点u0开始)，集合T的初值为T。从所有顶点uU和顶点vV-U的带权边中选出具有最小权值的边(u，v)，将顶点v加入集合U中，将边(u，v)加入集合T中。如此不断重复直到UV时即构造完毕。8080此时集合U中存放着最小生成树的顶点的集合，集
40、合T中存放着最小生成树的带权边的集合。图8-10给出了用普里姆算法构造最小生成树的过程。图8-10(a)为一个有7个顶点10条无向边的带权图；初始时算法的集合UA，集合V-UB，C，D，E，F，G，T，如图8-10(b)所示；在所有u为集合U中顶点，v为集合V-U中顶点的边(u，v)中寻找具有最小权值的边(u，v)，寻找到的是边(A，B)，权为50，把顶点B从集合V-U加入到集合U中，81 81 把边(A，B)加入到T中，如图8-10(c)所示；在所有u为集合U中顶点，v为集合V-U中顶点的边(u，v)中寻找具有最小权值的边(u，v)，寻找到的是边(B，E)，权为40，把顶点E从集合V-U加入
41、到集合U中，把边(B，E)加入到T中，如图8-10(d)所示；随后依次从集合V-U加入到集合U中的顶点为D，F，G，C，依次加入到T中的边为(E，D)(权为50)、(D，F)(权为30)、(D，G)(权为42)、(G，C)(权为45)，分别如图8-10(e)、(f)、(g)、(h)所示。最后得到的图8-10(h)就是原带权连通图的最小生成树。8282图 8-10 普里姆算法构造最小生成树的过程8383*8.4.3 普里姆函数设计和实现这里我们规定，当弧头顶点等于弧尾顶点时权值等于0(即邻接矩阵中对角线元素值均为0)。函数中定义了一个临时数组lowCost，数组元素lowCostv中保存了集合U
42、中顶点u与集合V-U中顶点v的所有边中当前具有最小权值的边(u，v)。集合U的初值为Uu0可以设计为从序号为0的顶点开始。令lowCost的初始值为邻接矩阵中第0行的值，这样lowCost就表示了从集合U中第一个顶点到达集合V-U中各个顶点的代价。8484 然后我们从lowCost中寻找具有最小权值的边，这样的边也就意味着其弧头顶点为集合U中的顶点，其弧尾顶点为集合V-U中的顶点。每选到一条这样的边(u，v)，就输出显示所选到的最小生成树的顶点信息和边的权值信息，并将lowCostv置为0，表示序号为v的顶点已从集合V-U中加入到集合U中。当顶点v从集合V-U加入到了集合U，若当前lowCos
43、t中从集合U中顶点到达集合V-U中顶点存在更小代价的边时，则用这样的边的权值修改lowCost中的权值。8585普里姆算法要处理的带权图G可以采用前面讨论过的邻接矩阵或邻接表存储结构存储顶点信息和边信息，下面设计的普里姆函数采用邻接矩阵存储结构。普里姆函数如下：void Prim(AdjMWGraph G)/*用普里姆得到带权图G的最小生成树，并把结果输出显示*/8686-int n G.Vertices.size，minCost;-int*lowCost (int*)malloc(sizeof(int)*n);-int i，j，k;-/*从序号为0的顶点出发得到最小生成树*/-printf(
44、顶点值%cn，G.Vertices.list0);-for(i 1;i n;i)-lowCosti G.edge0i;-for(i 1;i n;i)-8787-/*寻找当前最小权值的边的顶点*/-minCost MaxWeight;-/*MaxWeight为定义的最大权值*/-j 1;-k 1;-/*保存当前最小权值边的弧尾顶点序号*/-while(j n)-/*寻找最小权值的边*/-if(lowCostj minCost&lowCostj!0)-8888-minCost lowCostj;-k j;-/*保存当前最小权值边的弧尾顶点序号*/-j;-printf(顶点值%c-边的权值%dn，-
45、G.Vertices.listk，minCost);-lowCostk 0;-/*标记该顶点已在集合U中*/-/*修改经序号为k的顶点到其他顶点的最小代价值*/-for(j 1;j n;j)-8989-if(G.edgekj lowCostj)-lowCostj G.edgekj;-9090分析上述普里姆函数，函数主要是一个两重循环，其中每一重循环的次数均为顶点个数n，所以该算法的时间复杂度为O(n2)。由于该算法的时间复杂度只与图中顶点的个数有关，而与图中边的条数无关，所以当该算法用于顶点个数不很多而边稠密的图时时间效率较好。以图8-10(a)所示的无向连通带权图为例设计测试上述普里姆函数的
46、程序。91 91设计 设上述普里姆函数存放在文件Prim.h中，测试程序设计如下：include include include typedef char DataType;-define MaxSize 100 define MaxVertices 10 define MaxWeight 10000 include AdjMGraph.h9292 include AdjMGraphCreate.h include Prim.h void main(void)9393-AdjMWGraph g;-char a A，B，C，D，E，F，G;RowColWeight rcw 0，1，50，1，0，
47、50，0，2，60，2，0，60，1，3，65，-3，1，65，1，4，40，4，1，40，2，3，52，3，2，52，2，6，45，6，2，45，-3，4，50，4，3，50，3，5，30，5，3，30，3，6，42，6，3，42，4，5，70，-5，4，70;9494-int n 7，e 20;-CreatGraph(&g，a，n，rcw，e);-Prim(g);程序的运行结果为：顶点值 A顶点值 B-边的权值 50顶点值 E-边的权值 40顶点值 D-边的权值 509595顶点值 F-边的权值 30顶点值 G-边的权值 42顶点值 C-边的权值 45程序输出的顶点序列和边的权值序列对应了
48、图8-10(b)到图8-10(h)的最小生成树构造过程。在解决实际问题时，我们根据上述程序运行的结果，再结合原问题的带权图，即可构造出图8-10(a)的最小生成树图8-10(h)。96968.4.4 克鲁斯卡尔算法不同于普里姆算法，克鲁斯卡尔算法是一种按照带权图中边的权值的递增顺序构造最小生成树的方法。克鲁斯卡尔算法的思想是：设无向连通带权图G(V，E)，其中V为顶点的集合，E为边的集合。设带权图G的最小生成树T由顶点集合和边的集合构成，其初值为T(V，)，即初始时最小生成树T只由带权图G中的顶点集合组成，各顶点之间没有一条边。这样，最小生成树T中的各个顶点各自构成一个连通分量。然后，按照边的
49、权值递增的顺序考察带权图G中的边集E中的各条边，若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边加入到最小生成树T，9797同时把两个连通分量连接为一个连通分量；若被考察的边的两个顶点属于T的同一个连通分量，则将此边舍去。如此下去，当T中的连通分量个数为1时，T中的该连通分量即为带权图G的一棵最小生成树。9898对于图8-10(a)所示的无向连通带权图，按照克鲁斯卡尔算法构造最小生成树的过程如图8-11(a)(f)所示。根据克鲁斯卡尔算法构造最小生成树的方法，按照带权图G中边的权值从小到大的顺序，反复选择当前尚未被选取的边集合中权值最小的边加入到最小生成树中，直到带权图中所有顶点都加
50、入到最小生成树中为止。最后图8-11(f)所示就是所构造的最小生成树。9999 图 8-11 克鲁斯卡尔算法构造最小生成树的过程100100按照上述克鲁斯卡尔算法思想设计克鲁斯卡尔算法函数主要包括两个部分：首先是带权图G中e条边的权值的排序；其次是判断新选取的边的两个顶点是否属于同一个连通分量。对带权图G中e条边的权值的排序方法可以有很多种，各自的时间复杂度均不相同，对e条边的权值排序算法时间复杂度较好的算法有快速排序法、堆排序法等，这些排序算法的时间复杂度均可以达到O(elbe)。判断新选取的边的两个顶点是否属于同一个连通分量的101101问题是一个在最多有n个顶点的生成树中遍历寻找新选取的
