第6章 图精选文档.ppt

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

1、第第6章章图图本讲稿第一页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院第第6 6章图章图6.16.1图的定义和基本术语图的定义和基本术语6.26.2图的存储结构图的存储结构6.36.3图的遍历图的遍历6.46.4图的应用图的应用教学内容教学内容本讲稿第二页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院1.1.掌握：图的基本掌握：图的基本概念及相关术语和性质概念及相关术语和性质2.2.熟练掌握：图的熟练掌握：图的邻接矩阵和邻接表邻接矩阵和邻接表两种存储表示方法两种存储表示方法3.3.熟练掌握：图的两种遍历方法熟练掌握：图的两种遍历方法

2、DFSDFS和和BFSBFS4.4.熟练掌握：最短路算法（熟练掌握：最短路算法（DijkstraDijkstra算法算法）5.5.掌握：掌握：最小生成树最小生成树的两种算法及的两种算法及拓扑排序拓扑排序算法的思想算法的思想教学目标教学目标本讲稿第三页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院6.1 6.1 图的定义和术语图的定义和术语图：图：Graph=(V,E)V：顶点：顶点(数据元素数据元素)的的有穷非空有穷非空集合；集合；E：边的：边的有穷有穷集合。集合。无向图：无向图：有向图：有向图：每条边都是无方向的每条边都是无方向的每条边都是有方向的每条边都是有方

3、向的本讲稿第四页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院完全图：完全图：任意两个点都有一条边相连任意两个点都有一条边相连无向完全图有向完全图n n(n n-1)/2-1)/2条边条边条边条边n n(n n-1)-1)条边条边条边条边本讲稿第五页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院稀疏图稀疏图：有很少边或弧的图。：有很少边或弧的图。稠密图稠密图：有较多边或弧的图。：有较多边或弧的图。网网：边：边/弧带权的图。弧带权的图。邻接邻接：有边：有边/弧相连的两个顶点之间的关系。弧相连的两个顶点之间的关系。存在存在(vi,vj)，

4、则称，则称vi和和vj互为互为邻接点邻接点；存在存在，则称，则称vi邻接到邻接到vj，vj邻接于邻接于vi关联关联(依附依附)：边边/弧与顶点之间的关系。弧与顶点之间的关系。存在存在(vi,vj)/，则称该边则称该边/弧关联于弧关联于vi和和vj本讲稿第六页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院顶点的度顶点的度：与该顶点相关联的边的数目，记为：与该顶点相关联的边的数目，记为TD(v)在在有向图有向图中中,顶点的度等于该顶点的顶点的度等于该顶点的入度入度与与出度出度之和。之和。顶点顶点v的入度的入度是以是以v为终点的有向边的条数为终点的有向边的条数,记作记作

5、ID(v)顶点顶点v的出度的出度是以是以v为始点的有向边的条数为始点的有向边的条数,记作记作OD(v)问：问：当有向图中仅当有向图中仅1 1个顶点的入度为个顶点的入度为0,0,其余顶其余顶点的入度均为点的入度均为1 1，此时是何形状？，此时是何形状？答：答：是树！而且是一棵有向树！是树！而且是一棵有向树！本讲稿第七页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院路径路径：接续的边构成的顶点序列。：接续的边构成的顶点序列。路径长度路径长度：路径上边或弧的数目：路径上边或弧的数目/权值之和。权值之和。回路回路(环环)：第一个顶点和最后一个顶点相同的路径。第一个顶点和最

6、后一个顶点相同的路径。简单路径：简单路径：除路径起点和终点可以相同外，其余顶点均不相同的除路径起点和终点可以相同外，其余顶点均不相同的路径。路径。简单回路简单回路(简单环简单环)：除路径起点和终点相同外，其余顶点均不相同的路径。除路径起点和终点相同外，其余顶点均不相同的路径。本讲稿第八页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院 非非连连通通图图 连连通通图图 强强连连通通图图 非非强强连连通通图图 V0V0 V1V1 V2V2 V3V3 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3 V0V0 V2V2 V3V3 V

7、1V1 V5V5 V4V4连通图（强连通图）连通图（强连通图）连通图（强连通图）连通图（强连通图）在无（有）向图在无（有）向图G=(V,E)G=(V,E)中，若对任何两个顶点中，若对任何两个顶点 v v、u u 都存在从都存在从v v 到到 u u 的路径，则称的路径，则称G G是连通图（强连通图）。是连通图（强连通图）。本讲稿第九页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院(a)(a)(b)(b)(c)(c)V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2子图

8、子图子图子图设有两个图设有两个图G=G=（V V，EE）、）、G1=G1=（V1V1，E1E1），若），若V1V1 V V，E1 E1 E E，则称，则称 G1G1是是G G的子图。的子图。例例:(b):(b)、(c)(c)是是 (a)(a)的子图的子图权与网权与网权与网权与网图中边或弧所具有的相关数称为权。表明从一个顶点到图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。另一个顶点的距离或耗费。带权的图称为带权的图称为网网网网。本讲稿第十页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院连通分量（强连通分量）连通分量（强连通分量）连通分量（强

9、连通分量）连通分量（强连通分量）非非连连通通图图 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4无向图无向图G G 的极大连通子图称为的极大连通子图称为G G的连通分量。的连通分量。极大连通子图意思是：该子图是极大连通子图意思是：该子图是 G G 连通子图，将连通子图，将G G 的的任何不在该子图中的顶点加入，子图不再连通。任何不在该子图中的顶点加入，子图不再连通。V0V0 V2V2 V3V3 V1V1 V5V5 V4V4连通分量连通分量本讲稿第十一页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院有向图有向图G G 的极大强连通子图称为的极大强连通子图

10、称为G G的强连通分量。极大的强连通分量。极大强连通子图意思是：该子图是强连通子图意思是：该子图是G G的强连通子图，将的强连通子图，将D D的的任何不在该子图中的顶点加入，子图不再是强连通的。任何不在该子图中的顶点加入，子图不再是强连通的。强连通分量强连通分量 V0V0 V1V1 V2V2 V3V3 V0V0 V2V2 V3V3 V1V1本讲稿第十二页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院极小连通子图极小连通子图极小连通子图极小连通子图：该子图是：该子图是G G 的连通子图，在该子图中删的连通子图，在该子图中删除任何一条边，子图不再连通。除任何一条边，子

11、图不再连通。生成树：生成树：生成树：生成树：包含无向图包含无向图G G 所有顶点的极小连通子图。所有顶点的极小连通子图。生成森生成森生成森生成森林：林：林：林：对非连通图，由各个连通分量的生成树的集合。对非连通图，由各个连通分量的生成树的集合。连通图连通图 G1G1G1G1的生成树的生成树 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2本讲稿第十三页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院6.2 6.2 图的存储结构图的存储结构邻接表邻接表邻接多重表邻接多重

12、表十字链表十字链表链式存储结构：链式存储结构：顺序存储结构：顺序存储结构：数组表示法（邻接矩阵）数组表示法（邻接矩阵）多重链表多重链表重点介绍：重点介绍：邻接矩阵邻接矩阵(数组数组)表示法表示法邻接表邻接表(链式链式)表示法表示法本讲稿第十四页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院v建立一个建立一个顶点表顶点表（记录各个顶点信息）（记录各个顶点信息）和一个和一个邻接矩阵邻接矩阵（表示各个顶点之间关系）（表示各个顶点之间关系）。v设图设图 A=(A=(V V,E E)有有 n n 个顶点，则图的邻接矩阵是一个二个顶点，则图的邻接矩阵是一个二维数组维数组 A.

13、EdgennA.Edgenn，定义为：，定义为：数组（邻接矩阵）表示法数组（邻接矩阵）表示法本讲稿第十五页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院邻接矩阵：A.Edge=（v1v2v3v4v5）v1v2v3v4v50000000000000000000000000分析分析1 1：无向图的邻接矩阵是无向图的邻接矩阵是对称对称的；的；分析分析2 2：顶点顶点i i 的的度度第第 i i 行行(列列)中中1 1 的个数；的个数；特别：特别：完全图完全图的邻接矩阵中，对角元素为的邻接矩阵中，对角元素为0 0，其余，其余1 1。01010101010101110101

14、011100101010101010111010101110顶点表：无向图的邻接矩阵表示法无向图的邻接矩阵表示法v1v2v3v5v4v4本讲稿第十六页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院分析分析分析分析1 1 1 1：有向图的邻接矩阵有向图的邻接矩阵可能是不对称可能是不对称的。的。分析分析分析分析2 2 2 2：顶点的顶点的出度出度=第第i i行元素之和行元素之和 顶点的顶点的入度入度=第第i i列元素之和列元素之和 顶点的顶点的度度=第第i i行元素之和行元素之和+第第i i列元素之和列元素之和 v1v2v3v4A A邻接矩阵：A.Edge=(v1v2

15、v3v4)v1v2v3v40000000000000000注：注：在有向图的邻接矩阵中，在有向图的邻接矩阵中，第第i i行含义：以结点行含义：以结点v vi i为尾的弧为尾的弧(即出度边）；即出度边）；第第i i列含义：以结点列含义：以结点v vi i为头的弧为头的弧(即入度边）。即入度边）。顶点表：01100000000110000110000000011000有向图的邻接矩阵表示法有向图的邻接矩阵表示法本讲稿第十七页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院定义为：定义为：A.Edgeij=Wij或（或（vi,vj）VR无边（弧）无边（弧）v1v2v3v4

16、Nv5v65489755613邻接矩阵：N.Edge=(v1v2v3v4v5v6)顶点表：57489565315748956531网（即有权图）的邻接矩阵表示法网（即有权图）的邻接矩阵表示法本讲稿第十八页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院优点：优点：容易实现图的操作，如：求某顶点的度、判断顶容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边、找顶点的邻接点等等。点之间是否有边、找顶点的邻接点等等。缺点：缺点：n n个顶点需要个顶点需要n*nn*n个单元存储边个单元存储边;空间效率为空间效率为O(nO(n2 2)。对稀疏图而言尤其浪费空间。对稀疏图

17、而言尤其浪费空间。邻接矩阵表示法的特点邻接矩阵表示法的特点本讲稿第十九页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院/用两个数组分别存储顶点表和邻接矩阵用两个数组分别存储顶点表和邻接矩阵#defineMaxInt32767/表示极大值，即表示极大值，即#defineMVNum100/最大顶点数最大顶点数typedefcharVerTexType;/假设顶点的数据类型为字符型假设顶点的数据类型为字符型typedefintArcType;/假设边的权值类型为整型假设边的权值类型为整型typedefstructVerTexTypevexsMVNum;/顶点表顶点表Ar

18、cTypearcsMVNumMVNum;/邻接矩阵邻接矩阵intvexnum,arcnum;/图的当前点数和边数图的当前点数和边数AMGraph;邻接矩阵的存储表示邻接矩阵的存储表示本讲稿第二十页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院（1 1）输入）输入总顶点数和总边数总顶点数和总边数。（2 2）依次输入）依次输入点的信息存入顶点表点的信息存入顶点表中。中。（3 3）初始化邻接矩阵初始化邻接矩阵，使每个权值初始化为极大值。，使每个权值初始化为极大值。（4 4）构造邻接矩阵构造邻接矩阵。【算法思想算法思想】采用邻接矩阵表示法创建无向网采用邻接矩阵表示法创建无

19、向网本讲稿第二十一页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院StatusCreateUDN(AMGraph&G)/采用邻接矩阵表示法，创建无向网采用邻接矩阵表示法，创建无向网GcinG.vexnumG.arcnum;/输入总顶点数，总边数输入总顶点数，总边数for(i=0;iG.vexsi;/依次输入点的信息依次输入点的信息for(i=0;iG.vexnum;+i)/初始化邻接矩阵，边的权值均置为极大值初始化邻接矩阵，边的权值均置为极大值for(j=0;jG.vexnum;+j)G.arcsij=MaxInt;for(k=0;kv1v2w;/输入一条边依附的

20、顶点及权值输入一条边依附的顶点及权值i=LocateVex(G,v1);j=LocateVex(G,v2);/确定确定v1和和v2在在G中的位置中的位置G.arcsij=w;/边边的权值置为的权值置为wG.arcsji=G.arcsij;/置置的对称边的对称边的权值为的权值为w/forreturnOK;/CreateUDN【算法描述算法描述】本讲稿第二十二页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院intLocateVex(MGraphG,VertexTypeu)/*初始条件初始条件:图图G存在存在,u和和G中顶点有相同特征中顶点有相同特征*/*操作结果操作结

21、果:若若G中存在顶点中存在顶点u,则返回该顶点在图中位置则返回该顶点在图中位置;否则返回否则返回-1*/inti;for(i=0;iG.vexnum;+i)if(u=G.vexsi)returni;return-1;本讲稿第二十三页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院v对每个顶点对每个顶点vi建立一个建立一个单链表单链表，把与，把与vi有关联的有关联的边的信息链接边的信息链接起来，每起来，每个结点设为个结点设为3个域；个域；v v每个单链表有一个每个单链表有一个每个单链表有一个每个单链表有一个头结点头结点头结点头结点（设为（设为（设为（设为2 2个域），

22、存个域），存个域），存个域），存v vi i信息；信息；信息；信息；adjvex nextarcinfodatafirstarc表结点表结点表结点表结点头结点头结点头结点头结点邻接点域，表示vi一个邻接点的位置链域，指向vi下一个边或弧的结点数据域，与边有关信息（如权值）数据域，存储顶点vi 信息链域，指向单链表的第一个结点v v 每个单链表的每个单链表的每个单链表的每个单链表的头结点另外用顺序存储头结点另外用顺序存储头结点另外用顺序存储头结点另外用顺序存储结构存储。结构存储。结构存储。结构存储。邻接表（链式）表示法邻接表（链式）表示法本讲稿第二十四页，共八十二页 2022年10月3日 华东交

23、通大学理工学院华东交通大学理工学院0123413341420注：注：邻接表不唯一邻接表不唯一，因各个边结点的链入顺序是任意的，因各个边结点的链入顺序是任意的v1v2v3v4v5231420无向图的邻接表表示无向图的邻接表表示空间效率为空间效率为O(n+2e)O(n+2e)。若是稀疏图若是稀疏图(en(eG.vexnumG.arcnum;/输入总顶点数，总边数输入总顶点数，总边数for(i=0;iG.verticesi.data;/输入顶点值输入顶点值G.verticesi.firstarc=NULL;/初始化表头结点的指针域为初始化表头结点的指针域为NULL/forfor(k=0;kv1v2;

24、/输入一条边依附的两个顶点输入一条边依附的两个顶点i=LocateVex(G,v1);j=LocateVex(G,v2);p1=newArcNode;/生成一个新的边结点生成一个新的边结点*p1p1-adjvex=j;/邻接点序号为邻接点序号为jp1-nextarc=G.verticesi.firstarc;G.verticesi.firstarc=p1;/将新结点将新结点*p1插入顶点插入顶点vi的边表头部的边表头部p2=newArcNode;/生成另一个对称的新的边结点生成另一个对称的新的边结点*p2p2-adjvex=i;/邻接点序号为邻接点序号为ip2-nextarc=G.vertic

25、esj.firstarc;G.verticesj.firstarc=p2;/将新结点将新结点*p2插入顶点插入顶点vj的边表头部的边表头部/forreturnOK;/CreateUDG【算法描述算法描述】本讲稿第三十页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院优点：优点：空间效率高，容易寻找顶点的邻接点；空间效率高，容易寻找顶点的邻接点；缺点：缺点：判断两顶点间是否有边或弧，需搜索两结点对判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。应的单链表，没有邻接矩阵方便。邻接表表示法的特点邻接表表示法的特点本讲稿第三十一页，共八十二页 2022

26、年10月3日 华东交通大学理工学院华东交通大学理工学院v1v2v3v5v4v44321013341420v5v4v3v2v1231420（v1v2v3v4v5）v1v2v3v4v5000000000000000000000000001010101010101110101011100101010101010111010101110邻接矩阵与邻接表表示法的关系邻接矩阵与邻接表表示法的关系1.1.联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，链邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。表中结点个数等于一行中非零元素的个数。本讲稿第三十二页，共八十二页 20

27、22年10月3日 华东交通大学理工学院华东交通大学理工学院2.2.区别：区别：对于任一确定的无向图，邻接矩阵是对于任一确定的无向图，邻接矩阵是唯一唯一的（行列号与顶的（行列号与顶点编号一致），但邻接表点编号一致），但邻接表不唯一不唯一（链接次序与顶点编号无（链接次序与顶点编号无关）。关）。邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的空间复杂度为而邻接表的空间复杂度为O(n+e)O(n+e)。3.3.用途：用途：邻接矩阵多用于邻接矩阵多用于稠密图稠密图；而邻接表多用于；而邻接表多用于稀疏图稀疏图邻接矩阵与邻接表表示法的关系邻接矩阵与邻接表表示法的关系本讲稿第三

28、十三页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院遍历定义：遍历定义：从已给的连通图中某一顶点出发，沿着一些边访从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历图的遍历图的遍历图的遍历，它是，它是，它是，它是图的图的基本运算基本运算。遍历实质：遍历实质：找每个顶点的邻接点的过程。找每个顶点的邻接点的过程。图的特点：图的特点：图中可能存在图中可能存在回路回路，且图的任一顶点都可能与其，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边它顶点相

29、通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点又回到了曾经访问过的顶点。6.3 6.3 图的遍历图的遍历本讲稿第三十四页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院图常用的遍历：图常用的遍历：深度优先搜索深度优先搜索广度优先搜索广度优先搜索解决思路：解决思路：设置设置辅助数组辅助数组 visitedvisited n n，用来标记每个被，用来标记每个被访问过的顶点。访问过的顶点。初始状态为初始状态为0 0i i 被访问，改被访问，改 visitedvisited i i 为为1 1，防止被多次访问，防止被多次访问怎样避免重复访问？怎样避免重复访

30、问？本讲稿第三十五页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院基本思想：基本思想：仿树的先序遍历过程。仿树的先序遍历过程。v1v1v2v3v8v7v6v4v5DFSDFS结果结果结果结果v2v4v8v5v3v6v7起点深度优先搜索深度优先搜索(DFS(DFS Depth_First Search)Depth_First Search)本讲稿第三十六页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院深度优先搜索的步骤深度优先搜索的步骤简单归纳：简单归纳：访问起访问起始点始点v v;若若v v的的第第1 1个个邻接点没访问过，邻接点没访

31、问过，深度遍历深度遍历此邻接点；此邻接点；若当前邻接点已访问过，再找若当前邻接点已访问过，再找v v的第的第2 2个邻接点个邻接点重新重新遍历。遍历。本讲稿第三十七页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院深度优先搜索的步骤深度优先搜索的步骤详细归纳：详细归纳：E在访问图中某一起始顶点在访问图中某一起始顶点v后，由后，由v出发，访问出发，访问它的任一邻接顶点它的任一邻接顶点w1；E再从再从w1出发，访问出发，访问与与w1邻接邻接但还但还未未被访问被访问过的顶点过的顶点w2；E然后再从然后再从w2出发，进行类似的访问，出发，进行类似的访问，E如此进行下去，直至

32、到达所有的邻如此进行下去，直至到达所有的邻接顶点都被访问过的顶点接顶点都被访问过的顶点u为止。为止。起点本讲稿第三十八页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院深度优先搜索的步骤深度优先搜索的步骤详细归纳：详细归纳：E接着，退回一步，接着，退回一步，退到前一次刚访退到前一次刚访问过的顶点问过的顶点，看是否还有其它没有被，看是否还有其它没有被访问的邻接顶点。访问的邻接顶点。如果有，如果有，则访问此顶点，之后再从此则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；顶点出发，进行与前述类似的访问；如果没有，如果没有，就就再退回一步再退回一步进行搜索。进行搜索

33、。重复上述过程，直到连通图中所有重复上述过程，直到连通图中所有顶点都被访问过为止。顶点都被访问过为止。起点v2v1v3v5v4v6v2v1v3v5v4v6本讲稿第三十九页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院讨论讨论1 1：计算机如何实现：计算机如何实现DFSDFS？1 2 3 4 5 61 0 0 0 0 0 02 2 0 0 0 0 0 03 0 0 0 0 0 04 0 0 0 0 0 05 0 0 0 0 0 06 0 0 0 0 0 000000012345601000011 100001 11 110001 11 11 10101 11 11

34、111 101 11 11 11 11 11DFSDFS结果结果结果结果邻邻接接矩矩阵阵A辅助数组辅助数组 visitedn起点v2v1v3v5v2v1v3v5v4v4v6v6开辅助数组开辅助数组 visitedn！1 2 3 4 561 0 1 11 1 1 1 002 21 1 0 0 01 1031 1 0 0 01 1041 1 0 0 0 01 15 0 1 11 1 0 006 0 0 0 1 1 00本讲稿第四十页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院voidDFS(AMGraphG,intv)/图图G为邻接矩阵类型为邻接矩阵类型coutv;

35、visitedv=true;/访问第访问第v个顶点个顶点for(w=0;wG.vexnum;w+)/依次检查邻接矩阵依次检查邻接矩阵v所在的行所在的行if(G.arcsvw!=0)&(!visitedw)DFS(G,w);/w是是v的邻接点，如果的邻接点，如果w未访问，则递归调用未访问，则递归调用DFS讨论讨论讨论讨论2 2 2 2：DFSDFSDFSDFS算法如何编程？算法如何编程？算法如何编程？算法如何编程？可以用递归算法！可以用递归算法！本讲稿第四十一页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院讨论讨论讨论讨论3 3 3 3：在图的邻接表中如何进行：在图

36、的邻接表中如何进行：在图的邻接表中如何进行：在图的邻接表中如何进行DFSDFSDFSDFS？v0v1v2v3v0v1v2v3DFSDFS结果结果结果结果00000123辅助数组辅助数组 visitedn1000110011101111照样借用照样借用visitedn！起点0123本讲稿第四十二页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院讨论讨论讨论讨论4 4 4 4：邻接表的：邻接表的：邻接表的：邻接表的DFSDFSDFSDFS算法如何编程？算法如何编程？算法如何编程？算法如何编程？voidDFS(ALGraphG,intv)/图图G为邻接表类型为邻接表类型c

37、outadjvex;/表示表示w是是v的邻接点的邻接点if(!visitedw)DFS(G,w);/如果如果w未访问，则递归调用未访问，则递归调用DFSp=p-nextarc;/p指向下一个边结点指向下一个边结点仍可用递归算法仍可用递归算法本讲稿第四十三页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院n用用邻接矩阵邻接矩阵来表示图，遍历图中每一个顶点都要来表示图，遍历图中每一个顶点都要从头从头扫描扫描该顶点所在行，时间复杂度为该顶点所在行，时间复杂度为O(O(n n2 2)。n用用邻接表邻接表来表示图，虽然有来表示图，虽然有 2 2e e 个表结点，但只需扫描个表

38、结点，但只需扫描 e e 个结点即可完成遍历，加上访问个结点即可完成遍历，加上访问 n n个头结点的时间，个头结点的时间，时间复杂度为时间复杂度为O(O(n n+e e)。结论：结论：稠密图稠密图适于在邻接矩阵上进行深度遍历；适于在邻接矩阵上进行深度遍历；稀疏图稀疏图适于在邻接表上进行深度遍历。适于在邻接表上进行深度遍历。DFSDFS算法效率分析算法效率分析本讲稿第四十四页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院基本思想：基本思想：仿树的层次遍历过程仿树的层次遍历过程广度优先搜索广度优先搜索(BFS(BFS Breadth_First Search)Brea

39、dth_First Search)v1v1v2v3v8v7v6v4v5BFSBFS结果结果结果结果v2v3v4v5v6v7v8起点本讲稿第四十五页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院简单归纳：简单归纳：在访问了在访问了起始点起始点v v之后，依次访问之后，依次访问 v v的邻接点的邻接点；然后再依次访问然后再依次访问这些顶点中未被访问过的邻接点这些顶点中未被访问过的邻接点；直到所有顶点都被访问直到所有顶点都被访问过为止。过为止。广度优先搜索是一种广度优先搜索是一种分层分层的搜索过程，每向前走一的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样

40、有回退步可能访问一批顶点，不像深度优先搜索那样有回退的情况。的情况。因此，广度优先搜索因此，广度优先搜索不是一个递归不是一个递归的过程，其算法的过程，其算法也不是递归的。也不是递归的。广度优先搜索的步骤广度优先搜索的步骤本讲稿第四十六页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院讨论讨论1 1：计算机如何实现：计算机如何实现BFSBFS？邻接表邻接表除辅助数组除辅助数组visitedn外，还外，还需再开一辅助队列需再开一辅助队列起点辅助队列辅助队列v2已访问过了已访问过了BFS 遍历结果入队！入队！初始f=n-1,r=0本讲稿第四十七页，共八十二页 2022年1

41、0月3日 华东交通大学理工学院华东交通大学理工学院（1 1）从图中某个顶点）从图中某个顶点v v出发，访问出发，访问v v，并置，并置visitedvisitedv v 的值为的值为truetrue，然后将，然后将v v进队。进队。（2 2）只要队列不空，则重复下述处理。）只要队列不空，则重复下述处理。队头顶点队头顶点u u出队。出队。依次检查依次检查u u的所有邻接点的所有邻接点w w，如果，如果visitedvisitedw w 的值的值为为falsefalse，则访问，则访问w w，并置，并置visitedvisitedw w 的值为的值为truetrue，然，然后将后将w w进队。进队

42、。【算法思想算法思想】本讲稿第四十八页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院voidBFS(GraphG,intv)/按广度优先非递归遍历连通图按广度优先非递归遍历连通图Gcout=0;w=NextAdjVex(G,u,w)if(!visitedw)/w为为u的尚未访问的邻接顶点的尚未访问的邻接顶点coutw;visitedw=true;EnQueue(Q,w);/w进队进队/if/while/BFS【算法描述算法描述】本讲稿第四十九页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院如果使用邻接矩阵，则如果使用邻接矩阵，则BFS

43、对于每一个被访问到的顶点，都要循对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（环检测矩阵中的整整一行（n个元素），总的时间代价为个元素），总的时间代价为O(n2)。用邻接表来表示图，虽然有用邻接表来表示图，虽然有2e个表结点，但只需扫描个表结点，但只需扫描e个结点个结点即可完成遍历，加上访问即可完成遍历，加上访问n个头结点的时间，时间复杂度为个头结点的时间，时间复杂度为O(n+e)。BFSBFS算法效率分析算法效率分析本讲稿第五十页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院空间复杂度相同，都是空间复杂度相同，都是O(n)O(n)(借用了堆栈或队列）；

44、借用了堆栈或队列）；时间复杂度只与存储结构时间复杂度只与存储结构（邻接矩阵或邻接表）（邻接矩阵或邻接表）有关，而有关，而与搜索路径无关。与搜索路径无关。DFSDFS与与BFSBFS算法效率比较算法效率比较本讲稿第五十一页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院最小生成树最小生成树最短路径最短路径拓扑排序拓扑排序关键路径关键路径6.4 6.4 图的应用图的应用本讲稿第五十二页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院极小连通子图极小连通子图极小连通子图极小连通子图：该子图是该子图是G G 的连通子图，在该子图中删除任何一的连通

45、子图，在该子图中删除任何一条边，子图不再连通。条边，子图不再连通。生成树：生成树：生成树：生成树：包含图包含图G G所有顶点的极小连通子图（所有顶点的极小连通子图（n-1条边）条边）。G1G1的生成树的生成树连通图连通图 G1G1 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2最小生成树最小生成树本讲稿第五十三页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院DFSDFS生成生成树树邻邻接接表表0123413341420v4v3v2v1v0231420v0v2v1v

46、4v3BFSBFS生成生成树树v0v1v3v2v4无向连通图画出下图的生成树画出下图的生成树v0v1v2v4v4v3本讲稿第五十四页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院求最小生成树求最小生成树首先明确首先明确：使用不同的遍历图的方法，可以得到不同的生成树使用不同的遍历图的方法，可以得到不同的生成树从不同的顶点出发，也可能得到不同的生成树。从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，按照生成树的定义，n n 个顶点的个顶点的连通网络连通网络的生成树有的生成树有 n n 个顶点、个顶点、n-n-1 1 条边。条边。目标：目标：在网的多个生成树

47、中，寻找一个在网的多个生成树中，寻找一个各边各边权值之和最小的权值之和最小的生成树生成树本讲稿第五十五页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院v必须只使用该必须只使用该网中的边网中的边来构造最小生成树；来构造最小生成树；v必须使用且仅使用必须使用且仅使用n-1n-1条边条边来联结网络中的来联结网络中的n n个个顶点顶点v不能使用产生不能使用产生回路回路的边的边构造最小生成树的准则构造最小生成树的准则本讲稿第五十六页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院欲在欲在n n个城市间建立通信网，则个城市间建立通信网，则n n个城

48、市应铺个城市应铺n-1n-1条线路；条线路；但因为每条线路都会有对应的经济成本，而但因为每条线路都会有对应的经济成本，而n n个城市可能个城市可能有有n(n-1)/2 n(n-1)/2 条线路，那么，条线路，那么，如何选择如何选择n n1 1条线路，使总费条线路，使总费用最少？用最少？数学模型：数学模型：顶点顶点表示城市，有表示城市，有n n个；个；边边表示线路，有表示线路，有n n1 1条；条；边的权值边的权值表示线路的经济代价；表示线路的经济代价；连通网连通网表示表示n n个城市间通信网。个城市间通信网。显然此连通网是一个生成树！最小生成树的典型用途最小生成树的典型用途本讲稿第五十七页，共

49、八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院vPrimPrim（普里姆）算法（普里姆）算法 vKruskalKruskal（克鲁斯卡尔）算法（克鲁斯卡尔）算法PrimePrime算法算法:归并顶点归并顶点，与边数无关，适于，与边数无关，适于稠密网稠密网Kruskal算法：算法：归并边归并边，适于，适于稀疏网稀疏网如何求最小生成树如何求最小生成树本讲稿第五十八页，共八十二页 2022年10月3日 华东交通大学理工学院华东交通大学理工学院设连通网络设连通网络N=V,E 1.1.从从从从某某某某顶顶顶顶点点点点 u u0 0 出出出出发发发发，选选选选择择择择与与与与它它

50、它它关关关关联联联联的的的的具具具具有有有有最最最最小小小小权权权权值值值值的的的的边边边边(u u0 0,v v)，将其顶点加入到，将其顶点加入到，将其顶点加入到，将其顶点加入到生成树的顶点集合生成树的顶点集合U中中中中 2.2.每每每每一一一一步步步步从从从从一一一一个个个个顶顶顶顶点点点点在在在在U U中中中中，而而而而另另另另一一一一个个个个顶顶顶顶点点点点不不不不在在在在U U中中中中的的的的各各各各条条条条边边边边中中中中选选选选择择择择权权权权值值值值最最最最小小小小的的的的边边边边(u,(u,v),v),把把把把它它它它的的的的顶顶顶顶点点点点加加加加入入入入到到到到U中中中中