第九章 图的遍历算法

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的邻接顶点中选择任意一个顶点的邻接顶点中选择任

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

4、的子节点。层，继续访问该层没有被访问的其他的子节点。 5、如此往复，直至回退到根节点为止。、如此往复，直至回退到根节点为止。 算法算法9.1 DFS Input: 有向或无向图有向或无向图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

5、for 过程过程 dfs(v) /递归访问递归访问 1. 标记标记v已访问已访问 2. predfn predfn+1 /进来访问，是前序号进来访问，是前序号 3. For 每条边每条边(v,w)E 4. If w标记为未访问标记为未访问 then dfs(w) 5. End for 6. postdfn postdfn+1 /结点被访问完毕，退结点被访问完毕，退 回时访问该语句，即后序号回时访问该语句，即后序号 算法生成结构：算法生成结构： 1、树（全部顶点相连，能够一次到达）；、树（全部顶点相连，能够一次到达）； 2、森林（顶点不相连，不能够一次都到达）。、森林（顶点不相连，不能够一次都到

6、达）。 1、无向图的情况分析、无向图的情况分析 设设G=(V,E)是无向图，作为遍历的结果，是无向图，作为遍历的结果，G的边的边 分成一下两种类型。分成一下两种类型。 树边树边：深度优先搜索树中的边，如果在搜索边：深度优先搜索树中的边，如果在搜索边 (v,w)时，时，w是首次被访问，则边是首次被访问，则边(v,w)是树边。是树边。 回边回边：所有其它的边。：所有其它的边。 例例9.1。 e e d d c c b b f f a a h h g g i i j j a a b b c c d d e e f f g g h h i i j j 1,101,10 2,92,9 3,33,3 4,

7、24,2 5,15,1 6,86,8 7,77,7 8,68,6 9,59,5 10,410,4 2、有向图的情况、有向图的情况 有向图中的深度优先搜索导致结果：有向图中的深度优先搜索导致结果： 一个或多个一个或多个(有向有向)生成树，生成树，树的多少取决于树的多少取决于 初始点初始点。 （1）选择某起始点）选择某起始点v，深度优先搜索一棵树，深度优先搜索一棵树， 它由从它由从v出发所有可到达的顶点组成。出发所有可到达的顶点组成。 （2）没有遍历完所有的顶点，选择另一个顶）没有遍历完所有的顶点，选择另一个顶 点点w继续（继续（未访问过顶点），构建一颗从未访问过顶点），构建一颗从w可到达可到达

8、的所有未访问顶点组成的树，这个过程继续下去的所有未访问顶点组成的树，这个过程继续下去 直到所有的顶点都被访问过。直到所有的顶点都被访问过。 （3）重复上述过程，直至所有顶点被访问完）重复上述过程，直至所有顶点被访问完 毕。毕。 G的边分成的边分成4种类型：种类型： 1、树边、树边：深度优先搜索树中的边。如果在搜索边：深度优先搜索树中的边。如果在搜索边 (v,w)时，时，w是第一次被访问是第一次被访问，则，则(v,w)是树边。是树边。 2、回边、回边：在迄今为止构建的深度优先搜索树中，：在迄今为止构建的深度优先搜索树中， w是是v的祖先，并且当搜索的祖先，并且当搜索(v,w)时顶点时顶点w已被标

9、上已被标上 已访问，这样形成的边已访问，这样形成的边(v,w)是回边。是回边。 3、前向边、前向边：在迄今为止构建的深度优先搜索树中，：在迄今为止构建的深度优先搜索树中， w是是v的后裔，并且当搜索的后裔，并且当搜索(v,w)时顶点时顶点w被标上已被标上已 访问，这种形式的边访问，这种形式的边(v,w)是前向边。是前向边。 3、横跨边、横跨边：所有其它的边。：所有其它的边。 见例见例9.2。 c c d de e b b a a f f a a b b e e f f c c d d a a f f e e b b c c d d 1,41,4 2,32,3 3,13,1 4,24,2 5,6

10、5,6 6,56,5 1,41,4 2,22,2 3,13,1 4,34,3 5,65,6 6,56,5 (1)顶点顶点v被访问标记为访问的过程，每一个顶被访问标记为访问的过程，每一个顶 点的调用耗费是点的调用耗费是 (1)。一共需要。一共需要n个顶点，所以该个顶点，所以该 过程的总耗费是过程的总耗费是 (n)。 （2）算法的步骤）算法的步骤1和步骤和步骤3分别耗费分别耗费 (1) 和和 (n) 时间。时间。/初始化序列号、访问标志初始化序列号、访问标志 （3）步骤）步骤6测试一个顶点是否已标记要耗费测试一个顶点是否已标记要耗费 (n)。 （注意：测试方法是要依次搜索该点的邻接（注意：测试方法

11、是要依次搜索该点的邻接 点，看是否从某个点访问过它，所以是点，看是否从某个点访问过它，所以是 (n)） 9.2.1 深度优先搜索的时间复杂性深度优先搜索的时间复杂性 （4 4）测试顶点）测试顶点w是否是否标记为未访问，这一步标记为未访问，这一步 的执行次数等于的执行次数等于顶点顶点v v的邻接点数的邻接点数。 这一步执行的总次数，在有向图的情况下等这一步执行的总次数，在有向图的情况下等 于它的边数，在无向图的情况下是边数的两倍。于它的边数，在无向图的情况下是边数的两倍。 于是，不论是有向图还是无向图，这一步的于是，不论是有向图还是无向图，这一步的 耗费是耗费是 (m)， （5）算法的总运行时间

12、是：）算法的总运行时间是： (m+n)。如果图。如果图 是连通的或有是连通的或有mn,则运行时间简单地为则运行时间简单地为 (m)。但。但 是必须强调的是，图假设是用邻接表表示的。是必须强调的是，图假设是用邻接表表示的。 9.3 深度优先搜索的应用深度优先搜索的应用 深度优先搜索在图和几何算法中用得很普遍。深度优先搜索在图和几何算法中用得很普遍。 在本节中，我们列举它的一些重要应用。在本节中，我们列举它的一些重要应用。 设设G=(V,E)是一个有是一个有n个顶点和个顶点和m条边的有向或条边的有向或 无向图。为了测试无向图。为了测试G是否至少有一个回路，我们是否至少有一个回路，我们 对对G用深度

13、优先搜索，用深度优先搜索，如果在搜索过程中探测到如果在搜索过程中探测到 一条回边，那么一条回边，那么G是有回路的，否则是有回路的，否则G是无回路的。是无回路的。 注意注意G可能不连通，如果可能不连通，如果G是连通无向图，是连通无向图， 那么不需要对图进行遍历，那么不需要对图进行遍历，因为因为G是无回路的当是无回路的当 且仅当它是一棵树，则当且仅当且仅当它是一棵树，则当且仅当m=n-1。 9.3.1 图的无回路性图的无回路性 给出一个有向无回路图给出一个有向无回路图(dag)G=(V,E)，拓扑排，拓扑排 序问题是找出图顶点的一个线性序列，序问题是找出图顶点的一个线性序列，使得如果使得如果 (v

14、,w)E，那么在这个序中，那么在这个序中v在在w前出现。前出现。 例如，在图例如，在图9.3(a)中所示的有向无回路图中，中所示的有向无回路图中， 顶点的一个可能的拓扑排序是顶点的一个可能的拓扑排序是a,b,d,c,e, f,g。 我们将假设在这种有向无回路图中有一个入度我们将假设在这种有向无回路图中有一个入度 是是0的唯一的顶点的唯一的顶点s，如果不是的话，我们可以简，如果不是的话，我们可以简 单地添一个新的顶点单地添一个新的顶点s，然后让，然后让s到所有入度为到所有入度为0的的 点加上边。点加上边。 9.3.2 拓扑排序拓扑排序 a a b b d d f f c c e e g g s

15、s 接下来，我们从顶点接下来，我们从顶点s起，简单地对图起，简单地对图G执行执行 深度优先搜索。深度优先搜索。 当遍历完成时，计数器当遍历完成时，计数器postdfn定义了一个在定义了一个在 有向无回路图中顶点的反扑排序，于是，为了得有向无回路图中顶点的反扑排序，于是，为了得 到这个拓扑序，可以在算法到这个拓扑序，可以在算法DFS中在计数器中在计数器 postdfn刚好被增加后，加上一个输出步，把输出刚好被增加后，加上一个输出步，把输出 结果翻转过来就是我们需要的拓扑序。结果翻转过来就是我们需要的拓扑序。 关节点关节点: 在多于两个顶点的无向图在多于两个顶点的无向图G中，存在一个顶点中，存在一

16、个顶点 v，如果有不同于如果有不同于v的两个顶点的两个顶点u和和w，在，在u和和w间的间的 任何路径都必定经过顶点任何路径都必定经过顶点v。 这样，如果这样，如果G是连通的，移去是连通的，移去v和与它关联的边，和与它关联的边， 将产生将产生G的非连通子图（森林）。一个图如果是的非连通子图（森林）。一个图如果是 连通的并且没有关节点则称为是连通的并且没有关节点则称为是双连通双连通的。的。 9.3.3 寻找图的关节点寻找图的关节点 由深度优先生成树的特性可以得到如下结论：由深度优先生成树的特性可以得到如下结论： 1、 根是一个关节点根是一个关节点当且仅当在深度优先搜索树中，当且仅当在深度优先搜索树

17、中， 它有两个或更多的儿子；它有两个或更多的儿子； 原因：图中不存在连接不同子树顶点的边，删掉根原因：图中不存在连接不同子树顶点的边，删掉根 结点后，生成树就变成了森林。结点后，生成树就变成了森林。 2、 根以外的其他结点根以外的其他结点V，如果其某棵子树的根和，如果其某棵子树的根和 子树中的其他结点均没有指向该结点子树中的其他结点均没有指向该结点v的祖先的的祖先的 回边。回边。 或者：或者：根以外的顶点根以外的顶点v是一个关节点当且仅当是一个关节点当且仅当v有有 一个儿子一个儿子w，使得，使得(w)(v)。 为了找出关节点的集合，在图为了找出关节点的集合，在图G上执行一个上执行一个 深度优先

18、搜索遍历。深度优先搜索遍历。 在遍历的过程中，对每个顶点在遍历的过程中，对每个顶点v保持两个标保持两个标 号：号：(v) 和和(v)，(v)只是深度优先搜索算法中的只是深度优先搜索算法中的 predfn，每次调用深度优先搜索过程，就加，每次调用深度优先搜索过程，就加1， (v)初始化为初始化为(v) ，但在后来的遍历过程，但在后来的遍历过程中可以中可以 改变。改变。 对于每一个访问的顶点，令对于每一个访问的顶点，令(v)是下面几个中的是下面几个中的 最小值。最小值。 (v)；/叶子结点叶子结点 (u)，对于每个顶点，对于每个顶点u,(v,u)是回边；是回边； (w)，在深度优先搜索树中的每条边

19、，在深度优先搜索树中的每条边 (v,w)。 上述(v)值的变化是：一旦某个点出现回边，值的变化是：一旦某个点出现回边， 则该结点的则该结点的(v)值必然变小为其祖先结点值必然变小为其祖先结点k的的() 值。值。 如果某个结点的如果某个结点的值大于其值大于其值，则肯定有一值，则肯定有一 个子结点，必然是关节点；个子结点，必然是关节点； 如果该值小于其如果该值小于其值，肯定是有回边了。值，肯定是有回边了。 如果等于如果等于值，则肯定是没有孩子了。值，则肯定是没有孩子了。 使用这个值的目的就是在回访结点的过程中，使用这个值的目的就是在回访结点的过程中， 通过判断结点的通过判断结点的与与值的关系以得到

20、该结点是什值的关系以得到该结点是什 么结点么结点 算法算法9.2 ARTICPOINTS INPUT:连通无向图连通无向图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) /从初始结点开始访问从初始结点开始访问 过程过程 dfs(v) 1. 标记标记v已访问；已访问；artpoint false; /

21、关节点标记关节点标记 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 /根节点至少根节点至少 存在两个子树，是关节结点存在两个子树，是关节结点 9. Else 10. (v) min(

22、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是关节点的个数，是关节

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

24、从因为从w到到v的祖先顶点必须经过的祖先顶点必须经过v。 这说明在图这说明在图9.4种，可以看到，从以种，可以看到，从以w为根的子为根的子 树到树到u的任何路径必定包括的任何路径必定包括v，因此，因此v是一个关节点。是一个关节点。 以以w为根的子树包含一个或多个连通分支。在这为根的子树包含一个或多个连通分支。在这 个图中，根个图中，根u是关节点，因为它的度大于是关节点，因为它的度大于1。 见例见例9.3。 e e d d c c b b f f a a h h g g i i j j a a b b c c d d e e f f g g h h i i j j 1,11,1 2,12,1 3

25、,33,3 4,34,3 5,35,3 6,16,1 7,17,1 8,88,8 9,89,8 10,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结

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

27、a结点只有一个分支孩子，所以结点只有一个分支孩子，所以a不是关节点不是关节点 e e d d c c b b f f a a h h g g i i j j a a b b c c d d e e f f g g h h i i j j 1,11,1 2,12,1 3,33,3 4,34,3 5,35,3 6,16,1 7,17,1 8,78,7 9,79,7 10,710,7 给出一个有向图给出一个有向图G=(V,E)，G中的强连通分支是中的强连通分支是 它它顶点的极大集顶点的极大集，在该集中，在该集中，每一对顶点间都存在每一对顶点间都存在 一条路径一条路径。 下面的算下面的算STRONGC

28、ONNECTCOMP用深度优用深度优 先搜索来确定在有向图中的所有的强连通分支。先搜索来确定在有向图中的所有的强连通分支。 9.3.4 强连通分支强连通分支 算法算法9.3 STRONGCONNECTCOMP INPUT:有向图有向图G=(V,E) OUTPUT:G中的强连通分支中的强连通分支 1. 在图在图G上执行深度优先搜索，对每一个顶点赋上执行深度优先搜索，对每一个顶点赋 给相应的给相应的postdfn值值。 2.颠倒图颠倒图G中边的方向，构成一个新的图中边的方向，构成一个新的图 3.从具有最大从具有最大postdfn数值的顶点开始，在数值的顶点开始，在 上执行深度优先搜索，如果深度优先

29、搜索不能上执行深度优先搜索，如果深度优先搜索不能 到达所有的顶点，则在余下的顶点中找出一个到达所有的顶点，则在余下的顶点中找出一个 postdfn数值最大的顶点，开始下一次深度优先搜数值最大的顶点，开始下一次深度优先搜 索。索。 4.在最终得到的森林中的每一棵树对应一个强连在最终得到的森林中的每一棵树对应一个强连 通分支。通分支。 见例见例9.4。 G G c c d de e b b a a f f 原图原图 a a b b e e f f c c d d a a f f e e b b c c d d 1,41,4 2,32,3 3,13,1 4,24,2 5,65,6 6,56,5 1,

30、41,4 2,22,2 3,13,1 4,34,3 5,65,6 6,56,5 深度优先搜索结果图深度优先搜索结果图 c c d de e a a f f b b 将原图翻转图将原图翻转图 a a d d e e c c b b f f 最后的结果最后的结果 1、在广度优先搜索中，当访问了一个顶点、在广度优先搜索中，当访问了一个顶点v后，后， 接下来访问邻接于接下来访问邻接于v的所有顶点，产生出来的树称的所有顶点，产生出来的树称 为广度优先搜索树。为广度优先搜索树。 2、这种遍历的方法可以通过用一个、这种遍历的方法可以通过用一个队列存储队列存储没没 有检查过的顶点来实现有检查过的顶点来实现（先

31、进先出）（先进先出）。 3、广度优先的算法、广度优先的算法BFS能够用到有向和无向图中。能够用到有向和无向图中。 初始的时候，所有的顶点都标上未访问，计数器初始的时候，所有的顶点都标上未访问，计数器bfn 初始为初始为0，它表示顶点从队列中移出的序。在无向，它表示顶点从队列中移出的序。在无向 图的情况下，一条边或者是树边或者是横跨边；如图的情况下，一条边或者是树边或者是横跨边；如 果图是有向的，那么边可以是树边、回边或横跨边，果图是有向的，那么边可以是树边、回边或横跨边， 不存在前向边。不存在前向边。 9.4 广度优先搜索广度优先搜索 算法算法9.1 BFS Input: 有向或无向图有向或无向图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 /被访问顶点进队列被访问顶点进队列 2. 标记标记v已访问已访问 3.