图的基本概念和基本操作.ppt

《图的基本概念和基本操作.ppt》由会员分享，可在线阅读，更多相关《图的基本概念和基本操作.ppt（189页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第8章 图第第8章章图图8.1图的基本概念和基本操作图的基本概念和基本操作8.2图的邻接矩阵存储结构图的邻接矩阵存储结构8.3图的邻接表存储结构图的邻接表存储结构8.4图的其他存储结构图的其他存储结构8.5最小生成树最小生成树8.6最短路径最短路径第8章 图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）第8章 图图81带自身环的图和多重图（a）带自身环的图；（b）多重图第8章 图这

2、样，在图G中，V是顶点的有穷非空集合，E是顶点之间关系的有穷集合，E也叫做边的集合。图有许多复杂结构，本教材只讨论最基本的图，因此，本书讨论的图中不包括图81所示两种形式的图。图81（a）中有从顶点A到自身的边存在，称为带自身环的图;图81（b）中从顶点B到顶点D有两条无向边，称为多重图。第8章 图下面我们给出图的基本概念：（1）有向图和无向图：在有向图中，顶点对x,y是有序的，顶点对x,y称为从顶点x到顶点y的一条有向边，因此，x,y与y,x是两条不同的边。有向图中的顶点对x,y用一对尖括号括起来，x是有向边的始点，y是有向边的终点，有向图中的边也称作弧。在无向图中，顶点对（x,y）是无序的

3、，顶点对（x,y）称为与顶点x和顶点y相关联的一条边，这条边没有特定的方向，（x,y）与（y,x）是同一条边。第8章 图图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章 图图8四个图例（a）G1；（b）G2；（c）G3；（d）G4第8章 图(2)完全图：在有n个结点的无向图中，若有n

4、(n-1)/2条边，则称此图为无向完全图。图8的G1就是无向完全图。在有n个结点的有向图中，若有n(n-1)条边，则称此图为有向完全图。图8的G4就是有向完全图。完全图中的顶点个数和边的个数都达到最大值。第8章 图(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。第8章 图(4)

5、顶点的度：顶点v的度是与它相关联的边的条数，记作TD(v)。在有向图中，顶点的度等于该顶点的入度和出度之和，即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条有向边（或无向边）的图中，恒有下列关系式：第8章 图(5)路径：在图G=(V,E)中，若从顶点vi出发有一组边使可到达顶点vj，则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点v

6、j的路径。在图8的图G2中，从顶点0到顶点3的路径为0,1,3。(6)权：有些图的边附带有数据信息，这些附带的数据信息称为权。权可以表示实际问题中从一个顶点到另一个顶点的距离、花费的代价、所需的时间，等等。带权的图称作网络。图83就是带权图。其中，图83（a）是一个工程的施工进度图，图8-3（b）是一个交通网络图。第8章 图图83带权图（a）施工进度图；（b）交通网络图第8章 图（7）路径长度：对于不带权的图，一条路径的路径长度是指该路径上的边的条数；对于带权的图，一条路径的路径长度是指该路径上各个边权值的总和。在图8的无向图G2中，路径0,1,3的路径长度为2；在图83（a）的有向图中，路径

7、1,3,6,7的路径长度为16，路径1,4,7的路径长度为31。(8)子图：设有图G1=V1,E1和图G2=V2,E2，若V2V1且E2E1，则称图G2是图G1的子图。第8章 图(9)连通图和连通分量：在无向图中，若从顶点vi到顶点vj有路径，则称顶点vi和顶点vj是连通的。如果图中任意一对顶点都是连通的，则称该图是连通图。非连通图的极大连通子图称作连通分量。图82的无向图G1和G2都是连通图。(10)强连通图和强连通分量：在有向图中，若对于每一对顶点vi和vj都存在一条从vi到vj和从vj到vi的路径，则称该图是强连通图。非强连通图的极大强连通子图称作强连通分量。图82的有向图G4是强连通图

8、。图82的有向图G3不是强连通图，但G3有一个强连通分量包括顶点0和顶点1，边0,1和边1,0。第8章 图(11)生成树：一个连通图的极小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边。(12)简单路径和回路：若路径上各顶点v1,v2,vm,均互不重复，则称这样的路径为简单路径；若路径上第一个顶点v1与最后一个顶点vm重合，则称这样的路径为回路或环。第8章 图8.1.2图的基本操作讨论各种类型的图都要用到的图的基本操作。(1)在图中增加一个顶点；（2）如果顶点v1和v2是图中的两个顶点，则在图中插入边(v1,v2)；（3）如果顶点v是图中的顶点，则删除图中顶点v和与

9、顶点v相关联的所有边；（4）如果边(v1,v2)是图中的一条边，则删除边(v1,v2)；（5）如果顶点v是图中的顶点，则取顶点v的第一个邻接顶点；第8章 图（6）如顶点v和顶点w是图中的两个顶点且它们互为邻接顶点，则取得顶点v的w邻接顶点的下一个邻接顶点。（7）按某种规则遍历图。和树的遍历类同，图的遍历也是访问图中的每一个顶点且每个顶点只被访问一次。第8章 图8.2图的邻接矩阵存储结构图的邻接矩阵存储结构8.2.1邻接矩阵我们首先定义邻接矩阵。假设图G=(V,E)有n个顶点，即V=v0,v1,vn-1，E可用如下形式的矩阵A描述，对于A中的每一个元素aij，满足：若(i,j)E或i,jE否则第

10、8章 图由于矩阵A中的元素aij表示了顶点i和顶点j之间边的关系，或者说，A中的元素aij表示了顶点i和其他顶点j（0jn-1）的邻接关系，所以矩阵A称作邻接矩阵。在图的邻接矩阵存储结构中，顶点信息使用一维数组存储，边信息的邻接矩阵使用二维数组存储。图84（a）是一个无向图，图84（b）是对应的邻接矩阵存储结构。其中，V表示了图的顶点集合，A表示了图的邻接矩阵。无向图的邻接矩阵一定是对称矩阵。从无向图的定义和无向图的邻接矩阵定义可知，邻接矩阵中第i行（或第i列）中非零元素的个数等于第i个顶点的度数。又由于邻接矩阵中非零元的数值为1，所以有第8章 图图84无向图及其邻接矩阵（a）无向图；（b）邻

11、接矩阵第8章 图图85（a）是一个有向图，图85（b）是对应的邻接矩阵存储结构，其中，V表示图的顶点集合，A表示图的邻接矩阵。有向图的邻接矩阵一般是非对称矩阵。从有向图的定义和有向图的邻接矩阵定义可知，有向图的邻接矩阵中第i行中非零元素的个数等于第i个顶点的出度，有向图的邻接矩阵中第i列中非零元素的个数等于第i个顶点的入度，又由于邻接矩阵中非零元素的数值为1，所以有：第8章 图图85有向图及其邻接矩阵（a）有向图；（b）邻接矩阵第8章 图对于网（或称带权图），邻接矩阵A的定义为：ij且(i,j)E或i,jE否则但ij否则但i=j其中，wij0，wij是边(i,j)或弧，i,j的权值，权值wij

12、表示了从顶点i到顶点j的代价或称费用。当i=j时，邻接矩阵中的元素aij=0可理解为从一个顶点到自己顶点没有代价，这也完全和实际应用中的问题模型相符。有种特殊的网允许wij为负值，本书讨论的网不包括此种网。第8章 图图86（a）是一个带权图，图86（b）是对应的邻接矩阵存储结构。其中，V表示图的顶点集合，A表示图的邻接矩阵。对于带权图，邻接矩阵第i行中所有0aij的元素个数等于第i个顶点的出度，邻接矩阵第j列中所有0aij的元素个数等于第j个顶点的出度。第8章 图图86带权图及其邻接矩阵（a）带权图；（b）邻接矩阵第8章 图8.2.2邻接矩阵表示的图类对于上述的无向图、有向图和带权图三种类型的

13、图，其图类实现方法基本类同，如有向图中的弧a,b和弧b,a就等同于无向图中的边(a,b)，把不带权图中的边信息均定为1，不带权图就变成了带权图。因此，在上述三种类型的图中，带权图最有代表性。下面我们就以带权图为例讨论邻接矩阵表示的图类。第8章 图1.图类的定义在邻接矩阵表示的图中，顶点信息用一个一维数组表示，边（或称弧）信息用一个二维数组表示。在这里，顶点信息我们用第3章讨论的线性表表示，因此我们可以利用线性表实现的功能和提供的共有成员函数方便地完成顶点的插入、删除等操作。我们在第3章设计的线性表类是使用抽象数据类型Datatype来定义要操作的数据对象的，因此这里要在主函数使用图类之前定义抽

14、象数据类型Datatype为图的顶点信息数据类型，我们的测试例子中定义图的顶点信息数据类型(Vert)为char类型。第8章 图大多数情况下带权图的边信息只包含边的权值，作为教科书，我们主要注重基本原理和方法的讨论，因此我们这里设计的图类的边信息只包含边的权。注意，由于我们利用线性表来保存顶点信息，所以关于顶点信息的当前个数、是否表已满无法再继续插入等均由线性表来维护，这里无需再考虑，这也正是面向对象程序设计最主要的优点之一。第8章 图includeSeqList.hincludeSeqQueue.hconstintMaxVertices=10;constintMaxWeight=10000;

15、classAdjMWGraphprivate:SeqListVertices;/顶点信息的线性表第8章 图intEdgeMaxVerticesMaxVertices;/边的权信息的矩阵intnumOfEdges;/当前的边数public:AdjMWGraph(constintsz=MaxVertices);/构造函数intGraphEmpty()const/图空否returnVertices.ListEmpty();intNumOfVertices(void)/取当前顶点个数returnVertices.ListSize();第8章 图intNumOfEdges(void)/取当前边个数ret

16、urnnumOfEdges;VerTGetValue(constinti);/取顶点i的值intGetWeight(constintv1,constintv2);/取弧v1,v2的权/插入顶点vertexvoidInsertVertex(constVerT&vertex);/插入弧v1,v2，权为weightvoidInsertEdge(constintv1,constintv2,intweight);/删除顶点i和与顶点i相关的所有边voidDeleteVertex(constinti);第8章 图/删除弧v1,v2voidDeleteEdge(constintv1,constintv2);

17、/取顶点v的第一条邻接边，取到返回该邻接边的邻接顶点下标；否则返回-1intGetFirstNeighbor(constintv);/取顶点v1的邻接边的下一条邻接边，/若下一条邻接边存在，则返回该邻接边的邻接顶点下标；否则返回-1intGetNextNeighbor(constintv1,constintv2);/对连通图从顶点v开始用visit()深度优先搜索访问，visited为访问标记voidDepthFirstSearch(constintv,intvisited,第8章 图voidvisit(VerTitem);/对连通图从顶点v开始用visit()广度优先搜索访问，visited

18、为访问标记voidBroadFirstSearch(constintv,intvisited,voidvisit(VerTitem);/对非连通图用visit()进行深度优先搜索访问voidDepthFirstSearch(voidvisit(VerTitem);/对非连通图用visit()进行广度优先搜索访问voidBroadFirstSearch(voidvisit(VerTitem);第8章 图2.成员函数的实现AdjMWGraph:AdjMWGraph(constintsz)/构造函数for(inti=0;isz;i+)for(intj=0;jsz;j+)if(i=j)Edgeij=0

19、;elseEdgeij=MaxWeight;/MaxWeight表示无穷大numOfEdges=0;/当前边个数初始为0第8章 图VerTAdjMWGraph:GetValue(constinti)/取顶点i的值if(iVertices.ListSize()cerr参数i越界出错!endl;exit(1);/使用线性表的GetData(i)成员函数返回顶点i的值returnVertices.GetData(i);第8章 图intAdjMWGraph:GetWeight(constintv1,constintv2)/取弧v1,v2的权if(v1 Vertices.ListSize()|v2 Ve

20、rtices.ListSize()cerr参数v1或v2越界出错!endl;exit(1);第8章 图returnEdgev1v2;/返回弧v1,v2的权voidAdjMWGraph:InsertVertex(constVerT&vertex)/插入顶点vertex/在顶点线性表Vertices的当前表尾ListSize()插入顶点vertexVertices.Insert(vertex,Vertices.ListSize();第8章 图void AdjMWGraph:InsertEdge(const int v1,const int v2,intweight)/插入弧v1,v2，权为weig

21、htif(v1 Vertices.ListSize()|v2 Vertices.ListSize()cerr参数v1或v2越界出错!endl;exit(1);Edgev1v2=weight;/插入权为weight的边第8章 图numOfEdges+;/边个数加1voidAdjMWGraph:DeleteVertex(constintv)/删除顶点v和与顶点v相关的所有边/删除与顶点v相关的所有边for(inti=0;iVertices.ListSize();i+)for(intj=0;j0&EdgeijMaxWeight)Edgeij=MaxWeight;numOfEdges-;Vertice

22、s.Delete(v);/删除顶点v第8章 图voidAdjMWGraph:DeleteEdge(constintv1,constintv2)/删除弧，v1,v2if(v1Vertices.ListSize()|v2Vertices.ListSize()|v1=v2)cerr参数v1或v2出错!endl;exit(1);第8章 图Edgev1v2=MaxWeight;/把该边的权值置为无穷NumOfEdges-;/边个数减1第8章 图8.2.3邻接矩阵图类的深度优先搜索遍历和树的遍历操作类同，图的遍历操作也是图问题中最基本和最重要的操作。图的遍历操作的定义是访问图中的每一个顶点且每个顶点只被访

23、问一次。图的遍历操作方法有两种：一种是深度优先搜索遍历，另一种是广度优先搜索遍历。图的深度优先搜索遍历类同于树的先根遍历，图的广度优先搜索遍历类同于树的层序遍历。第8章 图图的遍历算法设计需要考虑三个问题：（1）图的特点是没有首尾之分，所以算法的参数要指定访问的第一个顶点；（2）对图的遍历路径有可能构成一个回路，从而造成死循环，所以算法设计要考虑遍历路径可能的回路问题；（3）一个顶点可能和若干个顶点都是相邻顶点，要使一个顶点的所有相邻顶点按照某种次序被访问。第8章 图我们首先考虑第（3）个问题的解决方法。为解决图的遍历操作的这个问题，我们在图的成员函数中设计了GetFirstNeighbor(

24、v)成员函数和GetNextNeighbor(v1,v2)成员函数。GetFirstNeighbor(v)找顶点v的第一条邻接边，若存在，则返回该邻接边的邻接顶点下标；否则返回-1。GetNextNeighbor(v1,v2)找顶点v1的v1,v2邻接边的下一条邻接边，若下一条邻接边存在，则返回该邻接边的邻接顶点下标；否则返回-1。第8章 图有了这两个成员函数，我们就可以从顶点v1首先找到第一条邻接边v1,v2，再从顶点v1的v1,v2邻接边找顶点v1的v1,v2邻接边后的下一条邻接边，从而可以找到顶点v1的所有邻接边。这两个成员函数的算法设计如下：intAdjMWGraph:GetFirst

25、Neighbor(constintv)/找顶点v的第一条邻接边，若存在则返回该邻接边的邻接顶点下标；否则返回-1if(vVertices.ListSize()第8章 图cerr参数v1越界出错!endl;exit(1);for(intcol=0;col 0&Edge v col MaxWeight)returncol;return-1;/不存在，则返回-1intAdjMWGraph:GetNextNeighbor(constintv1,constintv2)/找顶点v1的v1,v2邻接边的下一条邻接边，第8章 图/若下一条邻接边存在,则返回该邻接边的邻接顶点下标；否则返回-1if(v1 Ver

26、tices.ListSize()|v2 Vertices.ListSize()cerr参数v1或v2越界出错!endl;exit(1);第8章 图/使col=v2+1，因此寻找的是顶点v1的v1,v2邻接边的下一条邻接边for(intcol=v2+1;col 0&Edgev1col MaxWeight)returncol;return-1;/不存在，则返回-1第8章 图对于连通图，从初始顶点出发一定存在路径和图中的所有其他顶点相连，所以对于连通图从初始顶点出发一定可以遍历该图。图的深度优先遍历算法是遍历时深度优先的算法，即在图的所有邻接顶点中每次都在访问完当前顶点后首先访问当前顶点的第一个邻接

27、顶点，这样的算法是一个递归算法。连通图的深度优先搜索遍历算法思想是：（1）访问初始顶点v并标记顶点v为已访问；（2）查找顶点v的第一个邻接顶点w；第8章 图（3）若顶点v的邻接顶点w存在，则继续执行，否则算法结束；（4）若顶点w尚未被访问,则访问顶点w并标记顶点w为已访问；（5）查找顶点v的w邻接顶点后的下一个邻接顶点w，转到步骤（3）。第8章 图voidAdjMWGraph:DepthFirstSearch(constintv,intvisited,voidvisit(VerTitem)visit(GetValue(v);/访问顶点vvisitedv=1;/标记顶点v已访问intw=GetF

28、irstNeighbor(v);/顶点w为顶点v的第一个邻接顶点第8章 图while(w!=-1)/当邻接顶点存在时循环if(!visitedw)DepthFirstSearch(w,visited,visit);/对顶点w递归/顶点w为顶点v的w邻接顶点的下一个邻接顶点w=GetNextNeighbor(v,w);第8章 图上述递归算法属于第6章讨论过的回溯算法，当寻找顶点v的邻接顶点成功时继续进行，当寻找顶点v的邻接顶点失败时回溯到上一次递归调用的地方继续进行。对于图87所示的无向连通图，若顶点A为访问的首顶点，则深度优先搜索遍历的顶点访问顺序是：ABDECFG。第8章 图图87无向连通图

29、及其邻接矩阵（a）无向连通图；（b）邻接矩阵第8章 图8.2.4邻接矩阵图类的广度优先搜索遍历图的广度优先遍历算法是遍历时广度优先的算法。它是一个分层搜索的过程，和树的层序遍历算法类同，它也需要一个队列以保持访问过的顶点的顺序，以便按顺序访问这些顶点的邻接顶点。连通图的广度优先搜索遍历算法思想是：（1）访问初始顶点v并标记顶点v为已访问；（2）顶点v入队列；（3）当队列非空时则继续执行，否则算法结束；（4）出队列取得队头顶点u；第8章 图（5）查找顶点u的第一个邻接顶点w；（6）若顶点u的邻接顶点w存在，则继续执行，否则转到步骤（3）；（7）若顶点w尚未被访问则访问顶点w并标记顶点w为已访问；

30、(8)顶点w入队列；（9）查找顶点u的w邻接顶点后的下一个邻接顶点w，转到步骤（6）。第8章 图voidAdjMWGraph:BroadFirstSearch(constintv,intvisited,voidvisit(VerTitem)VerTu,w;SeqQueuequeue;/定义队列queuevisit(GetValue(v);visitedv=1;queue.QInsert(v);/顶点v入队列第8章 图while(!queue.QueueEmpty()/当队列非空时循环u=queue.QDelete();/出队列得到队头顶点uw=GetFirstNeighbor(u);while

31、(w!=-1)/若顶点u的邻接顶点w存在时循环if(!visitedw)第8章 图visit(GetValue(w);visitedw=1;queue.QInsert(w);/顶点w入队列w=GetNextNeighbor(u,w);/顶点u的w邻接顶点的下一个邻接顶点第8章 图8.2.5非连通图和连通分量对于连通图，从图的任意一个顶点开始深度或广度优先遍历一定可以访问图中的所有顶点；但对于非连通图，从图的任意一个顶点开始深度或广度优先遍历并不能访问图中的所有顶点。对于非连通图，从图的任意一个顶点开始深度或广度优先遍历只能访问包括该首顶点的连通分量中的所有顶点。第8章 图但当我们把每一个顶点都

32、作为一次首顶点深度或广度优先遍历非连通图，并根据顶点的访问标记来判断是否需要访问该顶点时，就一定可以访问该非连通图中的所有顶点。非连通图的深度优先搜索遍历算法如下：void AdjMWGraph:DepthFirstSearch(void visit(VerTitem)=/定义顶点访问标记数组int*visited=newintNumOfVertices();/顶点访问标记数组初始化第8章 图for(inti=0;iNumOfVertices();i+)visitedi=0;for(i=0;iNumOfVertices();i+)/对所有顶点循环/如该顶点尚未被访问则以该顶点为首顶点深度优先遍

33、历访问if(!visitedi)DepthFirstSearch(i,visited,visit);deletevisited;/删除顶点访问标记数组第8章 图非连通图的广度优先搜索遍历算法如下：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);

34、deletevisited;第8章 图非连通图的广度优先搜索遍历算法和非连通图的深度优先搜索遍历算法类同，故不再作注释。对于图87所示的无向连通图，若删除弧0,2和2,0，则该图变为图8-8所示的非连通图。图88非连通图的深度优先搜索遍历顶点序列为：ABDECFG。图88非连通图的广度优先搜索遍历顶点序列为：ABDECFG。第8章 图图88非连通图第8章 图8.2.6邻接矩阵图类的测试我们以图87所示的无向连通图为例测试邻接矩阵图类。我们首先给出建立邻接矩阵图类对象的外部函数。为后面使用方便，我们把下面的结构体定义和外部函数放在文件GraphLib.h中。structRowColWeight/

35、定义结构体类型RowColWeightintrow;/行下标第8章 图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-1第8章 图for(intk=0;ke;k+)G.InsertEdge(Ek.row,Ek.col,Ek.weight);voidPrint

36、char(charitem)/访问顶点的函数coutitem;第8章 图使用图87所示的无向连通图的测试程序如下：typedefcharVerT;/顶点类型定义typedefcharDatatype;/邻接矩阵图类中所使用线性表类型定义includeAdjMWGraph.hincludeGraphLib.hvoidmain(void)AdjMWGraphg;第8章 图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,

37、e=12;CreatGraph(g,a,n,rcw,e);cout当前的顶点个数为：g.NumOfVertices()endl;cout当前的边的条数为：g.NumOfEdges()endl;第8章 图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.Br

38、oadFirstSearch(0,visited,Printchar);deletevisited;第8章 图g.DeleteEdge(0,2);g.DeleteEdge(2,0);coutendl当前的顶点个数为：g.NumOfVertices();coutendl当前的边的条数为：g.NumOfEdges()endl;cout深度优先搜索序列为：;g.DepthFirstSearch(Printchar);coutendl广度优先搜索序列为：;g.BroadFirstSearch(Printchar);第8章 图程序的运行结果为：当前的顶点个数为：7；当前的边的条数为：12；连通图的深度优

39、先搜索序列为：ABDECFG；连通图的广度优先搜索序列为：ABCDEFG。删除边0,2和2,0后非连通图有当前的顶点个数为：7；当前的边的条数为：10；非连通图的深度优先搜索序列为：ABDECFG；非连通图的广度优先搜索序列为：ABDECFG。第8章 图8.3图的邻接表存储结构图的邻接表存储结构8.3.1图的邻接表存储结构图的邻接矩阵存储结构的主要特点是把图的边信息存储在一个nn矩阵中。其中，n为图中的顶点个数。当这个nn阶矩阵是稠密矩阵时，图的邻接矩阵存储结构是最常用也是最高效的存储结构。第8章 图图89是图85（a）所示有向图的邻接表存储结构。严格地说，该图的边信息存储矩阵不是一个稀疏矩阵

40、，因顶点个数太少，但为使我们讨论问题和表示问题不致过于麻烦，所以我们假设该图的边信息存储矩阵是一个稀疏矩阵。第8章 图图89有向图的邻接表存储结构第8章 图图89中行数组的data域存储图的顶点信息，adj域为该顶点的邻接顶点单链表的头指针。第i行单链表中的dest域存储边i,j的邻接顶点j，对于任意一条边i,j，因i值和存储该顶点的下标值一致，所以不需要再另外存储。如果是带权图再增加cost域，第i行单链表中的dest域值为j的cost域中存储了边i,j的权值wij。对比图89和第5章图54的行指针数组结构的三元组链表，可以发现，两者讲述的是同一种存储结构。第8章 图8.3.2邻接表存储结构

41、的图类includeSeqQueue.hconstintMaxVertices=100;structEdge/边结构体定义intdest;/邻接顶点下标DistTweight;/权Edge*next;/指针第8章 图Edge()/构造函数Edge(intd,DistTw):dest(d),weight(w),next(NULL)/构造函数;structitem/顶点数组的元素类型定义VerTdata;/顶点数据第8章 图Edge*adj;/邻接表指针;classAdjTWGraph/邻接表图类定义private:itemVerticesMaxVertices;/顶点数组intnumVertic

42、es;/顶点数组的当前元素个数第8章 图intnumOfEdges;/当前边的条数public:AdjTWGraph(void);AdjTWGraph(void);intGraphEmpty()constreturnnumVertices=0;intNumOfVertices(void)returnnumVertices;intNumOfEdges(void)第8章 图returnnumOfEdges;VerTGetValue(constinti);intGetWeight(constintv1,constintv2);voidInsertVertex(constVerT&vertex);vo

43、idInsertEdge(constintv1,constintv2,intweight);voidDeleteVertex(constintv);voidDeleteEdge(constintv1,constintv2);intGetFirstNeighbor(constintv);intGetNextNeighbor(constintv1,constintv2);第8章 图voidDepthFirstSearch(constintv,intvisited,voidvisit(VerTitem);voidBroadFirstSearch(constintv,intvisited,voidvi

44、sit(VerTitem);voidDepthFirstSearch(voidvisit(VerTitem);voidBroadFirstSearch(voidvisit(VerTitem);第8章 图1.构造函数和析构函数AdjTWGraph:AdjTWGraph(void)for(int i=0;i MaxVertices;i+)Verticesi.adj=NULL;numVertices=0;numOfEdges=0;AdjTWGraph:AdjTWGraph(void)/释放为存储边信息所动态建立的邻接链表的空间第8章 图for(inti=0;inext;deletep;p=q;第8章

45、 图2.简单成员函数的实现VerTAdjTWGraph:GetValue(constinti)if(inumVertices)cerr参数i越界出错!endl;exit(1);returnVerticesi.data;intAdjTWGraph:GetWeight(constintv1,constintv2)第8章 图if(v1numVertices|v2numVertices)cerr参数v1或v2越界出错!destnext;if(v2!=p-dest)第8章 图cerr边不存在!weight;第8章 图3.插入顶点和边以及删除顶点和边成员函数的实现插入顶点成员函数很简单，只需在存放顶点信息

46、的数组中插入一个顶点信息。voidAdjTWGraph:InsertVertex(constVerT&vertex)VerticesnumVertices.data=vertex;numVertices+;第8章 图插入边v1,v2的操作是要在数组下标的v1行中的邻接链表中插入一个包含dest,weight和next域的结点。其中，dest域的值为v2，邻接链表按dest域的值递增有序。这是一个建立单链表的过程，由于所建立的单链表无头指针，所以算法中要分别考虑是否是单链表的第一次插入；在不是单链表的第一次插入时,还要考虑在单链表的第一个结点前插入和在单链表的其他位置插入的情况。第8章 图voi

47、dAdjTWGraph:InsertEdge(constintv1,constintv2,intweight)if(v1numVertices|v2numVertices)cerr参数v1或v2越界出错!destnext;if(pre=NULL)/在第一个结点前插入第8章 图q-next=Verticesv1.adj;Verticesv1.adj=q;else/在其他位置插入q-next=pre-next;pre-next=q;numOfEdges+;第8章 图插入边成员函数算法使用的是10.2.2节将要讨论的链表插入排序算法，因此邻接表中的结点按边的弧尾顶点的大小有序排列。插入排序算法的思想

48、是：空链表时，直接生成第一条边的弧尾顶点的dest域结点插入；第二条边的弧尾顶点结点插入到链表中的位置由v2和第一条边结点的dest域比较确定(若v2小于第一条边结点的dest,则把v2生成的结点插在第一条边的结点前；否则，把v2生成的结点插在第一条边的结点后)。关于链表插入排序算法的更详细说明可参看10.2.2节。第8章 图插入边成员函数算法最坏情况下的时间复杂度为O(e)，其中e为边的条数。删除顶点v时要删除和顶点v关联的所有边，这包括要删除顶点v的所有出边v,j和所有入边i,v。在邻接表存储的图中删除顶点v的所有入边i,v的算法比较麻烦，需要在所有顶点为i的单链表中寻找dest域为v的结

49、点并删除。由于所建立的单链没有头结点，所以删除时还要分别考虑要删除结点是单链表的第一个结点和不是单链表的第一个结点的情况。在邻接表存储的图中删除顶点v的所有出边v,j的算法是逐个删除顶点数组第v行单链表的所有结点，并删除该顶点元素。第8章 图voidAdjTWGraph:DeleteVertex(constintv)Edge*pre,*curr;for(inti=0;idestnext;if(pre=NULL&curr-dest=v)/该出边结点是单链表的第一个结点时Verticesi.adj=curr-next;deletecurr;numOfEdges-;elseif(curr!=NULL

50、&curr-dest=v)/该出边结点是单链表的其他结点时第8章 图pre-next=curr-next;deletecurr;numOfEdges-;Edge*p=Verticesv.adj,*q;for(i=v;inext;deletep;/释放空间p=q;numOfEdges-;第8章 图从上述算法中可以看出，在邻接表中，为寻找邻接到顶点v的邻接顶点，即寻找边i,v的顶点i，必须遍历整个邻接表，在每一个按弧尾顶点序号有序的单链表中寻找结点的dest域值等于v的结点。因此其时间复杂度为O(ne)。其中，n为顶点个数，e为边的条数。删除边v1,v2的算法是在顶点数组的第v1行中删除结点的de