第08章 图精选文档.ppt

《第08章 图精选文档.ppt》由会员分享，可在线阅读，更多相关《第08章 图精选文档.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第08章 图本讲稿第一页，共五十五页 图论图论歌尼斯堡七桥问题：在图中找一条经过每边一次且仅一次的路欧拉回路。货郎担问题：在图中找一条经过每个点一次且仅一次的最短路。描述问题的重要工具描述问题的重要工具状态图关键路径问题：整个工程完成的时间为：从有向图的源点到汇点的最长路径。引ABCDADBCabcdefghk64521187244源点源点6174汇点汇点本讲稿第二页，共五十五页地理信息领域的应用地理信息领域的应用四色问题：任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。最短路径问题：vi到vj使总费用最小的旅行路线。数字地面模型构网课外书目：课外书目：离散数学基础离散数学基础

2、 耿素云耿素云 清华大学出版社清华大学出版社 （图论基础）（图论基础）算法设计与分析算法设计与分析 吕国英吕国英 清华大学出版社清华大学出版社 （算法策略的基本思想）（算法策略的基本思想）计算几何计算几何 周培德周培德 清华大学出版社清华大学出版社 （图论问题的解法）（图论问题的解法）数据结构数据结构 Pascal&C+Pascal&C+薛超英薛超英 华中理工大学出版社华中理工大学出版社 （算法实现）（算法实现）本讲稿第三页，共五十五页图的基本概念和抽象数据类型图的基本概念和抽象数据类型图的存储结构图的存储结构邻接矩阵图的实现邻接矩阵图的实现图的遍历图的遍历最小生成树最小生成树最短路径最短路径

3、主主要要知知识识点点本讲稿第四页，共五十五页8.1 8.1 图的基本概念和抽象数据类型图的基本概念和抽象数据类型1.1.图的基本概念图的基本概念 图图是是由由顶顶点点集集合合及及顶顶点点间间的的关关系系集集合合组组成成的的一一种种数数据据结结构构。图图G的定义是：的定义是：G=（V，E）其中，其中，V=x|x某个数据元素集合某个数据元素集合E=(x，y)|x，yV或或E=x，y|x，yV并且并且Path(x，y)其其中中，（x，y）表表示示从从x到到y的的一一条条双双向向通通路路，即即（x，y）是是无无方方向向的的；Path（x，y）表表示示从从x到到y的的一一条条单单向向通通路路，即即Pat

4、h（x，y）是是有有方向的。方向的。本讲稿第五页，共五十五页基本术语：基本术语：（1）顶顶点点和和边边（Vertex，Edge）：图图中中的的结结点点称称作作顶顶点点，图图中中的的第第i个个顶顶点点记记做做vi。两两个个顶顶点点vi和和vj相相关关联联称称作作顶顶点点vi和和vj之之间间有有一一条条边边，图图中中的的第第k条条边边记记做做ek，ek=（vi,vj）或）或vi,vj。（2）有有向向图图和和无无向向图图：在在有有向向图图中中，顶顶点点对对x,y是是有有序序的的，顶顶点点对对x,y称称为为从从顶顶点点x到到顶顶点点y的的一一条条有有向向边边，有有向向图图中中的的边边也也称称作作弧弧（

5、Arc）；在在无无向向图图中中，顶点对（顶点对（x,y）是无序的，顶点对（）是无序的，顶点对（x,y）称为与顶点）称为与顶点x和顶点和顶点y相关联的一条边。相关联的一条边。（3）完完全全图图：在在有有n个个顶顶点点的的无无向向图图中中，若若有有n(n-1)/2条条边边，即即任任意意两两个个顶顶点点之之间间有有且且只只有有一一条条边边，则则称称此此图图为为无无向向完完全全图图；在在有有n个个顶顶点点的的有有向向图图中中，若若有有n(n-1)条条边，即任意两个顶点之间有且只有方向相反的两条边，则称此图为边，即任意两个顶点之间有且只有方向相反的两条边，则称此图为有向完全图有向完全图。0 01 13

6、32 20 01 12 23 34 45 56 60 01 12 20 01 12 23 3(a)a)无向完全图无向完全图(b)b)无向图无向图(c)c)有向图有向图(d)d)有向完全图有向完全图本讲稿第六页，共五十五页（4）邻接顶点：）邻接顶点：在无向图在无向图G中，若（中，若（u,v）是）是E(G)中的一条边，则中的一条边，则称称u和和v互为邻接顶点，并称边（互为邻接顶点，并称边（u,v）依附于顶点）依附于顶点u和和v；在有向图；在有向图G中，若中，若u,v是是E(G)中的一条边，则称顶点中的一条边，则称顶点u邻接到顶点邻接到顶点v，顶点，顶点v邻邻接自顶点接自顶点u，并称边，并称边u,v

7、和顶点和顶点u和顶点和顶点v相相关联关联。（5）顶点的度（）顶点的度（Degree）：）：顶点顶点v的度是与它相关联的边的条数，记的度是与它相关联的边的条数，记作作TD(v)。（6）路径（）路径（Path/Route）：）：在图在图G=(V,E)中，若从顶点中，若从顶点vi出发有一出发有一组边使可到达顶点组边使可到达顶点vj，则称顶点，则称顶点vi到顶点到顶点vj的顶点序列为从顶点的顶点序列为从顶点vi到顶到顶点点vj的路径。的路径。0 01 13 32 20 01 12 23 34 45 56 60 01 12 20 01 12 23 3(a)a)无向完全图无向完全图(b)b)无向图无向图(

8、c)c)有向图有向图(d)d)有向完全图有向完全图本讲稿第七页，共五十五页（7）权（）权（Weight）：）：有些图的边附带有数据信息，这些附带的数据信有些图的边附带有数据信息，这些附带的数据信息称为权。带权的图也称作息称为权。带权的图也称作网络或网网络或网。2135467879610612715163BACDE60304575804035施工进度图施工进度图交通网络图交通网络图（8）路路径径长长度度：对对于于不不带带权权的的图图，一一条条路路径径的的路路径径长长度度是是指指该该路路径径上上的的边边的的条条数数；对对于于带带权权的的图图，一一条条路路径径的的路路径径长长度度是是指指该该路路径径

9、上上各各个个边边权权值值的总和。的总和。（9）子子图图：设设有有图图G1=V1,E1和和图图G2=V2,E2，若若V2 V1且且E2 E1，则称图，则称图G2是图是图G1的子图。的子图。本讲稿第八页，共五十五页（10）连通图和强连通图：）连通图和强连通图：在无向图中，若从顶点在无向图中，若从顶点vi到顶点到顶点vj有路径，有路径，则称顶点则称顶点vi和顶点和顶点vj是连通的。如果图中任意一对顶点都是连通的，是连通的。如果图中任意一对顶点都是连通的，则称该图是连通图。图中的无向图则称该图是连通图。图中的无向图a和和b都是连通图。都是连通图。在有向图中，若对于任意一对顶点在有向图中，若对于任意一对

10、顶点vi和顶点和顶点vj（vivj）都存在路径，）都存在路径，则称图则称图G是是强连通图强连通图。图。图8-2中的有向图中的有向图d是强连通图。是强连通图。（11）生成树：）生成树：一个连通图的最小连通子图称作该图的生成树。一个连通图的最小连通子图称作该图的生成树。有有n个顶点的连通图的生成树有个顶点的连通图的生成树有n个顶点和个顶点和n-1条边。条边。（12）简单路径和回路：）简单路径和回路：若路径上各顶点若路径上各顶点v1,v2,vm,互不重复，则称互不重复，则称这样的路径为简单路径；若路径上第一个顶点这样的路径为简单路径；若路径上第一个顶点v1与最后一个顶点与最后一个顶点vm重合，重合，

11、则称这样的路径为回路或环则称这样的路径为回路或环。BACDFEACDFEB本讲稿第九页，共五十五页数据集合：数据集合：由一组顶点集合由一组顶点集合vi和一组边集合和一组边集合ej组成。当为带权组成。当为带权图时每条边上权图时每条边上权wj构成权集合构成权集合wi。操作集合：操作集合：(1)初始化初始化Initiate(G,n)(2)插入顶点插入顶点InsertVertex(G,vertex)(3)插入边插入边InsertEdge(G,v1,v2,weight)(4)删除边删除边DeleteEdge（G,v1,v2)(5)删除顶点删除顶点DeleteVertex(G,vertex)(6)第一个邻

12、接结点第一个邻接结点GetFirstVex(G,v)(7)下一个邻接结点下一个邻接结点GetNextVex(G,intv1,v2)(8)遍历遍历DepthFirstSearch(G)2.2.图的抽象数据类型图的抽象数据类型 BACDE60304575804035本讲稿第十页，共五十五页假假设设图图G=(V,E)有有n个个顶顶点点，即即V=v0,v1,vn-1，E可可用用如如下下形形式式的矩阵的矩阵A描述，对于描述，对于A中的每一个元素中的每一个元素aij，满足：，满足：由于矩阵由于矩阵A中的元素中的元素aij表示了顶点表示了顶点vi和顶点和顶点vj之间边的关系，或者之间边的关系，或者说，说，A

13、中的元素中的元素aij表示了顶点表示了顶点vi和顶点和顶点vj（0jn-1）的邻接关系，）的邻接关系，所以矩阵所以矩阵A称作邻接矩阵。称作邻接矩阵。8.2 8.2 图的存储结构图的存储结构图的存储结构主要有图的存储结构主要有邻接矩阵和邻接表邻接矩阵和邻接表两种。两种。1.1.图的邻接矩阵存储结构图的邻接矩阵存储结构 本讲稿第十一页，共五十五页无向图的邻接矩阵一定是对称矩阵无向图的邻接矩阵一定是对称矩阵 有向图的邻接矩阵一般是非对称矩阵有向图的邻接矩阵一般是非对称矩阵 其中其中V表示了图的顶点集合，表示了图的顶点集合，A表示了图的邻接矩阵表示了图的邻接矩阵 本讲稿第十二页，共五十五页带权图及其邻

14、接矩阵带权图及其邻接矩阵 其其中中V表表示示了了图图的的顶顶点点集集合合，A表表示示了了图图的的邻邻接接矩矩阵阵。对对于于带带权权图图，邻邻接接矩矩阵阵第第i行行中中所所有有0aij的的元元素素个个数数等等于于第第i个个顶顶点点的的出出度度，邻接矩阵第邻接矩阵第j列中所有列中所有0aij的元素个数等于第的元素个数等于第j个顶点的入度。个顶点的入度。本讲稿第十三页，共五十五页2.2.图的邻接表存储结构图的邻接表存储结构 当当图图的的边边数数少少于于顶顶点点个个数数且且顶顶点点个个数数值值较较大大时时，图图的的邻邻接接nnnn矩矩阵阵的的存存储储问问题题就就变变成成了了稀稀疏疏矩矩阵阵的的存存储储

15、问问题题，此此时时，邻邻接接表表就就是是一一种种较邻接矩阵更为有效的存储结构。较邻接矩阵更为有效的存储结构。BADCE(a)01234ABCDE0datasorce1432adjdest next23411 (b)4 数数组组的的data域域存存储储图图的的顶顶点点信信息息，sorce域域存存储储该该顶顶点点在在数数组组中中的的下下标标序序号号，adj域域为为该该顶顶点点的的邻邻接接顶顶点点单单链链表表的的头头指指针针。第第i行行单单链链表表中中的的dest域域存存储储所所有有起起始始顶顶点点为为vi的的邻邻接接顶顶点点vj在在数数组组中中的的下下标标序序号号，next域域为为单单链链表表中中

16、下下一一个个邻邻接接顶顶点点的的指指针针域域。如如果果是是带带权权图图，单单链链表表中中需再增加需再增加cost域，用来存储边域，用来存储边的权值的权值wij。本讲稿第十四页，共五十五页8.3 8.3 邻接矩阵图类邻接矩阵图类 1.1.邻接矩阵图类的设计和实现邻接矩阵图类的设计和实现 邻接矩阵图类实现如下：邻接矩阵图类实现如下：#includeSeqList.h/包含动态数组结构的顺序表类包含动态数组结构的顺序表类classAdjMWGraphprivate:SeqListVertices;/顶点顺序表顶点顺序表intEdgeMaxVerticesMaxVertices;/边权值数组边权值数组

17、intnumOfEdges;/边的个数边的个数voidDepthFirstSearch(constintv,intvisited,voidVisit(VerTitem);voidBroadFirstSearch(constintv,intvisited,voidVisit(VerTitem);本讲稿第十五页，共五十五页public:AdjMWGraph(constintsz=MaxVertices);/构造函数构造函数AdjMWGraph(void);/析构函数析构函数intNumOfVertices(void)/取顶点个数取顶点个数returnVertices.Size();intNumOf

18、Edges(void)/取边的个数取边的个数returnnumOfEdges;VerTGetValue(constintv);/取顶点数值取顶点数值intGetWeight(constintv1,constintv2);/取边的权值取边的权值voidInsertVertex(constVerT&vertex);/插入顶点插入顶点voidInsertEdge(constintv1,constintv2,intweight);/插入边插入边voidDeleteVertex(constintv);/删除顶点删除顶点voidDeleteEdge(constintv1,constintv2);/删除边删

19、除边本讲稿第十六页，共五十五页intGetFirstNeighbor(constintv);/取第一个邻接顶点取第一个邻接顶点intGetNextNeighbor(constintv1,constintv2);/取下一个邻接顶点取下一个邻接顶点voidDepthFirstSearch(voidVisit(VerTitem);/深度优先遍历深度优先遍历voidBroadFirstSearch(voidVisit(VerTitem);/广度优先遍历广度优先遍历;本讲稿第十七页，共五十五页AdjMWGraph:AdjMWGraph(constintsz):Vertices(sz)/构造函数构造函数f

20、or(inti=0;isz;i+)for(intj=0;jsz;j+)if(i=j)Edgeij=0;elseEdgeij=MaxWeight;numOfEdges=0;VerTAdjMWGraph:GetValue(constintv)/取顶点取顶点v的数值的数值if(vVertices.Size()cout参数参数v越界出错越界出错!endl;exit(0);returnVertices.GetData(v);本讲稿第十八页，共五十五页intAdjMWGraph:GetWeight(constintv1,constintv2)/取起始顶点为取起始顶点为v1、终止顶点为、终止顶点为v2的边的

21、权值的边的权值if(v1Vertices.Size()|v2Vertices.Size()cout参数参数v1或或v2越界出错越界出错!endl;exit(0);returnEdgev1v2;voidAdjMWGraph:InsertVertex(constVerT&vertex)/插入顶点插入顶点vertex/把顶点把顶点vertex插入到顺序表的当前表尾位置插入到顺序表的当前表尾位置Vertices.Insert(vertex,Vertices.Size();本讲稿第十九页，共五十五页voidAdjMWGraph:InsertEdge(constintv1,constintv2,intwe

22、ight)/插入一条起始顶点为插入一条起始顶点为v1、终止顶点为、终止顶点为v2、权值为、权值为weight的边的边if(v1Vertices.Size()|v2Vertices.Size()cout参数参数v1或或v2越界出错越界出错!endl;exit(0);Edgev1v2=weight;/插入边插入边numOfEdges+;/边的个数加边的个数加1本讲稿第二十页，共五十五页voidAdjMWGraph:DeleteVertex(constintv)/删除顶点删除顶点v/删除所有包含顶点删除所有包含顶点v的边的边for(inti=0;iVertices.Size();i+)for(int

23、j=0;j0&EdgeijMaxWeight)Edgeij=MaxWeight;/把该边的权值置为无穷大把该边的权值置为无穷大numOfEdges-;/边的个数减边的个数减1Vertices.Delete(v);/删除顶点删除顶点v本讲稿第二十一页，共五十五页voidAdjMWGraph:DeleteEdge(constintv1,constintv2)/删除一条起始顶点为删除一条起始顶点为v1、终止顶点为、终止顶点为v2的边的边if(v1Vertices.Size()|v2Vertices.Size()|v1=v2)cout参数参数v1或或v2出错出错!endl;exit(0);if(Edg

24、ev1v2=MaxWeight|v1=v2)cout该边不存在该边不存在!endl;exit(0);Edgev1v2=MaxWeight;/把该边的权值置为无穷大把该边的权值置为无穷大numOfEdges-;/边的个数减边的个数减1本讲稿第二十二页，共五十五页intAdjMWGraph:GetFirstNeighbor(constintv)/取顶点取顶点v的第一个邻接顶点。若存在返回该顶点的下标序号，否则返回的第一个邻接顶点。若存在返回该顶点的下标序号，否则返回-1if(vVertices.Size()cout参数参数v1越界出错越界出错!endl;exit(0);for(intcol=0;c

25、ol0&EdgevcolMaxWeight)returncol;return-1;本讲稿第二十三页，共五十五页intAdjMWGraph:GetNextNeighbor(constintv1,constintv2)/取顶点取顶点v1的邻接顶点的邻接顶点v2后的邻接顶点后的邻接顶点/若存在返回该顶点的下标序号，否则返回若存在返回该顶点的下标序号，否则返回-1if(v1Vertices.Size()|v2Vertices.Size()cout参数参数v1或或v2越界出错越界出错!endl;exit(0);for(intcol=v2+1;col0&Edgev1colMaxWeight)returnc

26、ol;return-1;本讲稿第二十四页，共五十五页2.2.邻接矩阵图类的测试邻接矩阵图类的测试 例例8-1 8-1 以以下下图图所所示示的的带带权权有有向向图图为为例例编编写写测测试试邻邻接接矩矩阵阵图图类类的的程序。程序。A AB BC CD DE E10104040303050502020图的创建函数设计如下：图的创建函数设计如下：structRowColWeightintrow;/行下标行下标intcol;/列下标列下标intweight;/权值权值;图图8-8本讲稿第二十五页，共五十五页voidCreatGraph(AdjMWGraph&G,DataTypeV,intn,RowCol

27、WeightE,inte)/在图在图G中插入中插入n个顶点个顶点V和和e条边条边E/在图在图G中插入中插入n个顶点个顶点for(inti=0;in;i+)G.InsertVertex(Vi);/在图在图G中插入中插入e条边条边for(intk=0;ke;k+)G.InsertEdge(Ek.row,Ek.col,Ek.weight);本讲稿第二十六页，共五十五页测试程序设计如下：测试程序设计如下：#include#includetypedefcharVerT;/定义邻接矩阵图类中的定义邻接矩阵图类中的VerTtypedefcharDataType;/定义顺序表类中的定义顺序表类中的DataTy

28、peconstintMaxVertices=100;/定义最大顶点个数定义最大顶点个数constintMaxWeight=10000;/定义权值的无穷大定义权值的无穷大#includeAdjMWGraph.h/包含邻接矩阵的图类包含邻接矩阵的图类#includeCreatAdjMWGraph.h/包含邻接矩阵图的创建函数包含邻接矩阵图的创建函数voidmain(void)AdjMWGraphg;chara=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(g,a,n,rcw,e)

29、;/创建图创建图cout顶点个数为：顶点个数为：g.NumOfVertices()endl;cout边的条数为：边的条数为：g.NumOfEdges()endl;g.DeleteVertex(3);/删除顶点删除顶点3g.DeleteEdge(0,4);/删除边删除边coutendl顶点个数为：顶点个数为：g.NumOfVertices();coutendl边的条数为：边的条数为：g.NumOfEdges()endl;本讲稿第二十七页，共五十五页8.4 8.4 图的遍历图的遍历 1.1.图的深度和广度优先遍历算法图的深度和广度优先遍历算法 图图的的遍遍历历是是访访问问图图中中的的每每一一个个顶

30、顶点点且且每每个个顶顶点点只只被被访访问问一一次次。算法设计需要考虑三个问题：算法设计需要考虑三个问题：（1 1）算法的参数要指定访问的第一个顶点；）算法的参数要指定访问的第一个顶点；（2 2）要考虑遍历路径可能出现的死循环问题；）要考虑遍历路径可能出现的死循环问题；（3 3）要使一个顶点的所有邻接顶点按照某种次序被访问。）要使一个顶点的所有邻接顶点按照某种次序被访问。一、一、图的深度优先遍历算法图的深度优先遍历算法 。图图的的深深度度优优先先遍遍历历算算法法是是遍遍历历时时深深度度优优先先的的算算法法，是是一一个个递递归归算算法法。连通图连通图的深度优先遍历递归算法为：的深度优先遍历递归算法

31、为：（1 1）访问顶点）访问顶点v v并标记顶点并标记顶点v v为已访问；为已访问；（2 2）查找顶点）查找顶点v v的第一个邻接顶点的第一个邻接顶点w w；（3 3）若顶点）若顶点v v的邻接顶点的邻接顶点w w存在，则继续执行，否则算法结束；存在，则继续执行，否则算法结束；（4 4）若顶点）若顶点w w尚未被访问则深度优先搜索递归访问顶点尚未被访问则深度优先搜索递归访问顶点w w；（5 5）查找顶点）查找顶点v v的的w w邻接顶点的下一个邻接顶点邻接顶点的下一个邻接顶点w w，转到步骤（，转到步骤（3 3）。）。上述上述递归算法属于回溯算法递归算法属于回溯算法本讲稿第二十八页，共五十五页

32、二、二、图的广度优先遍历算法图的广度优先遍历算法 图图的的广广度度优优先先遍遍历历算算法法是是一一个个分分层层搜搜索索的的过过程程，需需要要一一个个队队列列以以保保持持访访问问过过的的顶顶点点的的顺顺序序，以以便便按按访访问问过过的的顶顶点点的的顺顺序序来来访访问问这这些些顶顶点点的的邻邻接顶点。接顶点。连通图连通图的广度优先遍历算法为：的广度优先遍历算法为：（1 1）访问初始顶点）访问初始顶点v v并标记顶点并标记顶点v v为已访问；为已访问；（2 2）顶点）顶点v v入队列；入队列；（3 3）当队列非空时则继续执行，否则算法结束；）当队列非空时则继续执行，否则算法结束；（4 4）出队列取得

33、队头顶点）出队列取得队头顶点u u；（5 5）查找顶点）查找顶点u u的第一个邻接顶点的第一个邻接顶点w w；（6 6）若若顶顶点点u u的的邻邻接接顶顶点点w w不不存存在在，则则转转到到步步骤骤（3 3），否否则则循循环环执执行，行，（6.16.1）若顶点）若顶点w w尚未被访问则访问顶点尚未被访问则访问顶点w w并标记顶点并标记顶点w w为已访问；为已访问；（6.26.2）顶点）顶点w w入队列；入队列；（6.36.3）查查找找顶顶点点u u的的w w邻邻接接顶顶点点后后的的下下一一个个邻邻接接顶顶点点w w，转转到到步步骤骤（6 6）。）。本讲稿第二十九页，共五十五页三、非连通图的遍历

34、三、非连通图的遍历 对对于于非非连连通通图图，从从图图的的任任意意一一个个顶顶点点开开始始深深度度或或广广度度优优先先遍遍历历并并不不能能访访问图中的所有顶点。问图中的所有顶点。只能访问和初始顶点连通的所有顶点。只能访问和初始顶点连通的所有顶点。但是，每一个顶点都作为一次初始顶点进行深度优先遍历或广度优先遍但是，每一个顶点都作为一次初始顶点进行深度优先遍历或广度优先遍历，并根据顶点的访问标记来判断是否需要访问该顶点，就一定可以访历，并根据顶点的访问标记来判断是否需要访问该顶点，就一定可以访问非连通图中的所有顶点。问非连通图中的所有顶点。本讲稿第三十页，共五十五页邻接矩阵存储结构图类的深度优先遍

35、历成员函数如下：邻接矩阵存储结构图类的深度优先遍历成员函数如下：voidAdjMWGraph:DepthFirstSearch(constintv,intvisited,voidVisit(VerTitem)/连通图连通图G以以v为初始顶点序号、访问操作为为初始顶点序号、访问操作为Visit()的深度优先遍历的深度优先遍历/数组数组visited标记了相应顶点是否已访问过，标记了相应顶点是否已访问过，0表示未访问，表示未访问，1表示已访问表示已访问Visit(GetValue(v);/访问该顶点访问该顶点visitedv=1;/置已访问标记置已访问标记intw=GetFirstNeighbor

36、(v);/取第一个邻接顶点取第一个邻接顶点while(w!=-1)/当邻接顶点存在时循环当邻接顶点存在时循环if(!visitedw)DepthFirstSearch(w,visited,Visit);/递归递归w=GetNextNeighbor(v,w);/取下一个邻接顶点取下一个邻接顶点2.2.图的深度和广度优先遍历函数实现图的深度和广度优先遍历函数实现 一、一、深度优先遍历深度优先遍历本讲稿第三十一页，共五十五页二、非连通图的深度优先遍历二、非连通图的深度优先遍历voidAdjMWGraph:DepthFirstSearch(voidVisit(VerTitem)/非连通图非连通图G访问

37、操作为访问操作为Visit()的深度优先遍历的深度优先遍历int*visited=newintNumOfVertices();for(inti=0;iNumOfVertices();i+)visitedi=0;/初始化访问标记初始化访问标记for(i=0;iNumOfVertices();i+)if(!visitedi)DepthFirstSearch(i,visited,Visit);/深度优先遍历深度优先遍历deletevisited;本讲稿第三十二页，共五十五页三、三、广度优先遍历广度优先遍历#includeSeqQueue.h/包含静态数组结构的顺序队列类包含静态数组结构的顺序队列类v

38、oidAdjMWGraph:BroadFirstSearch(constintv,intvisited,voidVisit(VerTitem)/连通图连通图G以以v为初始顶点序号、访问操作为为初始顶点序号、访问操作为Visit()的广度优先遍历的广度优先遍历/数组数组visited标记了相应顶点是否已访问过，标记了相应顶点是否已访问过，0表示未访问，表示未访问，1表示已访问表示已访问VerTu,w;SeqQueuequeue;/定义队列定义队列Visit(GetValue(v);/访问该顶点访问该顶点visitedv=1;/置已访问标记置已访问标记queue.Append(v);/顶点顶点v入

39、队列入队列while(queue.NotEmpty()/队列非空时循环队列非空时循环u=queue.Delete();/出队列出队列w=GetFirstNeighbor(u);/取顶点取顶点u的第一个邻接顶点的第一个邻接顶点本讲稿第三十三页，共五十五页while(w!=-1)/邻接顶点存在时邻接顶点存在时if(!visitedw)/若该顶点没有访问过若该顶点没有访问过Visit(GetValue(w);/访问该顶点访问该顶点visitedw=1;/置已访问标记置已访问标记queue.Append(w);/顶点顶点w入队列入队列/取顶点取顶点u的邻接顶点的邻接顶点w的下一个邻接顶点的下一个邻接顶

40、点w=GetNextNeighbor(u,w);本讲稿第三十四页，共五十五页四、非连通图的广度优先遍历四、非连通图的广度优先遍历voidAdjMWGraph:BroadFirstSearch(voidVisit(VerTitem)/非连通图非连通图G访问操作为访问操作为Visit()的广度优先遍历的广度优先遍历int*visited=newintNumOfVertices();for(inti=0;iNumOfVertices();i+)visitedi=0;for(i=0;iNumOfVertices();i+)if(!visitedi)BroadFirstSearch(i,visited,

41、Visit);deletevisited;本讲稿第三十五页，共五十五页五、程序举例五、程序举例例例8-2以以图图8-8所所示示的的带带权权有有向向图图为为例例，编编写写测测试试上上述述图图的的深深度度优优先先和和广广度度优优先先遍遍历历成成员员函函数数的程序。的程序。测试程序设计如下：测试程序设计如下：#include#includetypedefcharVerT;/定义邻接矩阵图类中的定义邻接矩阵图类中的VerTtypedefcharDataType;/定义顺序表类中的定义顺序表类中的DataTypeconstintMaxVertices=100;/定义最大顶点个数定义最大顶点个数const

42、intMaxQueueSize=100;/定义队列的最大个数定义队列的最大个数constintMaxWeight=10000;/定义权值的无穷大定义权值的无穷大#includeAdjMWGraph.h/包含邻接矩阵的图类包含邻接矩阵的图类#includeCreatAdjMWGraph.h/包含邻接矩阵图的创建函数包含邻接矩阵图的创建函数voidPrintchar(charitem)/访问操作函数访问操作函数coutitem;本讲稿第三十六页，共五十五页voidmain(void)AdjMWGraphg;chara=A,B,C,D,E;RowColWeightrcw=0,1,10,0,4,20,

43、1,3,30,2,1,40,3,2,50;intn=5,e=5;CreatGraph(g,a,n,rcw,e);cout深度优先搜索序列为：深度优先搜索序列为：;g.DepthFirstSearch(Printchar);coutendl广度优先搜索序列为：广度优先搜索序列为：;g.BroadFirstSearch(Printchar);本讲稿第三十七页，共五十五页8.5 8.5 最小生成树最小生成树1.1.基本概念基本概念 一个有一个有n n个顶点的连通图的生成树是个顶点的连通图的生成树是原图的极小连通子图原图的极小连通子图，它包含原图中的所有它包含原图中的所有n n个顶点，并且有保持图连通

44、的最少的边。个顶点，并且有保持图连通的最少的边。注意：注意：（1 1）若在生成树中删除一条边就会使该生成树因变成非连通图而不再满足生成树的定义；）若在生成树中删除一条边就会使该生成树因变成非连通图而不再满足生成树的定义；（2 2）若在生成树中增加一条边就会使该生成树中因存在回路而不再满足生成树的定）若在生成树中增加一条边就会使该生成树中因存在回路而不再满足生成树的定义；义；（3 3）一个连通图的生成树可能有许多；）一个连通图的生成树可能有许多；（4 4）有）有n n个顶点的无向连通图，无论它的生成树的形状如何，一定有且只有个顶点的无向连通图，无论它的生成树的形状如何，一定有且只有n-1n-1条

45、边。条边。1V2V3V4V5V6V1V2V3V4V5V6V1V2V3V4V5V6V(a)a)(b)b)(c)c)无向图和它的不同的生成树无向图和它的不同的生成树 本讲稿第三十八页，共五十五页 如果无向连通图是一个带权图，那么它的所有生成树中必有如果无向连通图是一个带权图，那么它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为一棵边的权值总和最小的生成树，我们称这棵生成树为最小代价最小代价生成树生成树，简称，简称最小生成树。最小生成树。构造有构造有n n个顶点的无向连通带权图的最小生成树必须满足以下三条：个顶点的无向连通带权图的最小生成树必须满足以下三条：（1 1）构造的最小生

46、成树必须包括）构造的最小生成树必须包括n n个顶点；个顶点；（2 2）构造的最小生成树中有且只有）构造的最小生成树中有且只有n-1n-1条边；条边；（3 3）构造的最小生成树中不存在回路。）构造的最小生成树中不存在回路。典型的构造方法有两种，一种称作典型的构造方法有两种，一种称作普里姆（普里姆（PrimPrim）算法）算法，另一种称作另一种称作克鲁斯卡尔（克鲁斯卡尔（KruskalKruskal）算法）算法。本讲稿第三十九页，共五十五页2.2.普里姆算法普里姆算法 一、算法思想一、算法思想 假设假设G=(V,E)G=(V,E)为一个带权图，其中为一个带权图，其中V V为带权图中顶点的集合，为带

47、权图中顶点的集合，E E为带权为带权图中边的权值集合。设置两个新的集合图中边的权值集合。设置两个新的集合U U和和T T，其中，其中U U用于存放带权图用于存放带权图G G的最小生成树的顶点的集合，的最小生成树的顶点的集合，T T用于存放带权图用于存放带权图G G的最小生成树的权值的的最小生成树的权值的集合。集合。普里姆算法思想是普里姆算法思想是：令集合：令集合U U的初值为的初值为U=uU=u0 0（即假设构造最小（即假设构造最小生成树时从顶点生成树时从顶点u u0 0开始），集合开始），集合T T的初值为的初值为T=T=。从所有顶点。从所有顶点uUuU和和顶点顶点vV-UvV-U的带权边中

48、选出具有最小权值的边的带权边中选出具有最小权值的边(u,v)u,v)，将顶点，将顶点v v加入集加入集合合U U中，将边中，将边(u,v)u,v)加入集合加入集合T T中。如此不断重复，当中。如此不断重复，当U=VU=V时则最小生时则最小生成树构造完毕。此时集合成树构造完毕。此时集合U U中存放着最小生成树顶点的集合，集合中存放着最小生成树顶点的集合，集合T T中中存放着最小生成树边的权值集合。存放着最小生成树边的权值集合。每次向每次向临时生成树临时生成树加入使得加入使得新临时生成树新临时生成树有最小权的边。有最小权的边。本讲稿第四十页，共五十五页A AC CB BG GE EF FD D50

49、50606045455252424230306565505040407070A AC CB BG GE EF FD DA AC CB BG GE EF FD D5050A AC CB BG GE EF FD D50504040A AC CB BG GE EF FD D505050504040A AC CB BG GE EF FD D5050303050504040A AC CB BG GE EF FD D50504242303050504040A AC CB BG GE EF FD D505045454242303050504040(a)a)(b)b)(c)c)(d)d)(e)e)(f)f)(

50、g)g)(h)h)图图8-10普里姆算法构造最小生成树的过程普里姆算法构造最小生成树的过程 本讲稿第四十一页，共五十五页二、普里姆函数设计二、普里姆函数设计 普普里里姆姆函函数数应应有有两两个个参参数数，一一个个参参数数是是图图G G，定定义义为为邻邻接接矩矩阵阵存存储储结结构构图图类类的的对对象象；另另一一个个参参数数是是通通过过函函数数得得到到的的最最小小生生成成树树的的顶顶点点数数据据和和相相应应顶顶点点的的边边的的权权值值数数据据closeVertexcloseVertex。其其数数据据类类型型定定义义为为如如下下结构体：结构体：struct MinSpanTreestruct Min