第九章-图的遍历算法课件.ppt

1、第三部分第三部分 最先割技术最先割技术 第九章第九章 图的遍历图的遍历 第九章第九章 图的遍历图的遍历 9 91 1 引言引言 9 92 2 深度优先搜索深度优先搜索 9 93 3 深度优先搜索的应用深度优先搜索的应用 9 94 4 广度优先搜索广度优先搜索 9 95 5 广度优先搜索的应用广度优先搜索的应用 在一些诸如找出最短路径和最小生成树的图在一些诸如找出最短路径和最小生成树的图的算法中，用由它们相应的算法顺序访问顶点的算法中，用由它们相应的算法顺序访问顶点和边。然而，在一些其他算法中，访问顶点的和边。然而，在一些其他算法中，访问顶点的顺序是不重要的，重要的是，不管输入的图如顺序是不重要

2、的，重要的是，不管输入的图如何，用一种系统的顺序来访问顶点。在本章中，何，用一种系统的顺序来访问顶点。在本章中，我们讨论图遍历的两种方法：深度优先搜索和我们讨论图遍历的两种方法：深度优先搜索和广度优先搜索。广度优先搜索。9.1 引引 言言 设设G=(V,E)是一个是一个有向或无向图有向或无向图，G的深度优的深度优先搜索运作如下：先搜索运作如下：1、初始化所有的顶点访问标志为未访问；、初始化所有的顶点访问标志为未访问；2、任意选择一个起始顶点，比如说、任意选择一个起始顶点，比如说sV，并，并标上已访问。标上已访问。3、从、从s的邻接顶点中选择任意一个顶点的邻接顶点中选择任意一个顶点w，访，访问该

3、顶点，同时将其标志为被访问。问该顶点，同时将其标志为被访问。9.2 深度优先搜索深度优先搜索 3、将访问指针移至将访问指针移至w结点，将其标志为被结点，将其标志为被访问，然后从访问，然后从w的临接结点中选择一个未被访的临接结点中选择一个未被访问的结点，向前继续访问；问的结点，向前继续访问；4、在访问过程中，按照上述的深度优先的方、在访问过程中，按照上述的深度优先的方式向前推进，一旦发现某一个顶点式向前推进，一旦发现某一个顶点X的所有邻的所有邻接点都被标志为已访问，访问指针回退至上一接点都被标志为已访问，访问指针回退至上一层，继续访问该层没有被访问的其他的子节点。层，继续访问该层没有被访问的其他

4、的子节点。5、如此往复，直至回退到根节点为止。、如此往复，直至回退到根节点为止。算法算法9.1 DFSInput:有向或无向图有向或无向图G=(V,E)。Output:在相应的深度优先搜索树中对顶点的前序在相应的深度优先搜索树中对顶点的前序和后序。和后序。1.predfn 0;postdfn 0 2.For 每个顶点每个顶点vV 3.标记标记v未访问未访问 /初始化访问标志初始化访问标志 4.End for 5.For 每个顶点每个顶点vV 6.If v未访问未访问 then dfs(v)/调用访问调用访问 7.End for过程过程 dfs(v)/递归访问递归访问 1.标记标记v已访问已访问

5、 2.predfn predfn+1/进来访问，是前序号进来访问，是前序号 3.For 每条边每条边(v,w)E 4.If w标记为未访问标记为未访问 then dfs(w)5.End for 6.postdfn postdfn+1/结点被访问完毕，退结点被访问完毕，退回时访问该语句，即后序号回时访问该语句，即后序号 算法生成结构：算法生成结构：1、树（全部顶点相连，能够一次到达）；、树（全部顶点相连，能够一次到达）；2、森林（顶点不相连，不能够一次都到达）。、森林（顶点不相连，不能够一次都到达）。1、无向图的情况分析、无向图的情况分析设设G=(V,E)是无向图，作为遍历的结果，是无向图，作为

6、遍历的结果，G的边的边分成一下两种类型。分成一下两种类型。树边树边：深度优先搜索树中的边，如果在搜索边：深度优先搜索树中的边，如果在搜索边(v,w)时，时，w是首次被访问，则边是首次被访问，则边(v,w)是树边。是树边。回边回边：所有其它的边。：所有其它的边。例例9.1。e ed dc cb bf fa ah hg gi ij ja ab bc cd de ef fg gh hi ij j1,101,102,92,93,33,34,24,25,15,16,86,87,77,78,68,69,59,510,410,42、有向图的情况、有向图的情况 有向图中的深度优先搜索导致结果：有向图中的深度优

7、先搜索导致结果：一个或多个一个或多个(有向有向)生成树，生成树，树的多少取决于树的多少取决于初始点初始点。（1）选择某起始点）选择某起始点v，深度优先搜索一棵树，深度优先搜索一棵树，它由从它由从v出发所有可到达的顶点组成。出发所有可到达的顶点组成。（2）没有遍历完所有的顶点，选择另一个顶）没有遍历完所有的顶点，选择另一个顶点点w继续（继续（未访问过顶点），构建一颗从未访问过顶点），构建一颗从w可到达可到达的所有未访问顶点组成的树，这个过程继续下去的所有未访问顶点组成的树，这个过程继续下去直到所有的顶点都被访问过。直到所有的顶点都被访问过。（3）重复上述过程，直至所有顶点被访问完）重复上述过程，

8、直至所有顶点被访问完毕。毕。G的边分成的边分成4种类型：种类型：1、树边、树边：深度优先搜索树中的边。如果在搜索边：深度优先搜索树中的边。如果在搜索边(v,w)时，时，w是第一次被访问是第一次被访问，则，则(v,w)是树边。是树边。2、回边、回边：在迄今为止构建的深度优先搜索树中，：在迄今为止构建的深度优先搜索树中，w是是v的祖先，并且当搜索的祖先，并且当搜索(v,w)时顶点时顶点w已被标上已被标上已访问，这样形成的边已访问，这样形成的边(v,w)是回边。是回边。3、前向边、前向边：在迄今为止构建的深度优先搜索树中，：在迄今为止构建的深度优先搜索树中，w是是v的后裔，并且当搜索的后裔，并且当搜

9、索(v,w)时顶点时顶点w被标上已被标上已访问，这种形式的边访问，这种形式的边(v,w)是前向边。是前向边。3、横跨边、横跨边：所有其它的边。：所有其它的边。见例见例9.2。c cd de eb ba af fa ab be ef fc cd da af fe eb bc cd d1,41,42,32,33,13,14,24,25,65,66,56,51,41,42,22,23,13,14,34,35,65,66,56,5 (1)顶点顶点v被访问标记为访问的过程，每一个顶被访问标记为访问的过程，每一个顶点的调用耗费是点的调用耗费是(1)。一共需要。一共需要n个顶点，所以该个顶点，所以该过程的总

10、耗费是过程的总耗费是(n)。（2）算法的步骤）算法的步骤1和步骤和步骤3分别耗费分别耗费(1)和和(n)时间。时间。/初始化序列号、访问标志初始化序列号、访问标志（3）步骤）步骤6测试一个顶点是否已标记要耗费测试一个顶点是否已标记要耗费(n)。（注意：测试方法是要依次搜索该点的邻接（注意：测试方法是要依次搜索该点的邻接点，看是否从某个点访问过它，所以是点，看是否从某个点访问过它，所以是(n)）9.2.1 深度优先搜索的时间复杂性深度优先搜索的时间复杂性 （4 4）测试顶点）测试顶点w是否是否标记为未访问，这一步标记为未访问，这一步的执行次数等于的执行次数等于顶点顶点v v的邻接点数的邻接点数。

11、这一步执行的总次数，在有向图的情况下等这一步执行的总次数，在有向图的情况下等于它的边数，在无向图的情况下是边数的两倍。于它的边数，在无向图的情况下是边数的两倍。于是，不论是有向图还是无向图，这一步的于是，不论是有向图还是无向图，这一步的耗费是耗费是(m)，（5）算法的总运行时间是：）算法的总运行时间是：(m+n)。如果图。如果图是连通的或有是连通的或有mn,则运行时间简单地为则运行时间简单地为(m)。但。但是必须强调的是，图假设是用邻接表表示的。是必须强调的是，图假设是用邻接表表示的。9.3 深度优先搜索的应用深度优先搜索的应用 深度优先搜索在图和几何算法中用得很普遍。深度优先搜索在图和几何算

12、法中用得很普遍。在本节中，我们列举它的一些重要应用。在本节中，我们列举它的一些重要应用。设设G=(V,E)是一个有是一个有n个顶点和个顶点和m条边的有向或条边的有向或无向图。为了测试无向图。为了测试G是否至少有一个回路，我们是否至少有一个回路，我们对对G用深度优先搜索，用深度优先搜索，如果在搜索过程中探测到如果在搜索过程中探测到一条回边，那么一条回边，那么G是有回路的，否则是有回路的，否则G是无回路的。是无回路的。注意注意G可能不连通，如果可能不连通，如果G是连通无向图，是连通无向图，那么不需要对图进行遍历，那么不需要对图进行遍历，因为因为G是无回路的当是无回路的当且仅当它是一棵树，则当且仅当

13、且仅当它是一棵树，则当且仅当m=n-1。9.3.1 图的无回路性图的无回路性 给出一个有向无回路图给出一个有向无回路图(dag)G=(V,E)，拓扑排，拓扑排序问题是找出图顶点的一个线性序列，序问题是找出图顶点的一个线性序列，使得如果使得如果(v,w)E，那么在这个序中，那么在这个序中v在在w前出现。前出现。例如，在图例如，在图9.3(a)中所示的有向无回路图中，中所示的有向无回路图中，顶点的一个可能的拓扑排序是顶点的一个可能的拓扑排序是a,b,d,c,e,f,g。我们将假设在这种有向无回路图中有一个入度我们将假设在这种有向无回路图中有一个入度是是0的唯一的顶点的唯一的顶点s，如果不是的话，我

14、们可以简，如果不是的话，我们可以简单地添一个新的顶点单地添一个新的顶点s，然后让，然后让s到所有入度为到所有入度为0的的点加上边。点加上边。9.3.2 拓扑排序拓扑排序a ab bd df fc ce eg gs s 接下来，我们从顶点接下来，我们从顶点s起，简单地对图起，简单地对图G执行执行深度优先搜索。深度优先搜索。当遍历完成时，计数器当遍历完成时，计数器postdfn定义了一个在定义了一个在有向无回路图中顶点的反扑排序，于是，为了得有向无回路图中顶点的反扑排序，于是，为了得到这个拓扑序，可以在算法到这个拓扑序，可以在算法DFS中在计数器中在计数器postdfn刚好被增加后，加上一个输出步

15、，把输出刚好被增加后，加上一个输出步，把输出结果翻转过来就是我们需要的拓扑序。结果翻转过来就是我们需要的拓扑序。关节点关节点:在多于两个顶点的无向图在多于两个顶点的无向图G中，存在一个顶点中，存在一个顶点v，如果有不同于如果有不同于v的两个顶点的两个顶点u和和w，在，在u和和w间的间的任何路径都必定经过顶点任何路径都必定经过顶点v。这样，如果这样，如果G是连通的，移去是连通的，移去v和与它关联的边，和与它关联的边，将产生将产生G的非连通子图（森林）。一个图如果是的非连通子图（森林）。一个图如果是连通的并且没有关节点则称为是连通的并且没有关节点则称为是双连通双连通的。的。9.3.3 寻找图的关节

16、点寻找图的关节点由深度优先生成树的特性可以得到如下结论：由深度优先生成树的特性可以得到如下结论：1、根是一个关节点根是一个关节点当且仅当在深度优先搜索树中，当且仅当在深度优先搜索树中，它有两个或更多的儿子；它有两个或更多的儿子；原因：图中不存在连接不同子树顶点的边，删掉根原因：图中不存在连接不同子树顶点的边，删掉根结点后，生成树就变成了森林。结点后，生成树就变成了森林。2、根以外的其他结点根以外的其他结点V，如果其某棵子树的根和，如果其某棵子树的根和子树中的其他结点均没有指向该结点子树中的其他结点均没有指向该结点v的祖先的的祖先的回边。回边。或者：或者：根以外的顶点根以外的顶点v是一个关节点当

17、且仅当是一个关节点当且仅当v有有一个儿子一个儿子w，使得，使得(w)(v)。为了找出关节点的集合，在图为了找出关节点的集合，在图G上执行一个上执行一个深度优先搜索遍历。深度优先搜索遍历。在遍历的过程中，对每个顶点在遍历的过程中，对每个顶点v保持两个标保持两个标号：号：(v)和和(v)，(v)只是深度优先搜索算法中的只是深度优先搜索算法中的predfn，每次调用深度优先搜索过程，就加，每次调用深度优先搜索过程，就加1，(v)初始化为初始化为(v)，但在后来的遍历过程，但在后来的遍历过程中可以中可以改变。改变。对于每一个访问的顶点，令对于每一个访问的顶点，令(v)是下面几个中的是下面几个中的最小值

18、。最小值。(v)；/叶子结点叶子结点(u)，对于每个顶点，对于每个顶点u,(v,u)是回边；是回边；(w)，在深度优先搜索树中的每条边，在深度优先搜索树中的每条边(v,w)。上述(v)值的变化是：一旦某个点出现回边，值的变化是：一旦某个点出现回边，则该结点的则该结点的(v)值必然变小为其祖先结点值必然变小为其祖先结点k的的()值。值。如果某个结点的如果某个结点的值大于其值大于其值，则肯定有一值，则肯定有一个子结点，必然是关节点；个子结点，必然是关节点；如果该值小于其如果该值小于其值，肯定是有回边了。值，肯定是有回边了。如果等于如果等于值，则肯定是没有孩子了。值，则肯定是没有孩子了。使用这个值的

19、目的就是在回访结点的过程中，使用这个值的目的就是在回访结点的过程中，通过判断结点的通过判断结点的与与值的关系以得到该结点是什值的关系以得到该结点是什么结点么结点 算法算法9.2 ARTICPOINTSINPUT:连通无向图连通无向图G=(V,E)。OUTPUT:包含包含G的所有可能关节点的数组的所有可能关节点的数组A1n。1.设设s为起始顶点为起始顶点 2.for 每个顶点每个顶点vV 3.标记标记v未访问未访问 4.end for /初始化全部结点为没有访问初始化全部结点为没有访问 5.predfn 0;count 0;rootdegree 0 6.dfs(s)/从初始结点开始访问从初始结点

20、开始访问过程过程 dfs(v)1.标记标记v已访问；已访问；artpoint false;/关节点标记关节点标记 predfn predfn+1/标记序号标记序号 2.(v)predfn;(v)predfn /初始化访问序号初始化访问序号 3.For 每条边每条边(v,w)E 4.If(v,w)为树边为树边 then 5.dfs(w)/深入开始访问后续结点深入开始访问后续结点 6.If v=s then /树根结点树根结点 7.rootdegree rootdegree+1 8.If rootdegree=2 then artpoint true /根节点至少根节点至少存在两个子树，是关节结点

21、存在两个子树，是关节结点 9.Else 10.(v)min(v),(w)11.If(w)(v)then artpoint true /有孩子就标记有孩子就标记为关节结点为关节结点 12.Endif 13.Else if(v,w)是回边是回边 then /v!=s (v)min(v),(w)14.Else do nothing w是是v的父亲的父亲 15.End if 16.End for 17.If artpoint then 18.count count+1 19.Acount v 20.End if （1）首先，算法执行必要的初始化，特别首先，算法执行必要的初始化，特别地，地，count是

22、关节点的个数，是关节点的个数，rootdegree是深度优是深度优先搜索树根的度，这在后来决定根是否是关节点先搜索树根的度，这在后来决定根是否是关节点时是需要的。时是需要的。（2）接着深度优先搜索从根开始着手，对于）接着深度优先搜索从根开始着手，对于每一个访问的顶点每一个访问的顶点v，(v)和和(v)用用predfn来初始来初始化。化。（3）在搜索从某顶点在搜索从某顶点w退回到退回到v时时，要做两件，要做两件事，首先，如果发现事，首先，如果发现(w)比比(v)小，小，(v)被设置为被设置为(w)，其次，如果，其次，如果(w)(v)，那么这就指出，那么这就指出v是是一个关节点，一个关节点，因为从

23、因为从w到到v的祖先顶点必须经过的祖先顶点必须经过v。这说明在图这说明在图9.4种，可以看到，从以种，可以看到，从以w为根的子为根的子树到树到u的任何路径必定包括的任何路径必定包括v，因此，因此v是一个关节点。是一个关节点。以以w为根的子树包含一个或多个连通分支。在这为根的子树包含一个或多个连通分支。在这个图中，根个图中，根u是关节点，因为它的度大于是关节点，因为它的度大于1。见例见例9.3。e ed dc cb bf fa ah hg gi ij ja ab bc cd de ef fg gh hi ij j1,11,12,12,13,33,34,34,35,35,36,16,17,17,1

24、8,88,89,89,810,810,8（1）初始化各个顶点；（2）从a-e开始搜索，一直到e均是正常搜索，各个数值依次递增增长；（3）搜索到e时，找到一个回边(e,c)，则e的(e)=minac=3；ae=5,c=3=3；（4）回退至）回退至d点时，该点的点时，该点的d=3;(原来是原来是4);(5)回退到回退到c点，点，c=3，由于，由于d=ac，所以，所以该结点是关节点。该结点是关节点。(6)回退到回退到b结点，结点，c=ab，所以，所以b也是一个也是一个关节点。关节点。此时，发现此时，发现b结点还有一个分支，继续搜索该分结点还有一个分支，继续搜索该分支。支。（1）探测到（j,h）是一个

25、回边，所以将 j=ah=8；（2）回到）回到i点，该点的点，该点的i也被改为也被改为8；（3）同理，对于）同理，对于h点来讲，其点来讲，其h也被置为也被置为8；此时，由于此时，由于iah,所以所以h是关节点；是关节点；（4）回退到）回退到g点点,同样存在同样存在hag，所以该点，所以该点也是关节点；检测到该点存在回路，所以将其也是关节点；检测到该点存在回路，所以将其g值置为其祖先结点的值值置为其祖先结点的值=1；（5）f b也被置为也被置为1,搜索回到搜索回到a结点，因为结点，因为a结点只有一个分支孩子，所以结点只有一个分支孩子，所以a不是关节点不是关节点 e ed dc cb bf fa a

26、h hg gi ij ja ab bc cd de ef fg gh hi ij j1,11,12,12,13,33,34,34,35,35,36,16,17,17,18,78,79,79,710,710,7 给出一个有向图给出一个有向图G=(V,E)，G中的强连通分支是中的强连通分支是它它顶点的极大集顶点的极大集，在该集中，在该集中，每一对顶点间都存在每一对顶点间都存在一条路径一条路径。下面的算下面的算STRONGCONNECTCOMP用深度优用深度优先搜索来确定在有向图中的所有的强连通分支。先搜索来确定在有向图中的所有的强连通分支。9.3.4 强连通分支强连通分支算法算法9.3 STRON

27、GCONNECTCOMPINPUT:有向图有向图G=(V,E)OUTPUT:G中的强连通分支中的强连通分支 1.在图在图G上执行深度优先搜索，对每一个顶点赋上执行深度优先搜索，对每一个顶点赋给相应的给相应的postdfn值值。2.颠倒图颠倒图G中边的方向，构成一个新的图中边的方向，构成一个新的图 3.从具有最大从具有最大postdfn数值的顶点开始，在数值的顶点开始，在 上执行深度优先搜索，如果深度优先搜索不能上执行深度优先搜索，如果深度优先搜索不能到达所有的顶点，则在余下的顶点中找出一个到达所有的顶点，则在余下的顶点中找出一个postdfn数值最大的顶点，开始下一次深度优先搜数值最大的顶点，

28、开始下一次深度优先搜索。索。4.在最终得到的森林中的每一棵树对应一个强连在最终得到的森林中的每一棵树对应一个强连通分支。通分支。见例见例9.4。GGc cd de eb ba af f原图原图a ab be ef fc cd da af fe eb bc cd d1,41,42,32,33,13,14,24,25,65,66,56,51,41,42,22,23,13,14,34,35,65,66,56,5深度优先搜索结果图深度优先搜索结果图c cd de ea af fb b将原图翻转图将原图翻转图a ad de ec cb bf f最后的结果最后的结果 1、在广度优先搜索中，当访问了一个顶点

29、、在广度优先搜索中，当访问了一个顶点v后，后，接下来访问邻接于接下来访问邻接于v的所有顶点，产生出来的树称的所有顶点，产生出来的树称为广度优先搜索树。为广度优先搜索树。2、这种遍历的方法可以通过用一个、这种遍历的方法可以通过用一个队列存储队列存储没没有检查过的顶点来实现有检查过的顶点来实现（先进先出）（先进先出）。3、广度优先的算法、广度优先的算法BFS能够用到有向和无向图中。能够用到有向和无向图中。初始的时候，所有的顶点都标上未访问，计数器初始的时候，所有的顶点都标上未访问，计数器bfn初始为初始为0，它表示顶点从队列中移出的序。在无向，它表示顶点从队列中移出的序。在无向图的情况下，一条边或

30、者是树边或者是横跨边；如图的情况下，一条边或者是树边或者是横跨边；如果图是有向的，那么边可以是树边、回边或横跨边，果图是有向的，那么边可以是树边、回边或横跨边，不存在前向边。不存在前向边。9.4 广度优先搜索广度优先搜索算法算法9.1 BFSInput:有向或无向图有向或无向图G=(V,E)。Output:广度优先搜索次序中顶点的编号。广度优先搜索次序中顶点的编号。1.bfn 0 2.For 每个顶点每个顶点vV 3.标记标记v未访问未访问 4.End for 5.For 每个顶点每个顶点vV 6.If v未访问未访问 then bfs(v)7.End for过程过程 bfs(v)1.Q v

31、/被访问顶点进队列被访问顶点进队列 2.标记标记v已访问已访问 3.While Q 4.v Pop(Q)/弹出头顶点弹出头顶点 5.bfn bfn+1 6.For 每条边每条边(v,w)E/保证广度优先保证广度优先 7.If w标记未为访问标记未为访问 then 8.Push(w,Q)/压入队列压入队列 9.标记标记w已访问已访问 10.end if 11.End for 12.End whilea ab bg gc cd de ef fh hi ij j1 12 23 34 45 56 67 78 89 91010图图9.19.1的广度优先搜索的广度优先搜索时间复杂性时间复杂性 广度优先搜索

32、应用在具有广度优先搜索应用在具有n个顶点个顶点m条边的条边的图图(包括有向图和无向图包括有向图和无向图)上时，它的时间复杂性上时，它的时间复杂性是和深度优先搜索一样的，为是和深度优先搜索一样的，为(m+n)。如果图是连通的或者如果图是连通的或者mn，那么时间复杂性，那么时间复杂性可简化为可简化为(m)。设设G=(V,E)是连通无向图，是连通无向图，s是是V中的一个顶点，中的一个顶点，当把算法当把算法BFS用到用到G上并以上并以s作为起始点时，产生作为起始点时，产生的广度优先搜索树中从的广度优先搜索树中从s到其他任意顶点的路径有到其他任意顶点的路径有最少的边数。最少的边数。假如我们要找出从假如我

33、们要找出从s到其他每一顶点的距离，到其他每一顶点的距离，这里从这里从s到一个顶点到一个顶点v的距离定义为：的距离定义为：从从s到到v的任意路径的最少边数。的任意路径的最少边数。于是上面的问题可以很容易做到，我们于是上面的问题可以很容易做到，我们只要在只要在每个顶点压入队列前，标上它的距离就可以了。每个顶点压入队列前，标上它的距离就可以了。这样，起始点将标上这样，起始点将标上0，它的邻接点是，它的邻接点是1，以此类，以此类推。推。9.5 广度优先搜索的应用广度优先搜索的应用 很明显，每个顶点的标号是它到起始点的最短很明显，每个顶点的标号是它到起始点的最短距离。距离。例如在图例如在图9.7中，顶点中，顶点a将被标上将被标上0，顶点，顶点b和和g标上标上1，顶点，顶点c,f和和h标上标上2，最后，顶点，最后，顶点d,e,i和和j标上标上3。注意，这里的顶点编号方式不同于算法中广度。注意，这里的顶点编号方式不同于算法中广度优先的编号方式。优先的编号方式。谢谢 谢谢