数据结构课件：图

图8.1图的基本概念8.2图的设计和实现8.3图的遍历8.4最小生成树8.5最短路径8.6本章小结图是又一种非线性数据结构。

在图结构中，

数据元素之间的关系是多对多的，

即图中每一个数据元素可以和图中任意别的数据元素相关。

图用于表示数据元素之间存在的网状结构关系。

本章首先介绍有关图的一些基本概念和图的基本操作，

然后讨论图的存储结构以及图基本操作的算法实现，

最后讨论了图的最小生成树和最短路径问题。

图的最小生成树和图的最短路径是图的两种最主要的应用。

8.1.1图的基本概念

图是由顶点集合及顶点间的关系集合组成的一种数据结构。

图G的定义是：

G＝(V，

E)

式中

V＝

{x|x∈某个数据元素集合}

E＝{(x，

y)|x，

y∈V}

或E＝

{＜x，-y＞|x，

y∈V并且Path(x，-y)}

其中，

Path(x，

y)表示从

x到y的一条单向通路，即Path(x，y)是有方向的。8.1图的基本概念图有许多复杂结构，本课程只讨论最基本的图，因此，本章讨论的图中不包括图8-1所示两种形式的图。图8-1(a)中有从自身到自身的边存在，称为带自身环的图，图8-1(b)中从顶点B到顶点D有两条无向边，称为多重图。

我们首先给出图的基本术语。为方便术语解释，图8-２给出了4个典型图例。

图8-1带自身环的图和多重图

(a)带自身环的图；(b)多重图

图8-2四个图例

(a)G1；(b)G2；(c)G3；(d)G4

(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相关联的一条边，这条边没有特定的方向，因此，(x，y)与(y，x)是同一条边。

图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(n-1)条边，即任意两个顶点之间有且只有方向相反的两条边，则称此图为有向完全图。图8-２(d)所示的G4就是有向完全图。

(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。

(5)顶点的度：顶点v的度是与它相关联的边的条数，记作TD(v)。对于有向图，顶点的度等于该顶点的入度和出度之和，即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)＝1＋2＝3。对于无向图，顶点的度等于该顶点的入度或出度，即TD(v)＝ID(v)＝OD(v)。

(6)路径：在图G＝(V，E)中，若从顶点vi出发有一组边可到达顶点vj，则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径。在图8-2(b)所示的图G2中，从顶点0到顶点3的路径为0，1，3。

(7)权：有些图的边附带有数据信息，这些附带的数据信息称为权。第i条边的权用符号wi表示。权可以表示实际问题中从一个顶点到另一个顶点的距离、花费的代价、所需的时间等等。带权的图也称作网络或网。图8-3就是带权图，其中，图8-3(a)是一个工程的施工进度图，图8-3(b)是一个交通网络图。

图8-3带权图

(a)施工进度图；(b)交通网络图

(8)路径长度：对于不带权的图，一条路径的路径长度是指该路径上的边的条数；对于带权的图，一条路径的路径长度是指该路径上各个边权值的总和。在图8-２(b)所示的无向图G2中，路径0，1，3的路径长度为2；在图8-3(a)所示的带权图中，路径1，3，6，7的路径长度为16。

(9)子图：设有图G1＝{V1，E1}和图G2＝{V2，E2}，若V2

V1且E2

E1，则称图G2是图G1的子图。

(10)连通图和连通分量：在无向图中，若从顶点vi到顶点vj有路径，则称顶点vi和顶点vj是连通的。如果图中任意一对顶点都是连通的，则称该图是连通图。非连通图的最大连通子图称作连通分量。图8-2中的无向图G1和G2都是连通图。

(11)生成树：一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边。

(12)简单路径和回路：若路径上各顶点v1，v2，…，vm互不重复，则称这样的路径为简单路径；若路径上第一个顶点v1与最后一个顶点vm重合，则称这样的路径为回路或环。8.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中插入边<v1，v2>，边<v1，v2>的权值为weight。

(4)删除边DeleteEdge(G，v1，v2)：在图G中删除边<v1，v2>。

(5)第一个邻接顶点GetFirstVex(G，v)：在图G中寻找顶点v的第一个邻接顶点。

注：图中每个顶点的若干个邻接顶点之间是没有先后次序的，但对于一个具体的图，一旦该图建立完毕，则图中每一个顶点的所有邻接顶点之间就有次序之分。

(6)下一个邻接顶点GetNextVex(G，intv1，v2)：在图G中寻找顶点v1的邻接顶点v2的下一个邻接顶点。

(7)深度优先遍历DepthFirstSearch(G)：深度优先遍历图G。

(8)广度优先遍历BroadFirstSearch(G)：广度优先遍历图G。

和树的遍历类同，图的遍历也是访问图中的每一个顶点且每个顶点只被访问一次。

从图的定义可知，图的信息包括两部分，图中顶点的信息和描述顶点之间关系的边的信息。顶点信息的描述问题是一个简单的表存储结构问题，可采用第2章讨论的顺序表或链表存储。8.2图的设计和实现

对于一个有n个顶点的图，由于每个顶点都可能和其他n-1个顶点成为邻接顶点，所以边之间的关系的描述问题实际上是一个n×n矩阵的计算机存储表示问题。

图的存储结构主要是图中边的存储结构。图的存储结构主要有邻接矩阵和邻接表两种。一旦确定了图的存储结构，即可具体设计和实现图的抽象数据类型。8.2.1图的邻接矩阵存储结构

我们首先定义邻接矩阵。假设图G＝(V，E)有n个顶点，即V＝{v0，v1，…，vn-1}，E可用如下形式的矩阵A描述，对于A中的每一个元素aij，满足：

由于矩阵A中的元素aij表示了顶点vi和顶点vj之间边的关系，或者说，A中的元素aij表示了顶点vi和顶点vj(0≤j≤n-1)的邻接关系，所以矩阵A称作邻接矩阵。在图的邻接矩阵存储结构中，顶点信息使用一维数组存储，边信息的邻接矩阵使用二维数组存储。图8-4(a)是一个无向图，图8-4(b)是该图的邻接矩阵存储结构，其中，V表示了图的顶点集合，A表示了图的邻接矩阵。无向图的邻接矩阵一定是对称矩阵。

图8-4无向图及其邻接矩阵

(a)无向图；(b)邻接矩阵图8-5(a)是一个有向图，图8-5(b)是对应的邻接矩阵存储结构，其中，V表示了图的顶点集合，A表示了图的邻接矩阵。有向图的邻接矩阵一般是非对称矩阵。

图8-5有向图及其邻接矩阵

(a)有向图；(b)邻接矩阵对于带权图，邻接矩阵A定义为：

其中，wij>0。(有一种特殊的带权图允许wij为负值，这里不做讨论。)根据不同的应用问题，邻接矩阵A也可定义为：

邻接矩阵A还可定义为(本书带权图的邻接矩阵使用此定义)：

图8-6(a)是一个带权图，图8-6(b)是对应的邻接矩阵存储结构，其中，V表示了图的顶点集合，A表示了图的邻接矩阵。对于带权图，邻接矩阵第i行中所有0<aij<∞的元素个数等于第i个顶点的出度，邻接矩阵第j列中所有0<aij<∞的元素个数等于第j个顶点的入度。

图8-6带权图及其邻接矩阵

(a)带权图；(b)邻接矩阵8.2.2图的邻接表存储结构

图的邻接矩阵存储结构的主要特点是把图的边信息存储在一个n×n矩阵中，其中n为图中的顶点个数。当这个n×n矩阵是稠密矩阵时，图的邻接矩阵存储结构是最常用也是最高效的存储结构。但当图的边数少于顶点个数且顶点个数值较大时，n×n矩阵的存储问题就变成了稀疏矩阵的存储问题，此种情况时邻接表就是一种较邻接矩阵更为有效的存储结构。

图8-7(a)是一个有向图，图8-7(b)是该有向图的邻接表存储结构。

图8-7有向图及其邻接表

(a)有向图；(b)邻接表图8-7(b)中行数组的data域存储图的顶点信息，adj域为该顶点的邻接顶点单链表的头指针。第i行单链表中的dest域存储所有起始顶点为vi的邻接顶点vj，因第i行单链表表示的边<vi，vj>的所有起始顶点均为vi，所以不需要再另外存储。next域为下一个结点的指针域。如果是带权图，单链表中需再增加cost域，第i行单链表中的dest域值为j的cost域中存储边<vi，vj>的权值wij。

对比图8-7(b)和第5章的图5-6行指针数组结构的三元组链表，可以发现，两者讲述的是同一种存储结构。

当图中顶点数目较小且边较多时，采用图的邻接矩阵存储结构效率较高；当图中顶点数目较大且边的数目远小于相同顶点的完全图的边数时，采用图的邻接表存储结构效率较高。

另外，图的存储结构还有十字链表存储结构等。图的十字链表存储结构原理和第5章的图5-7所示的三元组十字链表存储结构的原理完全相同，此处不再赘述。8.2.3邻接矩阵存储结构下图的操作实现

邻接矩阵存储结构下图的顶点信息存储在一个顺序表中，图的边信息存储在一个二维数组中。邻接矩阵的存储结构以及图的各种操作实现算法设计如下：

＃include"SeqList.h"--------/*包含顺序表头文件*/

typedefstruct

{

----SeqListVertices;----------/*存放顶点的顺序表*/

----intedge［MaxVertices］［MaxVertices］;/*存放边的邻接矩阵*/

----intnumOfEdges;-----------/*边的条数*/

}AdjMWGraph;------------------/*图的结构体定义*/

voidInitiate(AdjMWGraph*G，intn)-------/*初始化*/

{

----inti，j;

----for(i＝0;i<n;i＋＋)

--------for(j＝0;j<n;j＋＋)

--------{

------------if(i＝＝j)G->edge［i］［j］＝0;

------------elseG->edge［i］［j］＝MaxWeight;

--------}

----G->numOfEdges＝0;--------/*边的条数置为0*/

----ListInitiate(&G->Vertices);---/*顺序表初始化*/

}

voidInsertVertex(AdjMWGraph*G，DataTypevertex)

/*在图G中插入顶点vertex*/

{

----ListInsert(&G->Vertices，G->Vertices.size，vertex);-/*顺序表尾插入*/

}

voidInsertEdge(AdjMWGraph*G，intv1，intv2，intweight)

/*在图G中插入边<v1，v2>，边<v1，v2>的权为weight*/

{

--if(v1<0||v1>G->Vertices.size||v2<0||v2>G->Vertices.size)

----{

--------printf("参数v1或v2越界出错!＼n");

--------exit(1);

----}

----G->edge［v1］［v2］＝weight;

----G->numOfEdges＋＋;

}

voidDeleteEdge(AdjMWGraph*G，intv1，intv2)

/*在图G中删除边<v1，v2>*/

{

----if(v1<0||v1>G->Vertices.size||v2<0

---||v2>G->Vertices.size||v1＝＝v2)

----{

--------printf("参数v1或v2越界出错!＼n");

--------exit(1);

----}

----G->edge［v1］［v2］＝MaxWeight;

----G->numOfEdges--;

}

intGetFirstVex(AdjMWGraphG，intv)

/*在图G中寻找序号为v的顶点的第一个邻接顶点*/

/*如果这样的邻接顶点存在则返回该邻接顶点的序号，否则返回-1*/

{

----intcol;

----if(v<0||v>G.Vertices.size)

----{

--------printf("参数v1越界出错!＼n");

--------exit(1);

----}

----for(col＝0;col<＝G.Vertices.size;col＋＋)

--if(G.edge［v］［col］>0&&G.edge［v］［col］<MaxWeight)returncol;

----return-1;

}

intGetNextVex(AdjMWGraphG，intv1，intv2)

/*在图G中寻找v1顶点的邻接顶点v2的下一个邻接顶点*/

/*如果这样的邻接顶点存在则返回该邻接顶点的序号，否则返回-1*/

/*这里v1和v2都是相应顶点的序号*/

{

----intcol;

----if(v1<0||v1>G.Vertices.size||v2<0||v2>G.Vertices.size)

----{

--------printf("参数v1或v2越界出错!＼n");

--------exit(1);

----}

----for(col＝v2＋1;col<＝G.Vertices.size;col＋＋)

--if(G.edge［v1］［col］>0&&G.edge［v1］［col］<MaxWeight)returncol;

----return-1;

}以图8-8所示的有向带权图为例编写测试上述图操作函数的程序。

图8-8有向带权图设计设上述图操作的函数存放在文件AdjMGraph.h中。为方便以后设计测试程序时调用方便，我们把创建图的过程单独设计为一个函数。图的创建函数设计如下：

typedefstruct

{

----introw;--------/*行下标*/

----intcol;---------------/*列下标*/

----intweight;-------------/*权值*/

}RowColWeight;----------------/*边信息结构体定义*/

voidCreatGraph(AdjMWGraph*G，DataTypeV［］，intn，RowColWeightE［］，inte)

/*在图G中插入n个顶点信息V和e条边信息E*/

{

----inti，k;

----Initiate(G，n);---------/*顶点顺序表初始化*/

----for(i＝0;i<n;i＋＋)

--------InsertVertex(G，V［i］);--/*顶点插入*/

----for(k＝0;k<e;k＋＋)

---InsertEdge(G，E［k］.row，E［k］.col，E［k］.weight);-/*边插入*/

}测试程序设计如下：-＃include<stdio.h>

＃include<stdlib.h>

typedefcharDataType;---

＃defineMaxSize100

＃defineMaxVertices10

＃defineMaxEdges100

＃defineMaxWeight10000

＃include"AdjMGraph.h"

＃include"AdjMGraphCreate.h"

voidmain(void)

{

----AdjMWGraphg1;

----DataTypea［］＝{′A′，′B′，′C′，′D′，′E′};

--RowColWeightrcw［］＝{{0，1，10}，{0，4，20}，{1，3，30}，{2，1，40}，{3，2，50}};

----intn＝5，e＝5;

----inti，j;

----CreatGraph(&g1，a，n，rcw，e);

----printf("顶点集合为：-");

---for(i＝0;i<g1.Vertices.size;i＋＋)

--------printf("%c-"，g1.Vertices.list［i］);

----printf("＼n");

----printf("权值集合为：＼n");

----for(i＝0;i<g1.Vertices.size;i＋＋)

----{

--------for(j＝0;j<g1.Vertices.size;j＋＋)

------------printf("%5d"，g1.edge［i］［j］);

--------printf("＼n");

----}

}程序运行输出结果如下：

顶点集合为：-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--0

8.3.1图的深度和广度优先遍历算法

和树的遍历操作类同，图的遍历操作的定义是访问图中的每一个顶点且每个顶点只被访问一次。图的遍历方法主要有两种：一种是深度优先搜索遍历，另一种是广度优先搜索遍历。8.3图的遍历

图的深度优先搜索遍历类同于树的先根遍历，图的广度优先搜索遍历类同于树的层序遍历。

图的遍历算法设计需要考虑三个问题：

(1)图的特点是没有首尾之分，所以算法的参数要指定访问的第一个顶点。

(2)对图的遍历路径有可能构成一个回路，从而造成死循环，所以算法设计要考虑遍历路径可能出现的死循环问题。

(3)一个顶点可能和若干个顶点都是邻接顶点，要使一个顶点的所有邻接顶点按照某种次序被访问。对于连通图，从初始顶点出发一定存在路径和图中的所有其他顶点相连，所以对于连通图从初始顶点出发一定可以遍历该图。图的深度优先遍历算法是遍历时深度优先的算法，即在图的所有邻接顶点中每次都在访问完当前顶点后首先访问当前顶点的第一个邻接顶点，这样的算法是一个递归算法。连通图的深度优先搜索遍历递归算法为：

(1)访问顶点v并标记顶点v为已访问；

(2)查找顶点v的第一个邻接顶点w；

(3)若顶点v的邻接顶点w存在，则继续执行，否则算法结束；

(4)若顶点w尚未被访问，则深度优先搜索递归访问顶点w；

(5)查找顶点v的w邻接顶点的下一个邻接顶点w，转到步骤(3)。

上述递归算法属于回溯算法，当寻找顶点v的邻接顶点w成功时继续进行，当寻找顶点v的邻接顶点w失败时回溯到上一次递归调用的地方继续进行。

对于图8-8所示的有向连通图，若顶点A为初始访问的顶点，则深度优先搜索遍历的顶点访问顺序是：

-ABDCE图的广度优先遍历算法是一个分层搜索的过程，和树的层序遍历算法类同，图的广度优先搜索遍历算法也需要一个队列以保持访问过的顶点的顺序，以便按顺序访问这些顶点的邻接顶点。连通图的广度优先搜索遍历算法为：

(1)访问初始顶点v并标记顶点v为已访问；

(2)顶点v入队列；

(3)当队列非空时则继续执行，否则算法结束；

(4)出队列取得队头顶点u；

(5)查找顶点u的第一个邻接顶点w；

(6)若顶点u的邻接顶点w不存在，则转到步骤(3)，否则执行后序语句：

①若顶点w尚未被访问，则访问顶点w并标记顶点w为已访问；

②顶点w入队列；

③查找顶点u的w邻接顶点后的下一个邻接顶点w，转到步骤(6)。

对于图8-8所示的有向连通图，若顶点A为初始访问的顶点，则广度优先搜索遍历的顶点访问顺序是：

-ABEDC对于连通图，从图的任意一个顶点开始深度或广度优先遍历一定可以访问图中的所有顶点，但对于非连通图，从图的任意一个顶点开始深度或广度优先遍历并不能访问图中的所有顶点。对于非连通图，从图的任意一个顶点开始深度或广度优先遍历只能访问和初始顶点连通的所有顶点。

对于非连通图，当我们把每一个顶点都作为一次初始顶点进行深度或广度优先遍历搜索，并根据顶点的访问标记来判断是否需要访问该顶点，就一定可以访问非连通图中的所有顶点。8.3.2图的深度和广度优先遍历算法设计和实现

设图采用邻接矩阵存储结构，邻接矩阵存储结构下图的操作实现函数(如第一个邻接顶点函数GetFirstVex(G，v)和下一个邻接顶点函数GetNextVex(G，v，w))已经提供。为方便后边测试程序的设计且不失一般性，我们这里假设图的顶点信息为字母类型，并假设对顶点信息的访问为输出该顶点字母，实际应用中对顶点的访问可以是任意一个函数。

图的深度优先遍历函数实现如下：

-DepthFSearch(AdjMWGraphG，intv，intvisited［］)

/*连通图G以v为初始顶点序号的深度优先遍历*/

/*数组visited标记了相应顶点是否已访问过，0表示未访问，1表示已访问*/

{

----intw;

----printf("%c-"，G.Vertices.list［v］);--/*输出顶点字母*/

----visited［v］＝1;

----w＝GetFirstVex(G，v);

----while(w!＝-1)

----{

--------if(!visited［w］)DepthFSearch(G，w，visited);

--------w＝GetNextVex(G，v，w);

----}

}

voidDepthFirstSearch(AdjMWGraphG)

/*非连通图G的深度优先遍历*/

{

----inti;

----int*visited＝(int*)malloc(sizeof(int)*G.Vertices.size);

----for(i＝0;i<G.Vertices.size;i＋＋)

--------visited［i］＝0;

----for(i＝0;i<G.Vertices.size;i＋＋)

--------if(!visited［i］)DepthFSearch(G，i，visited);

----free(visited);

}图的广度优先遍历函数实现如下：-＃include"SeqCQueue.h"-----/*包括顺序循环队列*/

voidBroadFSearch(AdjMWGraphG，intv，intvisited［］)

/*连通图G以v为初始顶点序号的广度优先遍历*/

/*数组visited标记了相应顶点是否已访问过，0表示未访问，1表示已访问*/

{

----DataTypeu，w;

----SeqCQueuequeue;

----printf("%c-"，G.Vertices.list［v］);-/*输出顶点字母*/

----visited［v］＝1;

----QueueInitiate(&queue);

----QueueAppend(&queue，v);

----while(QueueNotEmpty(queue))

----{

--------QueueDelete(&queue，&u);

--------w＝GetFirstVex(G，u);

--------while(w!＝-1)

--------{

------------if(!visited［w］)

------------{

------printf("%c-"，G.Vertices.list［w］);-/*输出顶点字母*/

------visited［w］＝1;

----------------QueueAppend(&queue，w);

------------}

------------w＝GetNextVex(G，u，w);

--------}

----}

}

voidBroadFirstSearch(AdjMWGraphG)

/*非连通图G的广度优先遍历*/

{

----inti;

----int*visited＝(int*)malloc(sizeof(int)*G.Vertices.size);

----for(i＝0;i<G.Vertices.size;i＋＋)

--------visited［i］＝0;

----for(i＝0;i<G.Vertices.size;i＋＋)

--------if(!visited［i］)BroadFSearch(G，i，visited);

----free(visited);

}以图8-8所示的带权有向图为例编写测试上述图的深度优先和广度优先遍历函数的程序。

设计设图的基本操作函数存放在文件AdjMGraph.h中，上述图的深度优先和广度优先遍历函数存放在文件AdjMGraphTraverse.h中，因顺序循环队列中保存的是顶点序号，所以定义int为DataType。测试程序设计如下：-＃include<stdio.h>

＃include<stdlib.h>

＃include<malloc.h>

typedefintDataType;----/*顺序循环队列中保存顶点序号*/

＃defineMaxSize100

＃defineMaxVertices10

＃defineMaxEdges100

＃defineMaxWeight10000

＃defineMaxQueueSize100

＃include"AdjMGraph.h"＃include"AdjMGraphCreate.h"

＃include"AdjMGraphTraverse.h"

voidmain(void)

{

----AdjMWGraphg1;

----DataTypea［］＝{′A′，′B′，′C′，′D′，′E′};

---RowColWeightrcw［］＝{{0，1，10}，{0，4，20}，{1，3，30}，{2，1，40}，{3，2，50}};

----intn＝5，e＝5;

----CreatGraph(&g1，a，n，rcw，e);

----printf("深度优先搜索序列为：");

----DepthFirstSearch(g1);

----printf("＼n广度优先搜索序列为：");

----BroadFirstSearch(g1);

}程序运行输出结果如下：

-深度优先搜索序列为：A-B-D-C-E

-广度优先搜索序列为：A-B-E-D-C

8.4.1最小生成树的基本概念

一个有n个顶点的连通图的生成树是原图的极小连通子图，它包含原图中的所有n个顶点，并且有保持图连通的最少的边。8.4最小生成树由生成树的定义可知：

(1)若在生成树中删除一条边就会使该生成树因变成非连通图而不再满足生成树的定义；

(2)若在生成树中增加一条边就会使该生成树中因存在回路而不再满足生成树的定义；

(3)一个连通图的生成树可能有许多。使用不同的寻找方法可以得到不同的生成树。另外，从不同的初始顶点出发也可以得到不同的生成树。

图8-9给出了一个无向图和它的两棵不同的生成树。

图8-9无向图和它的不同的生成树

(a)无向图；(b)生成树1；(c)生成树2从生成树的定义显然可以证明，对于有n个顶点的无向连通图，无论它的生成树的形状如何，一定有且只有n-1条边。

如果无向连通图是一个带权图，那么它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小代价生成树，简称最小生成树。

许多应用问题都是一个求无向连通图的最小生成树问题。例如要在n个城市之间铺设光缆，铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同。

一个目标是要使这n个城市的任意两个之间都可以直接或间接通信，另一个目标是要使铺设光缆的总费用最低。解决这个问题的方法就是在由n个城市顶点、(n-1)!条不同费用的边构成的无向连通图中找出最小生成树，该最小生成树的方案就可以达到既满足使这n个城市的任意两个之间都可以直接或间接通信的目标，又可以满足使铺设光缆的总费用最低的目标。从最小生成树的定义可知，构造有n个顶点的无向连通带权图的最小生成树必须满足以下三条：

(1)构造的最小生成树必须包括n个顶点；

(2)构造的最小生成树中有且只有n-1条边；

(3)构造的最小生成树中不存在回路。

构造的最小生成树的方法有许多种，典型的构造方法有两种，一种称作普里姆(Prim)算法，另一种称作克鲁斯卡尔(Kruskal)算法。8.4.2普里姆算法

假设G＝(V，E)为一个带权图，其中V为网中顶点的集合，E为带权图中带权边的集合。设置两个新的集合U和T，其中U用于存放带权图G的最小生成树的顶点的集合，T用于存放带权图G的最小生成树的带权边的集合。普里姆算法的思想是：令集合U的初值为U＝{u0}(即假设构造最小生成树时均从顶点u0开始)，集合T的初值为T＝{}。从所有顶点u∈U和顶点v∈V-U的带权边中选出具有最小权值的边(u，v)，将顶点v加入集合U中，将边(u，v)加入集合T中。如此不断重复直到U＝V时即构造完毕。此时集合U中存放着最小生成树的顶点的集合，集合T中存放着最小生成树的带权边的集合。

图8-10给出了用普里姆算法构造最小生成树的过程。图8-10(a)为一个有7个顶点10条无向边的带权图；初始时算法的集合U＝{A}，集合V-U＝{B，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中，

把边(A，B)加入到T中，如图8-10(c)所示；在所有u为集合U中顶点，v为集合V-U中顶点的边(u，v)中寻找具有最小权值的边(u，v)，寻找到的是边(B，E)，权为40，把顶点E从集合V-U加入到集合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)就是原带权连通图的最小生成树。

图8-10普里姆算法构造最小生成树的过程*8.4.3普里姆函数设计和实现

这里我们规定，当弧头顶点等于弧尾顶点时权值等于0(即邻接矩阵中对角线元素值均为0)。

函数中定义了一个临时数组lowCost，数组元素lowCost［v］中保存了集合U中顶点u与集合V-U中顶点v的所有边中当前具有最小权值的边(u，v)。

集合U的初值为U＝{u0}可以设计为从序号为0的顶点开始。令lowCost的初始值为邻接矩阵中第0行的值，这样lowCost就表示了从集合U中第一个顶点到达集合V-U中各个顶点的代价。

然后我们从lowCost中寻找具有最小权值的边，这样的边也就意味着其弧头顶点为集合U中的顶点，其弧尾顶点为集合V-U中的顶点。每选到一条这样的边(u，v)，就输出显示所选到的最小生成树的顶点信息和边的权值信息，并将lowCost［v］置为0，表示序号为v的顶点已从集合V-U中加入到集合U中。当顶点v从集合V-U加入到了集合U，若当前lowCost中从集合U中顶点到达集合V-U中顶点存在更小代价的边时，则用这样的边的权值修改lowCost中的权值。普里姆算法要处理的带权图G可以采用前面讨论过的邻接矩阵或邻接表存储结构存储顶点信息和边信息，下面设计的普里姆函数采用邻接矩阵存储结构。普里姆函数如下：

voidPrim(AdjMWGraphG)

/*用普里姆得到带权图G的最小生成树，并把结果输出显示*/

{

----intn＝G.Vertices.size，minCost;

----int*lowCost＝(int*)malloc(sizeof(int)*n);

----inti，j，k;

----/*从序号为0的顶点出发得到最小生成树*/

----printf("顶点值＝%c＼n"，G.Vertices.list［0］);

----for(i＝1;i<n;i＋＋)---------------

--------lowCost［i］＝G.edge［0］［i］;

----for(i＝1;i<n;i＋＋)

----{

--------/*寻找当前最小权值的边的顶点*/

------minCost＝MaxWeight;-/*MaxWeight为定义的最大权值*/

--------j＝1;

-----k＝1;---/*保存当前最小权值边的弧尾顶点序号*/

--------while(j<n)

--------{

---/*寻找最小权值的边*/

----------if(lowCost［j］<minCost&&lowCost［j］!＝0)

------------{

----------------minCost＝lowCost［j］;

-----k＝j;----/*保存当前最小权值边的弧尾顶点序号*/

------------}

------------j＋＋;

--------}

--------printf("顶点值＝%c-边的权值＝%d＼n"，

----G.Vertices.list［k］，minCost);

--------lowCost［k］＝0;---/*标记该顶点已在集合U中*/

--------/*修改经序号为k的顶点到其他顶点的最小代价值*/

--------for(j＝1;j<n;j＋＋)

--------{

------------if(G.edge［k］［j］<lowCost［j］)

----------------lowCost［j］＝G.edge［k］［j］;

--------}

----}

}分析上述普里姆函数，函数主要是一个两重循环，其中每一重循环的次数均为顶点个数n，所以该算法的时间复杂度为O(n2)。由于该算法的时间复杂度只与图中顶点的个数有关，而与图中边的条数无关，所以当该算法用于顶点个数不很多而边稠密的图时时间效率较好。

以图8-10(a)所示的无向连通带权图为例设计测试上述普里姆函数的程序。设计设上述普里姆函数存放在文件Prim.h中，测试程序设计如下：

＃include<stdio.h>

＃include<stdlib.h>

＃include<malloc.h>

typedefcharDataType;---

＃defineMaxSize100

＃defineMaxVertices10

＃defineMaxWeight10000

＃include"AdjMGraph.h"

＃include"AdjMGraphCreate.h"

＃include"Prim.h"

voidmain(void)

{

----AdjMWGraphg;

----chara［］＝{′A′，′B′，′C′，′D′，′E′，′F′，′G′};

RowColWeightrcw［］＝{{0，1，50}，{1，0，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}};

---intn＝7，e＝20;

----CreatGraph(&g，a，n，rcw，e);

----Prim(g);

}程序的运行结果为：

顶点值＝A

顶点值＝B--边的权值＝50

顶点值＝E--边的权值＝40

顶点值＝D--边的权值＝50顶点值＝F--边的权值＝30

顶点值＝G--边的权值＝42

顶点值＝C--边的权值＝45

程序输出的顶点序列和边的权值序列对应了图8-10(b)到图8-10(h)的最小生成树构造过程。在解决实际问题时，我们根据上述程序运行的结果，再结合原问题的带权图，即可构造出图8-10(a)的最小生成树图8-10(h)。8.4.4克鲁斯卡尔算法

不同于普里姆算法，克鲁斯卡尔算法是一种按照带权图中边的权值的递增顺序构造最小生成树的方法。克鲁斯卡尔算法的思想是：设无向连通带权图G＝(V，E)，其中V为顶点的集合，E为边的集合。设带权图G的最小生成树T由顶点集合和边的集合构成，其初值为T＝(V，{})，即初始时最小生成树T只由带权图G中的顶点集合组成，各顶点之间没有一条边。这样，最小生成树T中的各个顶点各自构成一个连通分量。然后，按照边的权值递增的顺序考察带权图G中的边集E中的各条边，若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边加入到最小生成树T，同时把两个连通分量连接为一个连通分量；若被考察的边的两个顶点属于T的同一个连通分量，则将此边舍去。如此下去，当T中的连通分量个数为1时，T中的该连通分量即为带权图G的一棵最小生成树。对于图8-10(a)所示的无向连通带权图，按照克鲁斯卡尔算法构造最小生成树的过程如图8-11(a)~(f)所示。根据克鲁斯卡尔算法构造最小生成树的方法，按照带权图G中边的权值从小到大的顺序，反复选择当前尚未被选取的边集合中权值最小的边加入到最小生成树中，直到带权图中所有顶点都加入到最小生成树中为止。最后图8-11(f)所示就是所构造的最小生成树。

图8-11克鲁斯卡尔算法构造最小生成树的过程按照上述克鲁斯卡尔算法思想设计克鲁斯卡尔算法函数主要包括两个部分：首先是带权图G中e条边的权值的排序；其次是判断新选取的边的两个顶点是否属于同一个连通分量。对带权图G中e条边的权值的排序方法可以有很多种，各自的时间复杂度均不相同，对e条边的权值排序算法时间复杂度较好的算法有快速排序法、堆排序法等，这些排序算法的时间复杂度均可以达到O(elbe)。判断新选取的边的两个顶点是否属于同一个连通分量的问题是一个在最多有n个顶点的生成树中遍历寻找新选取的边的两个顶点是否存在的问题，此算法的时间复杂度最坏情况下为O(n)。

从上述分析我们可以得出，克鲁斯卡尔算法的时间复杂度主要由排序方法决定，而克鲁斯卡尔算法的排序方法只与带权图中边的个数有关，而与带权图中顶点的个数无关，当使用时间复杂度为O(elbe)的排序方法时，克鲁斯卡尔算法的时间复杂度即为O(elbe)，因此当带权图的顶点个数较多、而边的条数较少时，使用克鲁斯卡尔算法构造最小生成树效果较好。

8.5.1最短路径的基本概念

在一个图中，若从一个顶点到另一个顶点存在着路径，定义路径长度为一条路径上所经过的边的数目。图中从一个顶点到另一个顶点可能存在着多条路径，我们把路径长度最短的那条路径叫做最短路径，其路径长度叫做最短路径长度或最短距离。8.5最短路径在一个带权图中，若从一个顶点到另一个顶点存在着一条路径，则称该路径上所经过边的权值之和为该路径上的带权路径长度。带权图中从一个顶点到另一个顶点可能存在着多条路径，我们把带权路径长度值最小的那条路径也叫做最短路径，其带权路径长度也叫做最短路径长度或最短距离。

实际上，不带权的图上的最短路径问题也可以归结为带权图上的最短路径问题。因只要把不带权的图上的所有边的权值均定义为1，则不带权的图上的最短路径问题也就归结为带权图上的最短路径问题。因此不失一般性，我们这里只讨论带权图上的最短路径问题。带权图分无向带权图和有向带权图，当把无向带权图中的每一条边(vi，vj)都定义为弧<vi，vj>和弧<vj，vi>，则有向带权图就变成了无向带权图。因此不失一般性，我们这里只讨论有向带权图上的最短路径问题。

图8-12是一个有向带权图及其邻接矩阵。该带权图从顶点A到顶点D有4条路径，分别为：路径(A，D)，其带权路径长度为30；路径(A，C，F，D)，其带权路径长度为22；

路径(A，C，B，E，D)，其带权路径长度为32；路径(A，C，F，E，D)，其带权路径长度为34。路径(A，C，F，D)称为最短路径，其带权路径长度22称为最短距离。

图8-12有向带权图及其邻接矩阵

(a)有向带权图；(b)邻接矩阵8.5.2从一个顶点到其余各顶点的最短路径

对于从有向带权图中一个确定顶点(称为源点)到其余各顶点的最短路径问题，狄克斯特拉(Dijkastra)提出了一个按路径长度递增的顺序逐步产生最短路径的构造算法。狄克斯特拉算法的思想是：设置两个顶点的集合S和T，集合S中存放已找到最短路径的顶点，集合T中存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点，设为v0，然后从集合T中选择到源点v0路径长度最短的顶点u加入到集合S中，

集合S中每加入一个新的顶点u都要修改源点v0到集合T中剩余顶点的当前最短路径长度值，集合T中各顶点的新的当前最短路径长度值为原来的当前最短路径长度值与从源点过顶点u到达该顶点的路径长度中的较小者。此过程不断重复，直到集合T中的顶点全部加入到集合S中为止。

对于图8-12所示的有向带权图，图8-13(a)~(f)给出了狄克斯特拉算法求从顶点A到其余各顶点的最短路径的过程。图中虚线表示当前可选择的边，实线表示算法已确定包括到集合S中的顶点所对应的边。

图8-13狄克斯特拉算法求从顶点A到其余各顶点最短路径的过程*8.5.3狄克斯特拉算法设计和实现

根据狄克斯特拉算法，设计实现从一个顶点到其余各顶点的最短路径函数的具体方法如下：设计函数有2个输入参数——带权图G和源点序号v0；函数有2个输出参数——最短距离distance［n］和最短路径下标path［n］。函数把带权图G从源点v0到其余各顶点的最短距离数值存放在数组distance中，把带权图G从源点v0到其余各顶点的最短路径上到达目标顶点的前一顶点序号存放在数组path中。初始状态时若从源点v0到顶点vi有边，有distance［i］为该边的权值，则令path［i］为源点v0；若从源点v0到顶点vi无边，有distance［i］为定义的最大权值(这里为10000)，则令distance［i］为-1。

函数设计成迭代过程。设从源点v0到其余各顶点中最短的一条路径为(v0，vk)，其中vk满足：

distance［vk］＝min{distance［vi］|vi∈V-v0}-V是带权图G的顶点一旦确定distance［vk］且distance［vk］小于最大权值，则标识顶点vk已从集合T到集合S中。迭代构造下一条最短路径的方法是：假设下次最短路径的顶点是vj，则可想而知，最短路径或者是(v0，vj)，或者是(v0，vk，vj)；其最短距离distance［vj］或者是从顶点v0到顶点vj有向边的权值，或者是从顶点v0到顶点vk有向边的权值与从顶点vk到顶点vj有向边的权值之和，即distance［vk］与从顶点vk到顶点vj有向边的权值之和。同样地，一旦确定distance［vj］且distance［vj］小于最大权值，则标识顶点vj已从集合T到集合S中。这样的迭代过程一直进行到所有顶点都从集合T到了集合S中或目前已不存在任何一条边可选择为止。要说明的是，这样的迭代过程要确定从源点v0到各个顶点的最短路径序列(如(v0，vk，vj))的算法很复杂，但要确定从源点v0到各个顶点的最短路径的前一个顶点的序号却很容易。

下面函数的数组path中就存放了从源点v0到各个顶点的最短路径的前一个顶点的序号。voidDijkstra(AdjMWGraphG，intv0，intdistance［］，intpath［］)

/*带权图G从下标v0顶点到其他顶点的最短距离distance和最短路径下标path*/

{

----intn＝G.Vertices.size;

----int*s＝(int*)malloc(sizeof(int)*n);

----intminDis，i，j，u;

----/*初始化*/

----for(i＝0;i<n;i＋＋)---------------------

----{

--------distance［i］＝G.edge［v0］［i］;

--------s［i］＝0;

--------if(i!＝v0&&distance［i］<MaxWeight)path［i］＝v0;

--------elsepath［i］＝-1;

----}

----s［v0］＝1;--/*标记顶点v0已从集合T加入到集合S中*/

----/*在当前还未找到最短路径的顶点集中选取具有最短距离的顶点u*/

----for(i＝1;i<n;i＋＋)

----{

--------minDis＝MaxWeight;

--------for(j＝0;j<＝n;j＋＋)

------------if(s［j］＝＝0&&distance［j］<minDis)

------------{

----------------u＝j;

----------------minDis＝distance［j］;

------------}

--------/*当已不再存在路径时算法结束；此语句对非连通图是必须的*/

--------if(minDis＝＝MaxWeight)return;-----

--------s［u］＝1;-/*标记顶点u已从集合T加入到集合S中*/

--------/*修改从v0到其他顶点的最短距离和最短路径*/

--------for(j＝0;j<n;j＋＋)

-------if(s［j］＝＝0&&G.edge［u］［j］<MaxWeight&&

-------distance［u］＋G.edge［u］［j］<distance［j］)

------------{

--------/*顶