图的遍历和连通性 (2)幻灯片.ppt

图的遍历和连通性1第1页，共25页，编辑于2022年，星期五7.3 7.3 图的遍历图的遍历遍历：遍历：从已给的连通图中某一顶点出发，沿着一些边，访遍图从已给的连通图中某一顶点出发，沿着一些边，访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍图的遍图的遍图的遍历历历历，它是，它是，它是，它是图的图的基本运算。基本运算。遍历实质：遍历实质：找每个顶点的邻接点的过程。找每个顶点的邻接点的过程。图的特点：图的特点：图中可能存在图中可能存在回路，回路，且图的任一顶点都可能与其它且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点回到了曾经访问过的顶点。解决思路：解决思路：可设置一个可设置一个辅助数组辅助数组 visited n，用来标记每个，用来标记每个被访问过的顶点。它的初始状态为被访问过的顶点。它的初始状态为falsefalse，在图的遍历过，在图的遍历过程中，一旦某一个顶点程中，一旦某一个顶点i 被访问，就立即改被访问，就立即改 visited i为为truetrue，防止它被重复访问。，防止它被重复访问。怎样避免重复访问？2第2页，共25页，编辑于2022年，星期五深度优先搜索深度优先搜索和和广度优先搜索广度优先搜索 图常用的遍历：图常用的遍历：一、深度优先搜索一、深度优先搜索(DFS)(DFS)Depth_First Search基本思想：基本思想：类似于树的先根遍历过程。类似于树的先根遍历过程。1、连通图的深度优先搜索遍历、连通图的深度优先搜索遍历步骤：步骤：访问起始点访问起始点 v;v;依次从依次从v v的未被访问的邻接点出发深度优先遍历图直至图的未被访问的邻接点出发深度优先遍历图直至图中所有和中所有和v v有路径相通的顶点都被访问到。有路径相通的顶点都被访问到。3第3页，共25页，编辑于2022年，星期五v1v1v2v3v8v7v6v4v5DFS DFS 结果：结果：例例例例1 1 1 1：v2v4v8v5v3v6v7起点应退回到V8，因为V2已有标记void DFS(Graph G,int v)/从顶点从顶点v v出发，深度优先遍历出发，深度优先遍历G G visitedv=TRUE;VisitFunc(v);for(w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/对对v的尚未访问的邻接顶点的尚未访问的邻接顶点w递归调用递归调用DFS/DFS4第4页，共25页，编辑于2022年，星期五 对于无向图，这个算法可以对于无向图，这个算法可以遍历到遍历到v v顶点所在的连通分量顶点所在的连通分量中的所有顶点中的所有顶点，而与，而与v v顶点不在一个连通分量中的所有顶顶点不在一个连通分量中的所有顶点遍历不到；点遍历不到；对于有向图可以对于有向图可以遍历到起始顶点遍历到起始顶点v v能够到达的所有顶点。能够到达的所有顶点。若希望遍历到图中的所有顶点，就需要在上述深度优先遍若希望遍历到图中的所有顶点，就需要在上述深度优先遍历算法的基础上，历算法的基础上，增加对每个顶点访问状态的检测。增加对每个顶点访问状态的检测。2、非连通图的深度优先搜索遍历、非连通图的深度优先搜索遍历步骤：步骤：访问起始点访问起始点 v v及图中所有和及图中所有和v v有路径相通的顶点。有路径相通的顶点。如果图中尚有顶点未被访问，则以该顶点为起始点，如果图中尚有顶点未被访问，则以该顶点为起始点，进行深度优先搜索遍历。重复上述过程，直至所有顶进行深度优先搜索遍历。重复上述过程，直至所有顶点都已被访问。点都已被访问。5第5页，共25页，编辑于2022年，星期五abchdekfgF F F F F F F F FTTTTTTTTTachd kfe bgachkfedbg访问标志访问标志:访问次序访问次序:例例2:2:0 1 2 3 4 5 6 7 88123456706第6页，共25页，编辑于2022年，星期五void DFSTraverse(Graph G,Status(*Visit)(int v)/对图对图 G 作深度优先遍历作深度优先遍历。VisitFunc=Visit;for(v=0;vG.vexnum;+v)visitedv=FALSE;/访问标志数组初始化访问标志数组初始化 for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);/对尚未访问的顶点调用对尚未访问的顶点调用DFS7第7页，共25页，编辑于2022年，星期五DFS DFS 算法效率分析算法效率分析算法效率分析算法效率分析:（设图中有设图中有设图中有设图中有 n 个顶点，个顶点，个顶点，个顶点，e e 条边条边条边条边）（1）如果用邻接矩阵来表示图，遍历图中每一个顶点都要）如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历全部顶点所需的时间从头扫描该顶点所在行，因此遍历全部顶点所需的时间为为O(n2)。（2）如果用邻接表来表示图，虽然有）如果用邻接表来表示图，虽然有 2e 个表结点，个表结点，但只需扫描但只需扫描 e 个结点即可完成遍历，加上访问个结点即可完成遍历，加上访问 n个头结个头结点的时间，因此遍历图的时间复杂度为点的时间，因此遍历图的时间复杂度为O(n+e)。结结 论：论：稠密图稠密图适于在邻接矩阵上进行深度优先遍历；适于在邻接矩阵上进行深度优先遍历；稀疏图稀疏图适于在邻接表上进行深度优先遍历。适于在邻接表上进行深度优先遍历。8第8页，共25页，编辑于2022年，星期五二、广度优先搜索二、广度优先搜索(BFS)(BFS)基本思想：基本思想：仿树的层次遍历过程。仿树的层次遍历过程。Breadth_First Search在访问了起始点在访问了起始点v v之后，之后，依次访问依次访问 v v的各个未曾访问过的的各个未曾访问过的邻接点邻接点；然后按这些顶点被访问的然后按这些顶点被访问的先后次序先后次序依次访问它们的邻依次访问它们的邻接点，直至图中所有和接点，直至图中所有和V V有路径相通的顶点都被访问到。有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问若此时图中尚有顶点未被访问,则则另选图中一个未曾被另选图中一个未曾被访问的顶点作起始点访问的顶点作起始点，重复上述过程，直至图中所有，重复上述过程，直至图中所有顶点都被访问到为止。顶点都被访问到为止。步骤：步骤：9第9页，共25页，编辑于2022年，星期五v1v1v2v3v8v7v6v4v5BFS 结果：结果：例例1 1：v2v3v4v5v6v7v8v3 BFS BFS 结果：结果：结果：结果：v4 v5 起点起点v2 v1 v6v9 v8 v7例例例例2 2 2 2：10第10页，共25页，编辑于2022年，星期五讨论：讨论：答答:利用一个利用一个队列队列结构记录顶点访问顺序，将访问的每个顶结构记录顶点访问顺序，将访问的每个顶点入队，然后，再依次出队，出队时访问其邻接点并将邻接点点入队，然后，再依次出队，出队时访问其邻接点并将邻接点入队。入队。（2 2）如何避免重复访问某个顶点？）如何避免重复访问某个顶点？（1 1）在广度优先遍历中，要求先被访问的顶点其邻接点也被）在广度优先遍历中，要求先被访问的顶点其邻接点也被优先访问，应采用何种方式记录顶点访问顺序？优先访问，应采用何种方式记录顶点访问顺序？答：创建一个答：创建一个一维数组一维数组visited0.n-1visited0.n-1（n n是图中顶点的数目）是图中顶点的数目），用来记录每个顶点是否已经被访问过。，用来记录每个顶点是否已经被访问过。（3 3）广度优先搜索有回退的情况吗？）广度优先搜索有回退的情况吗？11第11页，共25页，编辑于2022年，星期五答：广度优先搜索是一种分层的搜索过程，每向前走一步答：广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。可能访问一批顶点，不像深度优先搜索那样有回退的情况。因此广度优先搜索不是一个递归的过程，其算法也不是递因此广度优先搜索不是一个递归的过程，其算法也不是递归的。归的。void BFSTraverse(Graph G,Status(*Visit)(int v)for(v=0;vG.vexnum;+v)visitedv=FALSE;/初始化访问标志初始化访问标志 InitQueue(Q);/置空的辅助队列置空的辅助队列Q for(v=0;vG.vexnum;+v)if(!visitedv)/v 尚未访问尚未访问 /BFSTraverse12第12页，共25页，编辑于2022年，星期五visitedv=TRUE;Visit(v);/访问访问vEnQueue(Q,v);/v入队列入队列while(!QueueEmpty(Q)DeQueue(Q,u);/队头元素出队并置为队头元素出队并置为u for(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w)if(!visitedw)visitedw=TRUE;Visit(w);EnQueue(Q,w);/访问的顶点访问的顶点w入队列入队列 /if/while13第13页，共25页，编辑于2022年，星期五BFS BFS 算法效率分析算法效率分析算法效率分析算法效率分析:如果使用邻接表来表示图，则如果使用邻接表来表示图，则BFS循环的总时间代价为循环的总时间代价为 d0+d1+dn-1=O(e)，其中的其中的 di 是顶点是顶点 i 的度的度。如果使用邻接矩阵，则如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（要循环检测矩阵中的整整一行（n 个元素），总的时间代个元素），总的时间代价为价为O(n2)。（设图中有设图中有设图中有设图中有 n n 个顶点，个顶点，个顶点，个顶点，e 条边条边条边条边）空间复杂度相同，都是空间复杂度相同，都是O(n)(O(n)(借用堆栈或队列装借用堆栈或队列装n n个顶个顶点）；点）；时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。与搜索路径无关。DFSDFS与与与与BFSBFS之比较：之比较：之比较：之比较：14第14页，共25页，编辑于2022年，星期五生成树：生成树：是一个极小连通子图，它含有图中全部顶点，但只有是一个极小连通子图，它含有图中全部顶点，但只有n-1n-1条边。条边。生成森林：生成森林：由若干棵由若干棵生成树生成树组成，含全部顶点，但构成这组成，含全部顶点，但构成这些树的边是最少的。些树的边是最少的。（对有向或无向图均适用）（对有向或无向图均适用）思考思考1：若对连通图进行遍历，得到的是什么？：若对连通图进行遍历，得到的是什么？一个极小连通子图，即图的一个极小连通子图，即图的生成树生成树！由深度优先搜索得到的生成树，为由深度优先搜索得到的生成树，为深度优先生成树。深度优先生成树。由广度优先搜索得到的生成树，为由广度优先搜索得到的生成树，为广度优先生成树。广度优先生成树。思考思考2：若对非连通图进行遍历，得到的是什么？：若对非连通图进行遍历，得到的是什么？各连通分量的生成树，即图的各连通分量的生成树，即图的生成森林生成森林！7.4 7.4 图的连通性图的连通性1.1.1.1.求无向图的生成树（或生成森林）求无向图的生成树（或生成森林）求无向图的生成树（或生成森林）求无向图的生成树（或生成森林）15第15页，共25页，编辑于2022年，星期五例例1 1：画出下图的生成树。：画出下图的生成树。DFS生生成成树树v0v1v2v4v4v3邻邻接接表表0123413341420v4v3v2v1v0231420v0v2v1v4v3BFS生生成成树树v0v1v3v2v4v0v1v2v4v4v3v0v1v2v4v4v316第16页，共25页，编辑于2022年，星期五DEABCFJLMGHIK例例2 2：画出下图的生成森林（或极小连通子图）：画出下图的生成森林（或极小连通子图）下面选用邻接表方式来求深度优先生成森林下面选用邻接表方式来求深度优先生成森林17第17页，共25页，编辑于2022年，星期五115 5M12L11K10J9I8H7G6F5E4D3C2B1A01201200437810661011126709121911112294710811DFS结果：结果：ABMJLCF DE GHKI18第18页，共25页，编辑于2022年，星期五DEGHIK子图子图1：子图子图2：子图子图3：AFCMLBJDEGHIKAFCMLBJ生生成成森森林林注：注：图的生成树（生成森林）不唯一！图的生成树（生成森林）不唯一！19第19页，共25页，编辑于2022年，星期五2.2.求无向网的最小生成树求无向网的最小生成树目标：目标：在网络的多个生成树中，寻找一个各边权值之和在网络的多个生成树中，寻找一个各边权值之和最小的生成树。即最小的生成树。即在在 e 条带权的边中选取条带权的边中选取 n-1 条边（不条边（不构成回路），使构成回路），使“权值之和权值之和”为最小。为最小。欲在欲在n n个城市间建立通信网，则个城市间建立通信网，则n n个城市应铺个城市应铺n-1n-1条线路；但因条线路；但因为每条线路都会有对应的经济成本，而为每条线路都会有对应的经济成本，而n n个城市可能有个城市可能有n(n-n(n-1)/2 1)/2 条线路，那么，条线路，那么，如何选择如何选择n n1 1条线路使总费用最少？条线路使总费用最少？典型用途：典型用途：最小生成树最小生成树（MSTMST）的的 性质如下性质如下：V V是顶点集，是顶点集，U U是是V V的一个非空子集，若的一个非空子集，若(u(u0 0,v,v0 0)是一条是一条最最小权值的边小权值的边，其中，其中u u0 0 U U，v v0 0 V-UV-U；则：；则：(u(u0 0,v,v0 0)必在最必在最小生成树上小生成树上。20第20页，共25页，编辑于2022年，星期五求求MST有多种算法，但最常用的是以下两种：有多种算法，但最常用的是以下两种：Prim（普里姆普里姆）算法）算法 Kruskal（克鲁斯卡尔克鲁斯卡尔）算法）算法PrimPrim算法特点算法特点:顶点归并顶点归并，与边数无关，适于稠密网。，与边数无关，适于稠密网。KruskalKruskal算法特点：算法特点：边归并边归并，适于求稀疏网。，适于求稀疏网。对边操作对顶点操作普里姆算法的基本思想普里姆算法的基本思想:在生成树的构造过程中，图中在生成树的构造过程中，图中 n n 个顶点分属两个集合：已落个顶点分属两个集合：已落在生成树上的顶点集在生成树上的顶点集 U U 和尚未落在生成树上的顶点集和尚未落在生成树上的顶点集V-U V-U，则应在所有连通则应在所有连通U U中顶点和中顶点和V-UV-U中顶点的边中选取权值最小的中顶点的边中选取权值最小的边。如图所示：边。如图所示：21第21页，共25页，编辑于2022年，星期五abcdegf例如例如:195141827168213ae12dcbgf7148531621所得生成树权值和所得生成树权值和=14+8+3+5+16+21=67集集合合U集合集合V-Uu0v022第22页，共25页，编辑于2022年，星期五方法：方法：设置一个辅助数组，对当前设置一个辅助数组，对当前VU集中的每个集中的每个顶点，记录和顶点集顶点，记录和顶点集U中顶点相连接的代价最小的边。中顶点相连接的代价最小的边。对每个属于对每个属于V-U的顶点的顶点vi，在辅助数组中存在一个相应在辅助数组中存在一个相应的分量的分量closedgei-1，它包含两个域，其中它包含两个域，其中lowcost存储该存储该边上的权。显然，边上的权。显然，closedgei-1.lowcostMincost(u,vi)|uU存储方式：存储方式：struct VertexType adjvex;/U集中的顶点序号集中的顶点序号 VRType lowcost;/边的权值边的权值 closedgeMAX_VERTEX_NUM;23第23页，共25页，编辑于2022年，星期五abcdegf195141827168213ae12dcb7aaa19141814例如例如:e12ee8168d3dd7213c55 19 14 1819 5 7 12 5 3 7 3 8 21 14 12 8 16 21 2718 16 27 （a b c d e f g)PrimPrim算法的时间效率算法的时间效率O O（n n2 2）（a b c d e f g)24第24页，共25页，编辑于2022年，星期五具体做法具体做法:先构造一个只含先构造一个只含 n 个顶点的子图个顶点的子图 SG，然后从权值，然后从权值最小的边开始，若它的添加不使最小的边开始，若它的添加不使SG 中产生回路，则在中产生回路，则在 SG 上上加上这条边，如此重复，直至加上加上这条边，如此重复，直至加上 n-1 条边为止。条边为止。考虑问题的出发点考虑问题的出发点:为使生成树上边的权值之和达到最小，为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。则应使生成树中每一条边的权值尽可能地小。克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想：1 14 46 65 52 23 31 15 56 65 55 54 46 63 36 62 21 15 54 43 32 21 13 35 52 24 46 6KruskalKruskal算法的时间效率算法的时间效率O O（elogelog2 2e e）25第25页，共25页，编辑于2022年，星期五