《图的基本概念和基本操作课件》由会员分享，可在线阅读，更多相关《图的基本概念和基本操作课件（190页珍藏版）》请在金锄头文库上搜索。
1、第第8章章图图8.1图的基本概念和基本操作图的基本概念和基本操作8.2图的邻接矩阵存储结构图的邻接矩阵存储结构8.3图的邻接表存储结构图的邻接表存储结构8.4图的其他存储结构图的其他存储结构8.5最小生成树最小生成树8.6最短路径最短路径8.1图的基本概念和基本操作图的基本概念和基本操作8.1.1图的基本概念图（Graph）是由顶点集合及顶点间的关系集合组成的一种数据结构。图G的定义是：G=（V，E）式中：V=x|x某个数据对象E=（x，y）|x，yV或E=x，y|x，yV并且Path（x，y）图81带自身环的图和多重图（a）带自身环的图；（b）多重图这样，在图G中，V是顶点的有穷非空集合，E
2、是顶点之间关系的有穷集合，E也叫做边的集合。图有许多复杂结构，本教材只讨论最基本的图，因此，本书讨论的图中不包括图81所示两种形式的图。图81（a）中有从顶点A到自身的边存在，称为带自身环的图;图81（b）中从顶点B到顶点D有两条无向边，称为多重图。下面我们给出图的基本概念：（1）有向图和无向图：在有向图中，顶点对x,y是有序的，顶点对x,y称为从顶点x到顶点y的一条有向边，因此，x,y与y,x是两条不同的边。有向图中的顶点对x,y用一对尖括号括起来，x是有向边的始点，y是有向边的终点，有向图中的边也称作弧。在无向图中，顶点对（x,y）是无序的，顶点对（x,y）称为与顶点x和顶点y相关联的一条
3、边，这条边没有特定的方向，（x,y）与（y,x）是同一条边。图8给出了四个图例。其中，图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,1,0,1,2。对于有向边，边的方向用箭头画出，箭头从有向边的始点指向有向边的终点。图8四个图例（a）G1；（b）G2；（c）G3；（d）G4(2)完全图：在有n个结点的无向图中，若有n(n-1)/2条边，则称此图为无向完全图。图8的G1就是无向完全图。在有n个结点
4、的有向图中，若有n(n-1)条边，则称此图为有向完全图。图8的G4就是有向完全图。完全图中的顶点个数和边的个数都达到最大值。(3)邻接顶点：在无向图G1，G2中，若（u,v）是E(G)中的一条边，则称u和v互为邻接顶点，并称边（u,v）依附于顶点u和v。在图8的无向图G1中，顶点0的邻接顶点有顶点1,2和3；在有向图G3，G4中，若u,v是E(G)中的一条边，则称顶点u邻接到顶点v，顶点v邻接自顶点u，并称边u,v与顶点u和顶点v相关联。在图8的有向图G3中，顶点1因边1,2邻接到顶点2。(4)顶点的度：顶点v的度是与它相关联的边的条数，记作TD(v)。在有向图中，顶点的度等于该顶点的入度和出
5、度之和，即TD(v)=ID(v)+OD(v)。顶点v的入度ID(v)是以v为终点的有向边的条数；顶点v的出度OD(v)是以v为始点的有向边的条数。在图8的有向图G3中，顶点1的入度ID(1)=1，顶点1的出度OD(1)=2，所以，顶点1的度TD(v)=ID(v)+OD(v)=1+2=3。可以证明，在一个有n个顶点、e条有向边（或无向边）的图中，恒有下列关系式：(5)路径：在图G=(V,E)中，若从顶点vi出发有一组边使可到达顶点vj，则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径。在图8的图G2中，从顶点0到顶点3的路径为0,1,3。(6)权：有些图的边附带有数据信息，这些附带的
6、数据信息称为权。权可以表示实际问题中从一个顶点到另一个顶点的距离、花费的代价、所需的时间，等等。带权的图称作网络。图83就是带权图。其中，图83（a）是一个工程的施工进度图，图8-3（b）是一个交通网络图。图83带权图（a）施工进度图；（b）交通网络图（7）路径长度：对于不带权的图，一条路径的路径长度是指该路径上的边的条数；对于带权的图，一条路径的路径长度是指该路径上各个边权值的总和。在图8的无向图G2中，路径0,1,3的路径长度为2；在图83（a）的有向图中，路径1,3,6,7的路径长度为16，路径1,4,7的路径长度为31。(8)子图：设有图G1=V1,E1和图G2=V2,E2，若V2V1
7、且E2E1，则称图G2是图G1的子图。(9)连通图和连通分量：在无向图中，若从顶点vi到顶点vj有路径，则称顶点vi和顶点vj是连通的。如果图中任意一对顶点都是连通的，则称该图是连通图。非连通图的极大连通子图称作连通分量。图82的无向图G1和G2都是连通图。(10)强连通图和强连通分量：在有向图中，若对于每一对顶点vi和vj都存在一条从vi到vj和从vj到vi的路径，则称该图是强连通图。非强连通图的极大强连通子图称作强连通分量。图82的有向图G4是强连通图。图82的有向图G3不是强连通图，但G3有一个强连通分量包括顶点0和顶点1，边0,1和边1,0。(11)生成树：一个连通图的极小连通子图称作
8、该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边。(12)简单路径和回路：若路径上各顶点v1,v2,vm,均互不重复，则称这样的路径为简单路径；若路径上第一个顶点v1与最后一个顶点vm重合，则称这样的路径为回路或环。8.1.2图的基本操作讨论各种类型的图都要用到的图的基本操作。(1)在图中增加一个顶点；（2）如果顶点v1和v2是图中的两个顶点，则在图中插入边(v1,v2)；（3）如果顶点v是图中的顶点，则删除图中顶点v和与顶点v相关联的所有边；（4）如果边(v1,v2)是图中的一条边，则删除边(v1,v2)；（5）如果顶点v是图中的顶点，则取顶点v的第一个邻接顶点；（6）如顶点v
9、和顶点w是图中的两个顶点且它们互为邻接顶点，则取得顶点v的w邻接顶点的下一个邻接顶点。（7）按某种规则遍历图。和树的遍历类同，图的遍历也是访问图中的每一个顶点且每个顶点只被访问一次。8.2图的邻接矩阵存储结构图的邻接矩阵存储结构8.2.1邻接矩阵我们首先定义邻接矩阵。假设图G=(V,E)有n个顶点，即V=v0,v1,vn-1，E可用如下形式的矩阵A描述，对于A中的每一个元素aij，满足：若(i,j)E或i,jE否则由于矩阵A中的元素aij表示了顶点i和顶点j之间边的关系，或者说，A中的元素aij表示了顶点i和其他顶点j（0jn-1）的邻接关系，所以矩阵A称作邻接矩阵。在图的邻接矩阵存储结构中，
10、顶点信息使用一维数组存储，边信息的邻接矩阵使用二维数组存储。图84（a）是一个无向图，图84（b）是对应的邻接矩阵存储结构。其中，V表示了图的顶点集合，A表示了图的邻接矩阵。无向图的邻接矩阵一定是对称矩阵。从无向图的定义和无向图的邻接矩阵定义可知，邻接矩阵中第i行（或第i列）中非零元素的个数等于第i个顶点的度数。又由于邻接矩阵中非零元的数值为1，所以有图84无向图及其邻接矩阵（a）无向图；（b）邻接矩阵图85（a）是一个有向图，图85（b）是对应的邻接矩阵存储结构，其中，V表示图的顶点集合，A表示图的邻接矩阵。有向图的邻接矩阵一般是非对称矩阵。从有向图的定义和有向图的邻接矩阵定义可知，有向图的
11、邻接矩阵中第i行中非零元素的个数等于第i个顶点的出度，有向图的邻接矩阵中第i列中非零元素的个数等于第i个顶点的入度，又由于邻接矩阵中非零元素的数值为1，所以有：图85有向图及其邻接矩阵（a）有向图；（b）邻接矩阵对于网（或称带权图），邻接矩阵A的定义为：ij且(i,j)E或i,jE否则但ij否则但i=j其中，wij0，wij是边(i,j)或弧，i,j的权值，权值wij表示了从顶点i到顶点j的代价或称费用。当i=j时，邻接矩阵中的元素aij=0可理解为从一个顶点到自己顶点没有代价，这也完全和实际应用中的问题模型相符。有种特殊的网允许wij为负值，本书讨论的网不包括此种网。图86（a）是一个带权图
12、，图86（b）是对应的邻接矩阵存储结构。其中，V表示图的顶点集合，A表示图的邻接矩阵。对于带权图，邻接矩阵第i行中所有0aij的元素个数等于第i个顶点的出度，邻接矩阵第j列中所有0aij的元素个数等于第j个顶点的出度。图86带权图及其邻接矩阵（a）带权图；（b）邻接矩阵8.2.2邻接矩阵表示的图类对于上述的无向图、有向图和带权图三种类型的图，其图类实现方法基本类同，如有向图中的弧a,b和弧b,a就等同于无向图中的边(a,b)，把不带权图中的边信息均定为1，不带权图就变成了带权图。因此，在上述三种类型的图中，带权图最有代表性。下面我们就以带权图为例讨论邻接矩阵表示的图类。1.图类的定义在邻接矩阵
13、表示的图中，顶点信息用一个一维数组表示，边（或称弧）信息用一个二维数组表示。在这里，顶点信息我们用第3章讨论的线性表表示，因此我们可以利用线性表实现的功能和提供的共有成员函数方便地完成顶点的插入、删除等操作。我们在第3章设计的线性表类是使用抽象数据类型Datatype来定义要操作的数据对象的，因此这里要在主函数使用图类之前定义抽象数据类型Datatype为图的顶点信息数据类型，我们的测试例子中定义图的顶点信息数据类型(Vert)为char类型。大多数情况下带权图的边信息只包含边的权值，作为教科书，我们主要注重基本原理和方法的讨论，因此我们这里设计的图类的边信息只包含边的权。注意，由于我们利用线
14、性表来保存顶点信息，所以关于顶点信息的当前个数、是否表已满无法再继续插入等均由线性表来维护，这里无需再考虑，这也正是面向对象程序设计最主要的优点之一。includeSeqList.hincludeSeqQueue.hconstintMaxVertices=10;constintMaxWeight=10000;classAdjMWGraphprivate:SeqListVertices;/顶点信息的线性表intEdgeMaxVerticesMaxVertices;/边的权信息的矩阵intnumOfEdges;/当前的边数public:AdjMWGraph(constintsz=MaxVertic
15、es);/构造函数intGraphEmpty()const/图空否returnVertices.ListEmpty();intNumOfVertices(void)/取当前顶点个数returnVertices.ListSize();intNumOfEdges(void)/取当前边个数returnnumOfEdges;VerTGetValue(constinti);/取顶点i的值intGetWeight(constintv1,constintv2);/取弧v1,v2的权/插入顶点vertexvoidInsertVertex(constVerT&vertex);/插入弧v1,v2，权为weight
16、voidInsertEdge(constintv1,constintv2,intweight);/删除顶点i和与顶点i相关的所有边voidDeleteVertex(constinti);/删除弧v1,v2voidDeleteEdge(constintv1,constintv2);/取顶点v的第一条邻接边，取到返回该邻接边的邻接顶点下标；否则返回-1intGetFirstNeighbor(constintv);/取顶点v1的邻接边的下一条邻接边，/若下一条邻接边存在，则返回该邻接边的邻接顶点下标；否则返回-1intGetNextNeighbor(constintv1,constintv2);/对
17、连通图从顶点v开始用visit()深度优先搜索访问，visited为访问标记voidDepthFirstSearch(constintv,intvisited,voidvisit(VerTitem);/对连通图从顶点v开始用visit()广度优先搜索访问，visited为访问标记voidBroadFirstSearch(constintv,intvisited,voidvisit(VerTitem);/对非连通图用visit()进行深度优先搜索访问voidDepthFirstSearch(voidvisit(VerTitem);/对非连通图用visit()进行广度优先搜索访问voidBroad
18、FirstSearch(voidvisit(VerTitem);2.成员函数的实现AdjMWGraph:AdjMWGraph(constintsz)/构造函数for(inti=0;isz;i+)for(intj=0;jsz;j+)if(i=j)Edgeij=0;elseEdgeij=MaxWeight;/MaxWeight表示无穷大numOfEdges=0;/当前边个数初始为0VerTAdjMWGraph:GetValue(constinti)/取顶点i的值if(iVertices.ListSize()cerr参数i越界出错!endl;exit(1);/使用线性表的GetData(i)成员函数
19、返回顶点i的值returnVertices.GetData(i);intAdjMWGraph:GetWeight(constintv1,constintv2)/取弧v1,v2的权if(v1 Vertices.ListSize() | v2 Vertices.ListSize()cerr参数v1或v2越界出错!endl;exit(1);returnEdgev1v2;/返回弧v1,v2的权voidAdjMWGraph:InsertVertex(constVerT&vertex)/插入顶点vertex/在顶点线性表Vertices的当前表尾ListSize()插入顶点vertexVertices.I
20、nsert(vertex,Vertices.ListSize();void AdjMWGraph:InsertEdge(const int v1,const int v2,intweight)/插入弧v1,v2，权为weightif(v1 Vertices.ListSize() | v2 Vertices.ListSize()cerr参数v1或v2越界出错!endl;exit(1);Edgev1v2=weight;/插入权为weight的边numOfEdges+;/边个数加1voidAdjMWGraph:DeleteVertex(constintv)/删除顶点v和与顶点v相关的所有边/删除与顶
21、点v相关的所有边for(inti=0;iVertices.ListSize();i+)for(intj=0;j0&EdgeijMaxWeight)Edgeij=MaxWeight;numOfEdges-;Vertices.Delete(v);/删除顶点vvoidAdjMWGraph:DeleteEdge(constintv1,constintv2)/删除弧，v1,v2if(v1Vertices.ListSize()|v2Vertices.ListSize()|v1=v2)cerr参数v1或v2出错!endl;exit(1);Edgev1v2=MaxWeight;/把该边的权值置为无穷NumOf
22、Edges-;/边个数减18.2.3邻接矩阵图类的深度优先搜索遍历和树的遍历操作类同，图的遍历操作也是图问题中最基本和最重要的操作。图的遍历操作的定义是访问图中的每一个顶点且每个顶点只被访问一次。图的遍历操作方法有两种：一种是深度优先搜索遍历，另一种是广度优先搜索遍历。图的深度优先搜索遍历类同于树的先根遍历，图的广度优先搜索遍历类同于树的层序遍历。图的遍历算法设计需要考虑三个问题：（1）图的特点是没有首尾之分，所以算法的参数要指定访问的第一个顶点；（2）对图的遍历路径有可能构成一个回路，从而造成死循环，所以算法设计要考虑遍历路径可能的回路问题；（3）一个顶点可能和若干个顶点都是相邻顶点，要使一
23、个顶点的所有相邻顶点按照某种次序被访问。我们首先考虑第（3）个问题的解决方法。为解决图的遍历操作的这个问题，我们在图的成员函数中设计了GetFirstNeighbor(v)成员函数和GetNextNeighbor(v1,v2)成员函数。GetFirstNeighbor(v)找顶点v的第一条邻接边，若存在，则返回该邻接边的邻接顶点下标；否则返回-1。GetNextNeighbor(v1,v2)找顶点v1的v1,v2邻接边的下一条邻接边，若下一条邻接边存在，则返回该邻接边的邻接顶点下标；否则返回-1。有了这两个成员函数，我们就可以从顶点v1首先找到第一条邻接边v1,v2，再从顶点v1的v1,v2邻
24、接边找顶点v1的v1,v2邻接边后的下一条邻接边，从而可以找到顶点v1的所有邻接边。这两个成员函数的算法设计如下：intAdjMWGraph:GetFirstNeighbor(constintv)/找顶点v的第一条邻接边，若存在则返回该邻接边的邻接顶点下标；否则返回-1if(vVertices.ListSize()cerr参数v1越界出错!endl;exit(1);for(intcol=0;col 0 & Edge v col MaxWeight)returncol;return-1;/不存在，则返回-1intAdjMWGraph:GetNextNeighbor(constintv1,cons
25、tintv2)/找顶点v1的v1,v2邻接边的下一条邻接边，/若下一条邻接边存在,则返回该邻接边的邻接顶点下标；否则返回-1if(v1 Vertices.ListSize() | v2 Vertices.ListSize()cerr参数v1或v2越界出错!endl;exit(1);/使col=v2+1，因此寻找的是顶点v1的v1,v2邻接边的下一条邻接边for(intcol=v2+1;col 0 & Edgev1col MaxWeight)returncol;return-1;/不存在，则返回-1对于连通图，从初始顶点出发一定存在路径和图中的所有其他顶点相连，所以对于连通图从初始顶点出发一定可
26、以遍历该图。图的深度优先遍历算法是遍历时深度优先的算法，即在图的所有邻接顶点中每次都在访问完当前顶点后首先访问当前顶点的第一个邻接顶点，这样的算法是一个递归算法。连通图的深度优先搜索遍历算法思想是：（1）访问初始顶点v并标记顶点v为已访问；（2）查找顶点v的第一个邻接顶点w；（3）若顶点v的邻接顶点w存在，则继续执行，否则算法结束；（4）若顶点w尚未被访问,则访问顶点w并标记顶点w为已访问；（5）查找顶点v的w邻接顶点后的下一个邻接顶点w，转到步骤（3）。voidAdjMWGraph:DepthFirstSearch(constintv,intvisited,voidvisit(VerTite
27、m)visit(GetValue(v);/访问顶点vvisitedv=1;/标记顶点v已访问intw=GetFirstNeighbor(v);/顶点w为顶点v的第一个邻接顶点while(w!=-1)/当邻接顶点存在时循环if(!visitedw)DepthFirstSearch(w,visited,visit);/对顶点w递归/顶点w为顶点v的w邻接顶点的下一个邻接顶点w=GetNextNeighbor(v,w);上述递归算法属于第6章讨论过的回溯算法，当寻找顶点v的邻接顶点成功时继续进行，当寻找顶点v的邻接顶点失败时回溯到上一次递归调用的地方继续进行。对于图87所示的无向连通图，若顶点A为访
28、问的首顶点，则深度优先搜索遍历的顶点访问顺序是：ABDECFG。图87无向连通图及其邻接矩阵（a）无向连通图；（b）邻接矩阵8.2.4邻接矩阵图类的广度优先搜索遍历图的广度优先遍历算法是遍历时广度优先的算法。它是一个分层搜索的过程，和树的层序遍历算法类同，它也需要一个队列以保持访问过的顶点的顺序，以便按顺序访问这些顶点的邻接顶点。连通图的广度优先搜索遍历算法思想是：（1）访问初始顶点v并标记顶点v为已访问；（2）顶点v入队列；（3）当队列非空时则继续执行，否则算法结束；（4）出队列取得队头顶点u；（5）查找顶点u的第一个邻接顶点w；（6）若顶点u的邻接顶点w存在，则继续执行，否则转到步骤（3）
29、；（7）若顶点w尚未被访问则访问顶点w并标记顶点w为已访问；(8)顶点w入队列；（9）查找顶点u的w邻接顶点后的下一个邻接顶点w，转到步骤（6）。voidAdjMWGraph:BroadFirstSearch(constintv,intvisited,voidvisit(VerTitem)VerTu,w;SeqQueuequeue;/定义队列queuevisit(GetValue(v);visitedv=1;queue.QInsert(v);/顶点v入队列while(!queue.QueueEmpty()/当队列非空时循环u=queue.QDelete();/出队列得到队头顶点uw=GetFi
30、rstNeighbor(u);while(w!=-1)/若顶点u的邻接顶点w存在时循环if(!visitedw)visit(GetValue(w);visitedw=1;queue.QInsert(w);/顶点w入队列w=GetNextNeighbor(u,w);/顶点u的w邻接顶点的下一个邻接顶点8.2.5非连通图和连通分量对于连通图，从图的任意一个顶点开始深度或广度优先遍历一定可以访问图中的所有顶点；但对于非连通图，从图的任意一个顶点开始深度或广度优先遍历并不能访问图中的所有顶点。对于非连通图，从图的任意一个顶点开始深度或广度优先遍历只能访问包括该首顶点的连通分量中的所有顶点。但当我们把每
31、一个顶点都作为一次首顶点深度或广度优先遍历非连通图，并根据顶点的访问标记来判断是否需要访问该顶点时，就一定可以访问该非连通图中的所有顶点。非连通图的深度优先搜索遍历算法如下：void AdjMWGraph:DepthFirstSearch(void visit(VerTitem)=/定义顶点访问标记数组int*visited=newintNumOfVertices();/顶点访问标记数组初始化for(inti=0;iNumOfVertices();i+)visitedi=0;for(i=0;iNumOfVertices();i+)/对所有顶点循环/如该顶点尚未被访问则以该顶点为首顶点深度优先遍
32、历访问if(!visitedi)DepthFirstSearch(i,visited,visit);deletevisited;/删除顶点访问标记数组非连通图的广度优先搜索遍历算法如下：voidAdjMWGraph:BroadFirstSearch(voidvisit(VerTitem)int*visited=newintNumOfVertices();for(inti=0;iNumOfVertices();i+)visitedi=0;for(i=0;iNumOfVertices();i+)if(!visitedi)BroadFirstSearch(i,visited,visit);delet
33、evisited;非连通图的广度优先搜索遍历算法和非连通图的深度优先搜索遍历算法类同，故不再作注释。对于图87所示的无向连通图，若删除弧0,2和2,0，则该图变为图8-8所示的非连通图。图88非连通图的深度优先搜索遍历顶点序列为：ABDECFG。图88非连通图的广度优先搜索遍历顶点序列为：ABDECFG。图88非连通图8.2.6邻接矩阵图类的测试我们以图87所示的无向连通图为例测试邻接矩阵图类。我们首先给出建立邻接矩阵图类对象的外部函数。为后面使用方便，我们把下面的结构体定义和外部函数放在文件GraphLib.h中。structRowColWeight/定义结构体类型RowColWeighti
34、ntrow;/行下标intcol;/列下标intweight;/权值;voidCreatGraph(AdjMWGraph &G,Datatype V ,intn,RowColWeightE,inte)/建立图G，所建立的图G有n个顶点V0.Vn-1，有e条边E0.Ee-1/向图G中插入n个顶点V0.Vn-1for(inti=0;in;i+)G.InsertVertex(Vi);/向图G中插入e条边E0.Ee-1for(intk=0;ke;k+)G.InsertEdge(Ek.row,Ek.col,Ek.weight);voidPrintchar(charitem)/访问顶点的函数coutite
35、m;使用图87所示的无向连通图的测试程序如下：typedefcharVerT;/顶点类型定义typedefcharDatatype;/邻接矩阵图类中所使用线性表类型定义includeAdjMWGraph.hincludeGraphLib.hvoidmain(void)AdjMWGraphg;chara=A,B,C,D,E,F,G;RowColWeightrcw=0,1,1,0,2,1,1,3,1,1,4,1,2,5,1,2,6,1,1,0,1,2,0,1,3,1,1,4,1,1,5,2,1,6,2,1;intn=7,e=12;CreatGraph(g,a,n,rcw,e);cout当前的顶点个
36、数为：g.NumOfVertices()endl;cout当前的边的条数为：g.NumOfEdges()endl;cout深度优先搜索序列为：;int*visited=newintg.NumOfVertices();for(inti=0;ig.NumOfVertices();i+)visitedi=0;g.DepthFirstSearch(0,visited,Printchar);coutendl广度优先搜索序列为：;for(i=0;ig.NumOfVertices();i+)visitedi=0;g.BroadFirstSearch(0,visited,Printchar);deletevi
37、sited;g.DeleteEdge(0,2);g.DeleteEdge(2,0);coutendl当前的顶点个数为：g.NumOfVertices();coutendl当前的边的条数为：g.NumOfEdges()endl;cout深度优先搜索序列为：;g.DepthFirstSearch(Printchar);coutendl广度优先搜索序列为：;g.BroadFirstSearch(Printchar);程序的运行结果为：当前的顶点个数为：7；当前的边的条数为：12；连通图的深度优先搜索序列为：ABDECFG；连通图的广度优先搜索序列为：ABCDEFG。删除边0,2和2,0后非连通图有当
38、前的顶点个数为：7；当前的边的条数为：10；非连通图的深度优先搜索序列为：ABDECFG；非连通图的广度优先搜索序列为：ABDECFG。8.3图的邻接表存储结构图的邻接表存储结构8.3.1图的邻接表存储结构图的邻接矩阵存储结构的主要特点是把图的边信息存储在一个nn矩阵中。其中，n为图中的顶点个数。当这个nn阶矩阵是稠密矩阵时，图的邻接矩阵存储结构是最常用也是最高效的存储结构。图89是图85（a）所示有向图的邻接表存储结构。严格地说，该图的边信息存储矩阵不是一个稀疏矩阵，因顶点个数太少，但为使我们讨论问题和表示问题不致过于麻烦，所以我们假设该图的边信息存储矩阵是一个稀疏矩阵。图89有向图的邻接表
39、存储结构图89中行数组的data域存储图的顶点信息，adj域为该顶点的邻接顶点单链表的头指针。第i行单链表中的dest域存储边i,j的邻接顶点j，对于任意一条边i,j，因i值和存储该顶点的下标值一致，所以不需要再另外存储。如果是带权图再增加cost域，第i行单链表中的dest域值为j的cost域中存储了边i,j的权值wij。对比图89和第5章图54的行指针数组结构的三元组链表，可以发现，两者讲述的是同一种存储结构。8.3.2邻接表存储结构的图类includeSeqQueue.hconstintMaxVertices=100;structEdge/边结构体定义intdest;/邻接顶点下标Dis
40、tTweight;/权Edge*next;/指针Edge()/构造函数Edge(intd,DistTw):dest(d),weight(w),next(NULL)/构造函数;structitem/顶点数组的元素类型定义VerTdata;/顶点数据Edge*adj;/邻接表指针;classAdjTWGraph/邻接表图类定义private:itemVerticesMaxVertices;/顶点数组intnumVertices;/顶点数组的当前元素个数intnumOfEdges;/当前边的条数public:AdjTWGraph(void);AdjTWGraph(void);intGraphEmpt
41、y()constreturnnumVertices=0;intNumOfVertices(void)returnnumVertices;intNumOfEdges(void)returnnumOfEdges;VerTGetValue(constinti);intGetWeight(constintv1,constintv2);voidInsertVertex(constVerT&vertex);voidInsertEdge(constintv1,constintv2,intweight);voidDeleteVertex(constintv);voidDeleteEdge(constintv1
42、,constintv2);intGetFirstNeighbor(constintv);intGetNextNeighbor(constintv1,constintv2);voidDepthFirstSearch(constintv,intvisited,voidvisit(VerTitem);voidBroadFirstSearch(constintv,intvisited,voidvisit(VerTitem);voidDepthFirstSearch(voidvisit(VerTitem);voidBroadFirstSearch(voidvisit(VerTitem);1.构造函数和析
43、构函数AdjTWGraph:AdjTWGraph(void)for(int i = 0; i MaxVertices; i+) Verticesi.adj =NULL;numVertices=0;numOfEdges=0;AdjTWGraph:AdjTWGraph(void)/释放为存储边信息所动态建立的邻接链表的空间for(inti=0;inext;deletep;p=q;2.简单成员函数的实现VerTAdjTWGraph:GetValue(constinti)if(inumVertices)cerr参数i越界出错!endl;exit(1);returnVerticesi.data;intA
44、djTWGraph:GetWeight(constintv1,constintv2)if(v1numVertices|v2numVertices)cerr参数v1或v2越界出错!destnext;if(v2!=p-dest)cerr边不存在!weight;3.插入顶点和边以及删除顶点和边成员函数的实现插入顶点成员函数很简单，只需在存放顶点信息的数组中插入一个顶点信息。voidAdjTWGraph:InsertVertex(constVerT&vertex)VerticesnumVertices.data=vertex;numVertices+;插入边v1,v2的操作是要在数组下标的v1行中的邻
45、接链表中插入一个包含dest,weight和next域的结点。其中，dest域的值为v2，邻接链表按dest域的值递增有序。这是一个建立单链表的过程，由于所建立的单链表无头指针，所以算法中要分别考虑是否是单链表的第一次插入；在不是单链表的第一次插入时,还要考虑在单链表的第一个结点前插入和在单链表的其他位置插入的情况。voidAdjTWGraph:InsertEdge(constintv1,constintv2,intweight)if(v1numVertices|v2numVertices)cerr参数v1或v2越界出错!destnext;if(pre=NULL)/在第一个结点前插入q-nex
46、t=Verticesv1.adj;Verticesv1.adj=q;else/在其他位置插入q-next=pre-next;pre-next=q;numOfEdges+;插入边成员函数算法使用的是10.2.2节将要讨论的链表插入排序算法，因此邻接表中的结点按边的弧尾顶点的大小有序排列。插入排序算法的思想是：空链表时，直接生成第一条边的弧尾顶点的dest域结点插入；第二条边的弧尾顶点结点插入到链表中的位置由v2和第一条边结点的dest域比较确定(若v2小于第一条边结点的dest,则把v2生成的结点插在第一条边的结点前；否则，把v2生成的结点插在第一条边的结点后)。关于链表插入排序算法的更详细说明
47、可参看10.2.2节。插入边成员函数算法最坏情况下的时间复杂度为O(e)，其中e为边的条数。删除顶点v时要删除和顶点v关联的所有边，这包括要删除顶点v的所有出边v,j和所有入边i,v。在邻接表存储的图中删除顶点v的所有入边i,v的算法比较麻烦，需要在所有顶点为i的单链表中寻找dest域为v的结点并删除。由于所建立的单链没有头结点，所以删除时还要分别考虑要删除结点是单链表的第一个结点和不是单链表的第一个结点的情况。在邻接表存储的图中删除顶点v的所有出边v,j的算法是逐个删除顶点数组第v行单链表的所有结点，并删除该顶点元素。voidAdjTWGraph:DeleteVertex(constintv
48、)Edge*pre,*curr;for(inti=0;idestnext;if(pre=NULL&curr-dest=v)/该出边结点是单链表的第一个结点时Verticesi.adj=curr-next;deletecurr;numOfEdges-;elseif(curr!=NULL&curr-dest=v)/该出边结点是单链表的其他结点时pre-next=curr-next;deletecurr;numOfEdges-;Edge*p=Verticesv.adj,*q;for(i=v;inext;deletep;/释放空间p=q;numOfEdges-;从上述算法中可以看出，在邻接表中，为寻找
49、邻接到顶点v的邻接顶点，即寻找边i,v的顶点i，必须遍历整个邻接表，在每一个按弧尾顶点序号有序的单链表中寻找结点的dest域值等于v的结点。因此其时间复杂度为O(ne)。其中，n为顶点个数，e为边的条数。删除边v1,v2的算法是在顶点数组的第v1行中删除结点的dest域为v2的结点。由于所建立的单链没有头结点，同样在删除时要分别考虑要删除结点是单链表的第一个结点和不是单链表的第一个结点的情况。voidAdjTWGraph:DeleteEdge(constintv1,constintv2)if(v1numVertices|v2numVertices)cerr参数v1或v2越界出错!destnex
50、t;if(pre=NULL&curr-dest=v2)/要删结点是单链表的第一个结点Verticesv1.adj=curr-next;deletecurr;numOfEdges-;elseif(pre!=NULL&curr-dest=v2)/不是单链表的第一个结点pre-next=curr-next;deletecurr;numOfEdges-;else/参数出错，该边不存在cerr边不存在!endl;exit(1);4.遍历成员函数要调用的成员函数intAdjTWGraph:GetFirstNeighbor(constintv)if(vnumVertices)cerr参数v1越界出错!des
51、t;elsereturn-1;intAdjTWGraph:GetNextNeighbor(constintv1,constintv2)if(v1numVertices|v2numVertices)cerr参数v1或v2越界出错!next != NULL & p-dest = v2) return p-next-dest;elsep=p-next;return-1;5.遍历成员函数由于遍历图的深度优先遍历算法和图的广度优先遍历算法是固定不变的算法，而这两个算法的成员函数实现都是通过调用GetFirstNeighbor(v)和GetNextNeighbor(v1,v2)实现的，所以邻接表实现的图类
52、的遍历成员函数和邻接矩阵实现的图类的遍历成员函数的实现过程完全一样。我们在这里只列出一个连通图的深度优先搜索遍历成员函数DepthFirstSearch(visit)，其余的不再列出。voidAdjTWGraph:DepthFirstSearch(constintv,intvisited,voidvisit(VerTitem)visit(GetValue(v);visitedv=1;intw=GetFirstNeighbor(v);while(w!=-1)if(!visitedw)DepthFirstSearch(w,visited,visit);w=GetNextNeighbor(v,w);
53、8.3.3邻接表存储结构图类的测试邻接表存储结构图类的测试程序和8.2.6节的邻接矩阵存储结构图类的测试程序基本相同。不相同的部分主要是类型定义符和包含的头文件不同，即测试文件的开头部分不同。不相同部分如下：typedefcharVerT;typedefintDistT;typedefcharDatatype;includeAdjTWGraph.h另一个不相同之处是主函数中的图类对象的定义语句不同，这里的图类对象的定义语句为：AdjTWGraphg;。在主函数调用的创建图的函数CreatGraph(G,V,n,E,e)中，除图G的类型定义不同外，其他部分也完全相同，图G的类型定义为AdjTWG
54、raph&G。该测试程序的测试结果和8.2.6节的测试结果完全相同。为节省篇幅，所有相同部分就不再列出。8.4图的其他存储结构图的其他存储结构8.4.1逆邻接表从上述图的邻接表存储结构类的成员函数实现算法中可以看出，在邻接表中，为求顶点v的入度，即为求边i,v中的顶点i，必须遍历整个邻接表，在每一个单链表中寻找结点dest域值等于v的结点，其时间复杂度为O(ne)。其中，n为顶点个数，e为边的条数。为了便于确定顶点v的入度或以v为头的弧，可以建立图的逆邻接表，即对图中每个顶点v建立一个和邻接表结构类同的单链表，只是这个单链表的dest域改名为source域。source域中存放的是邻接到顶点v
55、的邻接顶点下标，逆邻接表也因此而得名。图85（a）的有向图的逆邻接表存储结构如图810所示。图810逆邻接表在逆邻接表中求顶点v入度最坏情况下的时间复杂度为O(e)。其中，e为边的条数。但是，由于每条边既在邻接表中存储，又在逆邻接表中存储，所以此时插入边和删除边的成员函数要同时对邻接表和逆邻接表进行维护。8.4.2十字链表在图的邻接表和逆邻接表存储结构中，每条边的信息都既要存储在邻接表中，又要存储在逆邻接表中，这增加了插入边和删除边成员函数的算法复杂性。十字链表存储结构是解决这个问题的一个方法。十字链表存储结构既可以方便地表示邻接表和逆邻接表，又使每条边只存储了一个结点。十字链表中每个结点的结
56、构定义为：headVertailVerwieghttailNextheatNext其中：headVer为弧头下标域；tailVer为弧尾下标域；headNext为以顶点tailVer为弧尾的下一个弧头结点指针域，即headNext为顶点tailVer的入边链指针域；tailNext为以顶点headVer为弧头的下一个弧尾结点指针域，即tailNext为顶点headVer的出边链指针域；weight为边headVer,tailVer的权值域。十字链表中顶点数组元素结构定义为：datafirstInfirstOut其中：data为顶点信息域，firstIn为该顶点的入边指针域，firstOut为该
57、顶点的出边指针域。图811给出了一个带权有向图和对应的十字链表存储结构。图中链表的结点各个域的排列次序和上边给出的结点结构定义次序相同。可以看出，该图共有7条边，对应的十字链表存储结构也只有7个结点。图811带权有向图及其十字链表存储结构（a）带权有向图；（b）十字链表存储结构8.4.3邻接多重表在无向图的邻接表存储结构中，一条无向边(v1,v2)被存储在顶点v1的邻接单链表和顶点v2的邻接单链表中。此外，若要删除一条无向边(v1,v2)，又需两次扫描邻接表，寻找无向边(v1,v2)的两个结点并删除。对于无向图的邻接表存储结构，我们可以改进存储结构为邻接多重表存储结构。在邻接多重表中，存储一条
58、无向边(v1,v2)的结点只有一个。结点的结构为：markheadVertailVerweightheadNexttailNext其中：mark为标志域，用来标记该边是否被访问过，结点结构中也可无此域；headVer为弧头下标域；tailVer为弧尾下标域；weight为边（headVer,tailVer）的权值域；headNext为以顶点tailVer为弧尾的下一个弧头结点指针域，即headNext为顶点tailVer的入边链指针域；tailNext为以顶点headVer为弧头的下一个弧尾结点指针域，即tailNext为顶点headVer的出边链指针域。要指出的是，由于一条无向边在多重表存储
59、结构中只有一个结点，所以从顶点tailVer到顶点headVer的边结点也就是从顶点headVer到顶点tailVer的边结点。顶点数组元素的结构和邻接表的相同，即一个data域和一个指向该顶点链表的指针first域。图812是一个无向图及其邻接多重表存储结构。可以看出，在邻接多重表存储结构中，每条无向边只存储了一个结点。图812无向图及其邻接多重表存储结构（a）无向图；（b）邻接多重表存储结构8.5最小生成树最小生成树8.5.1最小生成树的基本概念一个有n个顶点的连通图的生成树是原图的极小连通子图，它包含原图中的所有n个顶点，并且有保持图连通的最少的边。由生成树的定义可知:（1）若在生成树中
60、删除一条边，就会使该生成树因变成非连通图而不再满足生成树的定义；（2）若在生成树中增加一条边,就会使该生成树中因存在回路而不再满足生成树的定义；（3）一个连通图的生成树可能有许多。使用不同的遍历图的方法可以得到不同的生成树。如对无向图使用深度优先搜索遍历方法与使用广度优先搜索遍历方法将会得到两个结构不同的生成树；从不同的顶点出发，也可以得到不同的生成树。图8-13给出了一个无向图和它的两棵不同的生成树。图813无向图和它的不同的生成树（a）无向图；（b）生成树1；（c）生成树2从最小生成树的定义可知，构造有n个顶点的无向连通网的最小生成树必须满足以下三条：（1）构造的最小生成树必须包括n个顶点
61、；（2）构造的最小生成树中有且只有n-1条边；（3）构造的最小生成树中不存在回路。构造的最小生成树的方法有许多种，典型的构造方法有两种:一种称作普里姆（Prim）算法，另一种称作克鲁斯卡尔（Kruskal）算法。8.5.2普里姆算法假设G=(V,E)是一个网络，其中V为网中顶点的集合，E为网中带权边的集合。设置两个新的集合U和T，其中U用于存放网G的最小生成树的顶点的集合，T用于存放网G的最小生成树的带权边的集合。令集合U的初值为U=u0（即假设构造最小生成树时均从顶点u0开始），集合T的初值为T=。普里姆算法的思想是：从所有顶点uU和顶点vV-U的带权边中选出具有最小权值的边(u,v)，将顶
62、点v加入集合U中，将边(u,v)加入集合T中。如此不断重复，直到U=V时即构造完毕。此时集合U中存放着最小生成树的顶点的集合，集合T中存放着最小生成树的带权边的集合。图814给出了用普里姆算法构造最小生成树的过程。图814（a）是一个有7个顶点、10条无向边的带权图。初始时算法的集合U=A， 集 合 V-U=B,C,D,E,F,G， T=， 如 图814（b）所示。在所有u为集合U中顶点，v为集合V-U中顶点的边(u,v)中，寻找具有最小权值的边(u,v)，寻找到的是边(A,B)，权为50，把顶点B从集合V-U加入 到 集 合 U中 ， 把 边 (A,B)加 入 到 T中 ， 如 图814（c
63、）所示。在所有u为集合U中顶点，v为集合V-U中顶点的边(u,v)中寻找具有最小权值的边(u,v)，寻找到的是边(B,E)，权为40，把顶点E从集合V-U加入到集合U中，把边(B,E)加入到T中，如图814（d）所示；随后依次从集合V-U加入到集合U中的顶点为D,F,G,C，依次加入到T中的边为(E,D),权为50，(D,F)权为30，(D,G)权为42，(G,C)权为45，分别如图814(e),(f),(g),(h)所示。最后得到的图814（h）就是原带权连通图的最小生成树。图814普里姆算法构造最小生成树的过程图814普里姆算法构造最小生成树的过程图814普里姆算法构造最小生成树的过程我们
64、再来讨论普里姆算法的实现问题。普里姆算法要处理的带权图对象G可以是前面讨论过的任意存储结构的图类。我们下面讨论的普里姆算法使用邻接矩阵的图类，算法中定义的对象G的顶点集合就是普里姆算法中的集合V，对象G的边集合就是普里姆算法中的集合E。普里姆算法所构造的最小生成树是集合U和集合T，集合U是顶点的集合，集合T是带权边的集合。要表示一条带权边需有三个参数，即弧头顶点、弧尾顶点和权值，但考虑到集合U中对应位置上已有弧尾顶点，而弧头顶点是未加入新生成顶点前集合U中的一个顶点，所以算法实现时可设置一个包括两个域的数组，一个域是新加入到最小生成树中边的弧尾顶点，另一个域是新加入到最小生成树中边的权值。由这
65、两个参数用户可以对照网G找到新加入到最小生成树中边的弧头顶点。这样实现的普里姆算法可以大大简化算法实现过程。因此，普里姆算法构造的最小生成树的数组元素结构定义为：StructMinSpanTreeVerTvertex;/顶点信息Intweight;/权值;我们下面设计了实现普里姆算法的外部函数，也可以把它设计成某个图类的成员函数，设计成成员函数的方法和设计成外部函数的方法类同。用普里姆方法建立网G的最小生成树minSTree的外部函数如下：structMinSpanTreeVerTvertex;intweight;voidPrim(AdjMWGraph&G,MinSpanTreeminSTre
66、e)/用普里姆方法建立网G的最小生成树minSTreeintn=G.NumOfVertices(),minCost;int*lowCost=newintn;inti,j,k;for(i=1;in;i+)/初始化lowCosti=G.GetWeight(0,i);closeVertexi.vertex=G.GetValue(0);/从序号为0的顶点出发构造最小生成树minSTree0.vertex=G.GetValue(0);cout顶点值=G.GetValue(0)endl;for(i=1;in;i+)/寻找当前最小权值的边的顶点minCost=MaxWeight;/MaxWeight为图类中
67、定义的最大权值j=1;k=1;while(jn)if(lowCostjminCost&lowCostj!=0)minCost=lowCostj;k=j;j+;cout顶点值=G.GetValue(k)边的权值=minCostcoutendl;lowCostk=0;/修改其他顶点的边的权值*/for(intj=1;jn;j+)if(G.GetWeight(k,j)lowCostj)lowCostj=G.GetWeight(k,j);minSTreej.vertex=G.GetValue(k);上述函数存放在文件Prim.h中。分析上述普里姆算法可见，算法主要是一个两重循环，其中每一重循环的次数均
68、为顶点个数n，所以该算法的时间复杂度为O(n2)。由于该算法的时间复杂度只与网中顶点的个数有关，而与网中边的条数无关，所以当该算法用于顶点个数不很多而边稠密的网时，时间效率较高。以图814（a）所示的无向连通网为例，上述普里姆算法函数的测试程序如下：typedefcharVerT;typedefcharDatatype;includeAdjMWGraph.hincludePrim.hincludeGraphLib.h“/包含CreatGraph()函数voidmain(void)AdjMWGraphg;chara=A,B,C,D,E,F,G;RowColWeightrcw=0,1,50,1,0
69、,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);intm=g.NumOfVertices();MinSpanTree*closeVertex=newMinSpanTreem;Prim(g,closeVertex);程序的运行结果为：顶点值=A顶点值=B边的权值=50顶点值=E边的权值=40顶点值=D边的权值=50顶
70、点值=F边的权值=30顶点值=G边的权值=42顶点值=C边的权值=45程序显示的顶点序列和边的权值序列对应了图814（b）到图814（h）的最小生成树构造过程。在解决实际问题时，我们根据上述程序运行的结果，再结合原问题的网，在这里为图814（a），即可构造出图814（a）的最小生成树图814（h）。另外，函数的返回参数minSTree中也存放了类似的结果，可用于其他使用最小生成树的应用程序的输入参数。8.5.3克鲁斯卡尔算法与普里姆算法不同，克鲁斯卡尔算法是一种按照网中边的权值的递增顺序构造最小生成树的方法。克鲁斯卡尔算法的思想是：设无向连通网G=(V,E)，其中V为顶点的集合，E为边的集合。
71、设网G的最小生成树T由顶点集合和边的集合构成，其初值为T=(V,)，即初始时最小生成树T只由网G中的顶点集合组成，各顶点之间没有一条边。对于图814（a）所示的无向连通网，按照克鲁斯卡尔算法构造最小生成树的过程如图815所示。根据克鲁斯卡尔算法构造最小生成树的方法，按照网G中边的权值从小到大的顺序，反复选择当前尚未被选取的边集合中权值最小的边加入到最小生成树中，直到网中所有顶点都加入到最小生成树中为止。最后，图815（f）所示就是所构造的最小生成树。对比图815（f）和图814（h）可以发现，虽然构造最小生成树的方法不同，但克鲁斯卡尔算法构造的最小生成树和普里姆算法构造的最小生成树结构完全相同
72、。图815克鲁斯卡尔算法构造最小生成树的过程按照上述克鲁斯卡尔算法思想设计克鲁斯卡尔算法函数主要包括两个部分：首先是网G中e条边的权值的排序，其次是判断新选取的边的两个顶点是否属于同一个连通分量。对网G中e条边的权值的排序方法可以有很多种，各自的时间复杂度均不相同。对e条边的权值排序算法时间复杂度最好的方法如快速排序法、堆排序法等可以达到O(elbe)。判断新选取的边的两个顶点是否属于同一个连通分量的问题是一个在最多有n个结点的生成树中遍历寻找新选取的边的两个顶点是否存在的问题，此算法的时间复杂度最坏情况下为O(n)。一个连通分量还可以看作是一个等价类，判断新选取的边的两个顶点是否属于同一个连
73、通分量的问题可以看作是一个求等价类的过程。等价类属于集合结构，本书没有讨论。关于排序问题我们将在第9章讨论。从上述分析我们可以得出，克鲁斯卡尔算法的时间复杂度主要由排序方法决定，而克鲁斯卡尔算法的排序方法只与网中边的个数有关，而与网中顶点的个数无关，当使用时间复杂度为O(elbe)的排序方法时，克鲁斯卡尔算法的时间复杂度即为O(elbe)，因此当网的顶点个数较多、而边的条数较少时，使用克鲁斯卡尔算法构造最小生成树效果较好。8.6最短路径最短路径8.6.1最短路径的基本概念在一个图中，若从一个顶点到另一个顶点存在着一条路径，则称该路径的路径长度为该路径上所经过的边的数目。图中从一个顶点到另一个顶
74、点可能存在着多条路径，我们把路径长度最短的那条路径叫做最短路径，其路径长度叫做最短路径长度或最短距离。在一个网中，若从一个顶点到另一个顶点存在着一条路径，则称该路径上所经过边的权值之和为该路径上的带权路径长度。网中从一个顶点到另一个顶点可能存在着多条路径，我们把带权路径长度最短的那条路径也叫做最短路径，其带权路径长度也叫做最短路径长度或最短距离。实际上，不带权的图上最短路径问题也可以归结为带权的网上最短路径问题。因只要把不带权的图上所有边上的权值均定义为1，则不带权的图上最短路径问题也就归结为带权的网上最短路径问题了。因此不失一般性，我们这里只讨论带权的网上最短路径问题。网有无向网和有向网，当
75、把无向网中的每一条边(vi,vj)都定义为弧vi,vj和弧vj,vi，则有向网就变成了无向网。因此不失一般性，我们这里只讨论带权的有向网上最短路径问题。图816是一个有向网和它的邻接矩阵。该网从顶点A到顶点D有三条路径，分别为路径（A,D），其带权路径长度为30；路径（A,C,F,D），其带权路径长度为22；路径（A,C,B,E,D），其带权路径长度为32；路径（A,C,F,D）称为最短路径，其带权路径长度22称为最短距离。图816有向网及其邻接矩阵（a）有向网；（b）邻接矩阵8.6.2从一个顶点到其余各顶点的最短路径对于从有向网中一个确定顶点（称为源点）到其余各顶点的最短路径问题，狄克斯特拉
76、(Dijkastra)提出了一个按路径长度递增的顺序逐步产生最短路径的构造算法，狄克斯特拉算法的思想是：设置两个顶点的集合S和T，集合S中存放已找到最短路径的顶点，集合T中存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点，设为v0。然后，不断从集合T中选择到源点v0路径长度最短的顶点u加入到集合S中。集合S中每加入一个新的顶点u，都要修改源点v0到集合T中剩余顶点的当前最短路径长度值。集合T中各顶点的新的当前最短路径长度值，为原来的当前最短路径长度值与顶点u的最短路径长度值加上顶点u到该顶点的路径长度值（即为从源点过顶点u到达该顶点的路径长度）中的较小者。此过程不断重复，直到集合
77、T中的顶点全部加入到集合S中为止。对于图816所示的有向网，图817给出了狄克斯特拉算法求从顶点A到其余各顶点的最短路径的过程。图中，虚线表示当前可选择的边，实线表示算法已确定包括到集合S中的顶点所对应的边。图817狄克斯特拉算法求从顶点A到其余各顶点的最短路径的过程函数设计成迭代过程。设从源点v0到其余各顶点中最短的一条路径为(v0,vk)，其中vk满足：distancevk=mindistancevi|viV-v0V是网G的顶点一旦确定distancevk且distancevk小于最大权值，则标识顶点vk已从集合T到集合S中。根据上述设计思想设计的外部函数如下，该外部函数也可方便地改为图类
78、的成员函数。voidDijkstra(AdjMWGraph&G,intv0,intdistance ,intpath)/网G从下标v0顶点到其他顶点的最短距离distance和最短路径下标pathintn=G.NumOfVertices();int*s=newintn;intminDis,i,j,u;/初始化for(i=0;in;i+)distancei=G.GetWeight(v0,i);si=0;if(i!=v0&distanceiMaxWeight)pathi=v0;elsepathi=-1;sv0=1;/标记顶点v0已从集合T加入到集合S中/在当前还未找到最短路径的顶点集中选取具有最短
79、距离的顶点ufor(i=1;in;i+)minDis=MaxWeight;for(j=0;j=n;j+)if(sj=0&distancejminDis)u=j;minDis=distancej;/当已不再存在路径时算法结束；此语句对非连通图是必需的if(minDis=MaxWeight)return;su=1;/标记顶点u已从集合T加入到集合S中/修改从v0到其他顶点的最短距离和最短路径for(j=0;jn;j+)if(sj=0&G.GetWeight(u,j)MaxWeight&distanceu+G.GetWeight(u,j)distancej)/顶点v0经顶点u到其他顶点的最短距离和最
80、短路径distancej=distanceu+G.GetWeight(u,j);pathj=u;上述函数的主体是两个循环次数为顶点个数n的循环，所以该函数的时间复杂度为O(n2)。以图816的有向网为例的测试程序如下：typedefcharVerT;typedefcharDatatype;includeAdjMWGraph.hincludeDijkstra.hincludeGraphLib.hvoidmain(void)AdjMWGraphg;chara=A,B,C,D,E,F;RowColWeightrcw=0,2,5,0,3,30,1,0,2,1,4,8,2,1,15,2,5,7,4,3,
81、4,5,3,10,5,4,18;intn=6,e=9;CreatGraph(g,a,n,rcw,e);intm=g.NumOfVertices();int*distance=newintm;int*path=newintm;intv0=0;Dijkstra(g,v0,distance,path);cout从顶点g.GetValue(v0)到其他各顶点的最短距离为：endl;for(inti=0;im;i+)cout到顶点g.GetValue(i)的最短距离为：distanceiendl;cout从顶点g.GetValue(v0)到其他各顶点最短路径的前一顶点为：endl;for(i=0;im;
82、i+)if(pathi!=-1)cout到顶点g.GetValue(i)的前一顶点为g.GetValue(pathi)endl;程序的运行结果如下：从顶点A到其他各顶点的最短距离为：到顶点A的最短距离为：0到顶点B的最短距离为：20到顶点C的最短距离为：5到顶点D的最短距离为：22到顶点E的最短距离为：28到顶点F的最短距离为：12从顶点A到其他各顶点最短路径的前一顶点为：到顶点B的前一顶点为：C到顶点C的前一顶点为：A到顶点D的前一顶点为：F到顶点E的前一顶点为：B到顶点F的前一顶点为：C当测试程序的v0=3时的运行结果如下：从顶点D到其他各顶点的最短距离为：到顶点A的最短距离为：10000
83、到顶点B的最短距离为：10000到顶点C的最短距离为：10000到顶点D的最短距离为：0到顶点E的最短距离为：10000到顶点F的最短距离为：10000如果在函数中没有语句：if(minDis=MaxWeight)return;则当v0=3时，因从源点v0到其他顶点没有路径存在而出错。8.6.3所有顶点之间的最短路径对于一个各边权值均大于0的有n个顶点的带权有向图，若要求所有顶点之间的最短路径和最短距离，可轮流以每一个顶点为源点，重复调用上述狄克斯特拉算法函数Dijkstra()n次，即可求得所有顶点之间的最短路径和最短距离。利用Dijkstra()函数求所有顶点之间的最短路径算法如下。其中，
84、distancei中存放着从顶点i到其他顶点的最短距离，pathi中存放着从顶点i到其他顶点的最短路径的前一顶点下标。voidShortPath(AdjMWGraph&G,int*distance,int*path)intn=G.NumOfVertices();for(inti=0;in;i+)Dijkstra(G,i,distancei,pathi);由于狄克斯特拉算法的时间复杂度是O(n2)，所以n次调用狄克斯特拉算法的时间复杂度是O(n3)。以图816的有向网为例的测试程序如下。其中，函数Make2DArray()为5.2节讨论的两维动态数组。include/包含getch()函数typ
85、edefcharVerT;typedefcharDatatype;includeAdjMWGraph.hincludeDijkstra.hincludeGraphLib.hvoidShortPath(AdjMWGraph&G,int*distance,int*path)intn=G.NumOfVertices();for(inti=0;in;i+)Dijkstra(G,i,distancei,pathi);templatevoidMake2DArray(T*&a,introw,intcol)/定义二维动态数组a，其行数为row,列数为cola=newT*row;/a为有row个指针的指针数组f
86、or(inti=0;irow;i+)ai=newTcol;/每个指针指向一个有col个元素空间的数组voidmain(void)AdjMWGraphg;chara=A,B,C,D,E,F;RowColWeightrcw=0,2,5,0,3,30,1,0,2,1,4,8,2,1,15,2,5,7,4,3,4,5,3,10,5,4,18;intn=6,e=9;CreatGraph(g,a,n,rcw,e);intm=g.NumOfVertices();int*distance,*path;Make2DArray(distance,m,m);Make2DArray(path,m,m);ShortPa
87、th(g,distance,path);inti,j;for(i=0;im;i+)cout从顶点g.GetValue(i)到其他各顶点的最短距离为：endl;for(j=0;jm;j+)cout到顶点g.GetValue(j)的最短距离为：distanceijendl;cout从顶点g.GetValue(i)到其他各顶点最短路径的前一顶点分别为：endl;for(j=0;jm;j+)if(pathij!=-1)cout到顶点g.GetValue(j)的前一顶点为g.GetValue(pathij)endl;getch();/键入任意键继续，以便观察屏幕在递推求最短距离Anij的过程中，我们同时
88、定义pathkij。pathkij保存从顶点vi到顶点vj递推产生的最短路径的顶点序号，且该最短路径上所经过的顶点序号不大于k。根据上述弗洛伊德算法思想求所有顶点之间的最短路径和最短距离的函数如下：voidFloyd(AdjMWGraph&G,int*distance,int*path)/求图G中每对顶点之间的最短距离distance和最短路径的顶点序号pathinti,j,k;intn=G.NumOfVertices();/初始化for(i=0;in;i+)for(j=0;jn;j+)distanceij=G.GetWeight(i,j);if(i!=j&distanceij!=MaxWei
89、ght)pathij=i;elseif(i=j)pathij=0;elsepathij=-1;for(k=0;kn;k+)for(i=0;in;i+)for(j=0;j(distanceik+distancekj)distanceij=distanceik+distancekj;pathij=pathkj;如前面所分析的，在第k+1次递推时存在两种可能性，从顶点vi到顶点vj又产生一条经过序号为k+1顶点的路径和不存在经过序号为k+1的顶点的路径。当从顶点vi到顶点vj又产生一条经过序号为k+1顶点的路径时，还要判断新产生路径的距离是否比原来路径的距离短；当距离短时替换，否则不替换。上述算法产
90、生的最短路径的顶点序列中间的若干个顶点序号会出现不连续，但可根据最短距离和原始网的邻接矩阵识别出，即此最短路径的顶点序列可作辅助参考。u%rZoWlThQeNbJ8G4D1A-w*t$qYnVjSgPdLaI7F3C0y)v&s#pXmUiRfNcK9H5E2B+x(u$rZoWkThQeMbJ7G4D1z-w*t!qYnVjSgOdLaI6F3C0y)v%s#pXlUiRfNcK8H5E2A+x(u$rZnWkThPeMbJ7G4C1z-w&t!qYmVjRgOdL9I6F3B0y(v%s#oXlUiQfNbK8H5D2A+x*u$rZnWkShPeMaJ7G4C1z)w&t!pYmVjRg
91、OcL9I6E3B0y(v%r#oXlTiQfNbK8G5D2A-x*u$qZnVkShPdMaJ7F4C0z)w&s!pYmUjRgOcL9H6E3B+y(v%r#oWlTiQeNbK8G5D1A-x*t$qZnVkSgPdMaI7F4C0z)v&s!pXmUjRfOcK9H6E2B+y(u%rZoWlThQeNbJ8G4D1A-w*t$qYnVkSgPdLaI7F3C0z)v&s#pXmUiRfOcK9H5E2B+x(u%rZoWkThQeMbJ8G4D1z-w*t!qYnVjSgOdLaI6F3C0y)v%s#pXlUiRfNcK9H5E2A+x(u$rZoWkThPeMbJ7G4D1z
92、-w&t!qYmVjSgOdL9I6F3B0y)v%s#oXlUiQfNcK8H5D2A+x*u$rZnWkShPeMaJ7G4C1z-w&t!pYmVjRgOdL9I6E3B0y(v%s#oXlTiQfNbK8H5D2A-x*u$qZnWkShPdMaJ7F4C1z)w&s!pYmUjRgOcL9H6E3B+y(v%r#oWlTiQeNbK8G5D2A-x*t$qZnVkShPdMaI7F4C0z)w&s!pXmUjRfOcL9H6E2B+y(u%r#oWlThQeNbJ8G5D1A-w*t$qYnVkSgPdLaI7F3C0z)v&s!pXmUiRfOcK9H6E2B+x(u%rZoWlT
93、hQeMbJ8G4D1A-w*t!qYnVjSgPdLaI6F3C0y)v&s#pXlUiRfNcK9H5E2A+x(u$rZoWkThPeMbJ7G4D1z-w*t!qYmVjSgOdLaI6F3B0y)v%s#pXlUiQfNcK8H5E2A+x*u$rZnWkThPeMaJ7G4C1z-w&t!pYmVjRgOdL9I6E3B0y(v%s#oXlUiQfNbK8H5D2A+x*u$qZnWkShPeMaJ7F4C1z)w&t!pYmUjRgOcL9I6E3B+y(v%r#oXlTiQeNbK81z-w&t!qYmVjRgOdL9I6F3B0y(v%s#oXlUiQfNbK8H5D2A+x
94、*u$qZnWkShPeMaJ7F4C1z)w&t!pYmUjRgOcL9I6E3B+y(v%r#oXlTiQeNbK8G5D2A-x*u$qZnVkShPdMaJ7F4C0z)w&s!pYmUjRfOcL9H6E3B+y(u%r#oWlTiQeNbJ8G5D1A-x*t$qYnVkSgPdMaI7F3C0z)v&s!pXmUjRfOcK9H6E2B+y(u%rZoWlThQeNbJ8G4D1A-w*t$qYnVjSgPdLaI7F3C0y)v&s#pXmUiRfNcK9H5E2B+x(u$rZoWkThQeMbJ7G4D1z-w*t!qYnVjSgOdLaI6F3C0y)v%s#pXlUiR
95、fNcK8H5E2A+x(u$rZnWkThPeMbJ7G4C1z-w&t!qYmVjRgOdL9I6F3B0y(v%s#oXlUiQfNcK8H5D2A+x*u$rZnWkShPeMaJ7G4C1z)w&t!pYmVjRgOcL9I6E3B0y(v%r#oXlTiQfNbK8G5D2A-x*u$qZnVkShPdMaJ7F4C1z)w&s!pYmUjRgOcL9H6E3B+y(v%r#oWlTiQeNbK8G5D1A-x*t$qZnVkSgPdMaI7F4C0z)v&s!pXmUjRfOcK9H6E2B+y(u%rZoWlThQeNbJ8G5D1A-w*t$qYnVkSgPdLaI7F3C0
96、z)v&s#pXmUiRfOcK9H5E2B+x(u%rZoWkThQeMbJ8G4D1z-w*t!qYnVjSgOdLaI6F3C0y)v&s#pXlUiRfNcK9H5E2A*t$qYnVkSgPdLaI7F3C0z)v&s#pXmUiRfOcK9H5E2B+x(u%rZoWkThQeMbJ8G4D1z-w*t!qYnVjSgPdLaI6F3C0y)v&s#pXlUiRfNcK9H5E2A+x(u$rZoWkThPeMbJ7G4D1z-w&t!qYmVjSgOdL9I6F3B0y)v%s#oXlUiQfNcK8H5E2A+x*u$rZnWkThPeMaJ7G4C1z-w&t!pYmVjRg
97、OdL9I6E3B0y(v%s#oXlTiQfNbK8H5D2A-x*u$qZnWkShPdMaJ7F4C1z)w&t!pYmUjRgOcL9I6E3B+y(v%r#oXlTiQeNbK8G5D2A-x*t$qZnVkShPdMaI7F4C0z)w&s!pXmUjRfOcL9H6E2B+y(u%r#oWlThQeNbJ8G5D1A-x*t$qYnVkSgPdMaI7F3C0z)v&s!pXmUiRfOcK9H6E2B+x(u%rZoWlThQeMbJ8G4D1A-w*t!qYnVjSgPdLaI6F3C0y)v&s#pXmUiRfNcK9H5E2B+x(u$rZoWkThQeMbJ7G4D1z
98、-w*t!qYmVjSgOdLaI6F3B0y)v%s#pXlUiQfNcK8H5E2A+x*u$rZnWkThPeMaJ7C0y)v&s#pXmUiRfNcK9H5E2B+x(u$rZoWkThQeMbJ7G4D1z-w*t!qYmVjSgOdLaI6F3B0y)v%s#pXlUiQfNcK8H5E2A+x(u$rZnWkThPeMbJ7G4C1z-w&t!qYmVjRgOdL9I6F3B0y(v%s#oXlUiQfNbK8H5D2A+x*u$qZnWkShPeMaJ7F4C1z)w&t!pYmVjRgOcL9I6E3B0y(v%r#oXlTiQfNbK8G5D2A-x*u$qZnVkShP
99、dMaJ7F4C0z)w&s!pYmUjRfOcL9H6E3B+y(u%r#oWlTiQeNbJ8G5D1A-x*t$qZnVkSgPdMaI7F4C0z)v&s!pXmUjRfOcK9H6E2B+y(u%rZoWlThQeNbJ8G4D1A-w*t$qYnVjSgPdLaI7F3C0y)v&s#pXmUiRfOcK9H5E2B+x(u%rZoWkThQeMbJ8G4D1z-w*t!qYnVjSgOdLaI6F3C0y)v%s#pXlUiRfNcK8H5E2A+x(u$rZnWkThPeMbJ7G4C1z-w&t!qYmVjSgOdL9I6Fx(u%rZoWkThQeMbJ8G4D1z-w*t
100、!qYnVjSgOdLaI6F3C0y)v%s#pXlUiRfNcK8H5E2A+x(u$rZoWkThPeMbJ7G4D1z-w&t!qYmVjSgOdL9I6F3B0y)v%s#oXlUiQfNcK8H5D2A+x*u$rZnWkShPeMaJ7G4C1z)w&t!pYmVjRgOdL9I6E3B0y(v%s#oXlTiQfNbK8H5D2A-x*u$qZnWkShPdMaJ7F4C1z)w&s!pYmUjRgOcL9H6E3B+y(v%r#oWlTiQeNbK8G5D1A-x*t$qZnVkShPdMaI7F4C0z)w&s!pXmUjRfOcL9H6E2B+y(u%r#oWlThQeN
101、bJ8G5D1A-w*t$qYnVkSgPdLaI7F3C0z)v&s#pXmUiRfOcK9H6E2B+x(u%rZoWlThQeMbJ8G4D1A-w*t!qYnVjSgPdLaI6F3C0y)v&s#pXlUiRfNcK9H5E2A+x(u$rZoWkThPeMbJ7G4D1z-w&t!qYmVjSgOdLaI6F3B0y)v%s#pXlUiQfNcK8D1A-w*t!qYnVjSgPdLaI6F3C0y)v&s#pXlUiRfNcK9H5E2A+x(u$rZoWkThQeMbJ7G4D1z-w*t!qYmVjSgOdLaI6F3B0y)v%s#pXlUiQfNcK8H5E2A+x*u$
102、rZnWkThPeMaJ7G4C1z-w&t!pYmVjRgOdL9I6E3B0y(v%s#oXlUiQfNbK8H5D2A+x*u$qZnWkShPeMaJ7F4C1z)w&t!pYmUjRgOcL9I6E3B+y(v%r#oXlTiQeNbK8G5D2A-x*t$qZnVkShPdMaJ7F4C0z)w&s!pYmUjRfOcL9H6E3B+y(u%r#oWlTiQeNbJ8G5D1A-x*t$qYnVkSgPdMaI7F3C0z)v&s!pXmUiRfOcK9H6E2B+y(u%rZoWlThQeNbJ8G4D1A-w*t$qYnVjSgPdLaI7F3Cu%r#oWlTiQeNbJ8G
103、5D1A-x*t$qYnVkSgPdMaI7F3C0z)v&s!pXmUjRfOcK9H6E2B+y(u%rZoWlThQeNbJ8G4D1A-w*t$qYnVjSgPdLaI7F3C0y)v&s#pXmUiRfNcK9H5E2B+x(u$rZoWkThQeMbJ8G4D1z-w*t!qYnVjSgOdLaI6F3C0y)v%s#pXlUiRfNcK8H5E2A+x(u$rZnWkThPeMbJ7G4C1z-w&t!qYmVjRgOdL9I6F3B0y(v%s#oXlUiQfNcK8H5D2A+x*u$rZnWkShPeMaJ7G4C1z)w&t!pYmVjRgOcL9I6E3B0y(v%r#
104、oXlTiMbJ7G4C1z-w&t!qYmVjSgOdL9I6F3B0y)v%s#oXlUiQfNcK8H5D2A+x*u$rZnWkShPeMaJ7G4C1z)w&t!pYmVjRgOcL9I6E3B0y(v%r#oXlTiQfNbK8H5D2A-x*u$qZnWkShPdMaJ7F4C1z)w&s!pYmUjRgOcL9H6E3B+y(v%r#oWlTiQeNbK8G5D1A-x*t$qZnVkSgPdMaI7F4C0z)v&s!pXmUjRfOcL9H6E2B+y(u%r#oWlThQeNbJ8G5D1A-w*t$qYnVkSgPdLaI7F3C0z)v&s#pXmUiRfOcK9H5
105、E2B+x(u%rZoWkThQeMbJ8G4D1A-w*t!qYnVjSgPdLaI6F3C0y)v&s#pXlUiRfNcK9H5E2A+x(u$rZoWkThPeMbJ7G4D1z-w&t!qYmVjSgOdL9I6F3B0y)v%s#oXQeMbJ8G4D1A-w*t!qYnVjSgPdLaI6F3C0y)v&s#pXlUiRfNcK9H5E2A+x(u$rZoWkThPeMbJ7G4D1z-w&t!qYmVjSgOdLaI6F3B0y)v%s#pXlUiQfNcK8H5E2A+x*u$rZnWkThPeMaJ7G4C1z-w&t!pYmVjRgOdL9I6E3B0y(v%s#oXlTiQfNbK8H5D2A-x*u$qZnWkShPeMaJ7F4C1z)w&t!pYmUjRgOcL9I6E3B+y(v%r#oXlTiQeNbK8G5D2A-x*t$qZnVkShPdMaI7F4C0z)w&s!pXmUjRfOcL9H6E3B*u$qZnWkShPeMaJ7F4C1z)w&t!pYmUjRgOcL9I6E3B+y(v%r#oXlTiQeNbK8G5D2A-x*t$qZnVkShPdMaJ7F4C0z)w&s!pYmUjRfOcL9H6E3B+y(u%r#oWlTiQeNbJ8G5D1A-x*t$qYnVkSg
