第九章图的遍历算法

第三部分最先割技术

第九章图的遍历

第九章图的遍历9．1引言9．2深度优先搜索9．3深度优先搜索的应用9．4广度优先搜索9．5广度优先搜索的应用在一些诸如找出最短路径和最小生成树的图的算法中，用由它们相应的算法顺序访问顶点和边。然而，在一些其他算法中，访问顶点的顺序是不重要的，重要的是，不管输入的图如何，用一种系统的顺序来访问顶点。在本章中，我们讨论图遍历的两种方法：深度优先搜索和广度优先搜索。9.1引言设G=(V,E)是一个有向或无向图，G的深度优先搜索运作如下：1、初始化所有的顶点访问标志为未访问；2、任意选择一个起始顶点，比如说s∈V，并标上已访问。3、从s的邻接顶点中选择任意一个顶点w，访问该顶点，同时将其标志为被访问。9.2深度优先搜索

3、将访问指针移至w结点，将其标志为被访问，然后从w的临接结点中选择一个未被访问的结点，向前继续访问；

4、在访问过程中，按照上述的深度优先的方式向前推进，一旦发现某一个顶点X的所有邻接点都被标志为已访问，访问指针回退至上一层，继续访问该层没有被访问的其他的子节点。

5、如此往复，直至回退到根节点为止。算法9.1DFSInput:有向或无向图G=(V,E)。Output:在相应的深度优先搜索树中对顶点的前序和后序。1.predfn0;postdfn02.For每个顶点v∈V3.标记v未访问//初始化访问标志4.Endfor5.For每个顶点v∈V6.Ifv未访问thendfs(v)//调用访问7.Endfor过程dfs(v)//递归访问1.标记v已访问2.predfnpredfn+1

//进来访问，是前序号3.For每条边(v,w)∈E4.Ifw标记为未访问thendfs(w)5.Endfor6.postdfnpostdfn+1

//结点被访问完毕，退回时访问该语句，即后序号算法生成结构：1、树（全部顶点相连，能够一次到达）；2、森林（顶点不相连，不能够一次都到达）。1、无向图的情况分析设G=(V,E)是无向图，作为遍历的结果，G的边分成一下两种类型。树边：深度优先搜索树中的边，如果在搜索边(v,w)时，w是首次被访问，则边(v,w)是树边。回边：所有其它的边。例9.1。edcbfahgijabcdefghij1,102,93,34,25,16,87,78,69,510,42、有向图的情况

有向图中的深度优先搜索导致结果：一个或多个(有向)生成树，树的多少取决于初始点。（1）选择某起始点v，深度优先搜索一棵树，它由从v出发所有可到达的顶点组成。（2）没有遍历完所有的顶点，选择另一个顶点w继续（未访问过顶点），构建一颗从w可到达的所有未访问顶点组成的树，这个过程继续下去直到所有的顶点都被访问过。（3）重复上述过程，直至所有顶点被访问完毕。G的边分成4种类型：1、树边：深度优先搜索树中的边。如果在搜索边(v,w)时，w是第一次被访问，则(v,w)是树边。2、回边：在迄今为止构建的深度优先搜索树中，w是v的祖先，并且当搜索(v,w)时顶点w已被标上已访问，这样形成的边(v,w)是回边。3、前向边：在迄今为止构建的深度优先搜索树中，w是v的后裔，并且当搜索(v,w)时顶点w被标上已访问，这种形式的边(v,w)是前向边。3、横跨边：所有其它的边。见例9.2。cdebafabefcdafebcd1,42,33,14,25,66,51,42,23,14,35,66,5

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

9.2.1深度优先搜索的时间复杂性（4）测试顶点w是否标记为未访问，这一步的执行次数等于顶点v的邻接点数。

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

深度优先搜索在图和几何算法中用得很普遍。在本节中，我们列举它的一些重要应用。设G=(V,E)是一个有n个顶点和m条边的有向或无向图。为了测试G是否至少有一个回路，我们对G用深度优先搜索，如果在搜索过程中探测到一条回边，那么G是有回路的，否则G是无回路的。

注意G可能不连通，如果G是连通无向图，那么不需要对图进行遍历，因为G是无回路的当且仅当它是一棵树，则当且仅当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，如果不是的话，我们可以简单地添一个新的顶点s，然后让s到所有入度为0的点加上边。9.3.2拓扑排序abdfcegs接下来，我们从顶点s起，简单地对图G执行深度优先搜索。当遍历完成时，计数器postdfn定义了一个在有向无回路图中顶点的反扑排序，于是，为了得到这个拓扑序，可以在算法DFS中在计数器postdfn刚好被增加后，加上一个输出步，把输出结果翻转过来就是我们需要的拓扑序。

关节点:

在多于两个顶点的无向图G中，存在一个顶点v，如果有不同于v的两个顶点u和w，在u和w间的任何路径都必定经过顶点v。这样，如果G是连通的，移去v和与它关联的边，将产生G的非连通子图（森林）。一个图如果是连通的并且没有关节点则称为是双连通的。9.3.3寻找图的关节点由深度优先生成树的特性可以得到如下结论：1、根是一个关节点当且仅当在深度优先搜索树中，它有两个或更多的儿子；原因：图中不存在连接不同子树顶点的边，删掉根结点后，生成树就变成了森林。2、根以外的其他结点V，如果其某棵子树的根和子树中的其他结点均没有指向该结点v的祖先的回边。或者：根以外的顶点v是一个关节点当且仅当v有一个儿子w，使得β(w)≥α(v)。为了找出关节点的集合，在图G上执行一个深度优先搜索遍历。在遍历的过程中，对每个顶点v保持两个标号：α(v)和β(v)，α(v)只是深度优先搜索算法中的predfn，每次调用深度优先搜索过程，就加1，β(v)初始化为α(v)，但在后来的遍历过程中可以改变。对于每一个访问的顶点，令β(v)是下面几个中的最小值。

α(v)；//叶子结点

α(u)，对于每个顶点u,(v,u)是回边；

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

使用这个值的目的就是在回访结点的过程中，通过判断结点的α与β值的关系以得到该结点是什么结点

算法9.2ARTICPOINTSINPUT:连通无向图G=(V,E)。OUTPUT:包含G的所有可能关节点的数组A[1…n]。1.设s为起始顶点2.for每个顶点v∈V3.标记v未访问4.endfor//初始化全部结点为没有访问5.predfn0;count0;rootdegree06.dfs(s)//从初始结点开始访问过程dfs(v)1.标记v已访问；artpointfalse;//关节点标记predfnpredfn+1//标记序号2.α(v)predfn;

β(v)predfn//初始化访问序号3.For每条边(v,w)∈E4.If(v,w)为树边then5.dfs(w)//深入开始访问后续结点6.Ifv=sthen

//树根结点7.rootdegreerootdegree+18.Ifrootdegree=2thenartpointtrue//根节点至少存在两个子树，是关节结点9.Else

10.β(v)min{β(v),β(w)}11.Ifβ(w)≥α(v)thenartpointtrue//有孩子就标记为关节结点12.Endif13.Elseif(v,w)是回边then//v!=s

β(v)min{β(v),α(w)}14.Elsedonothing{w是v的父亲}15.Endif16.Endfor17.Ifartpointthen18.countcount+119.A[count]

v20.Endif（1）首先，算法执行必要的初始化，特别地，count是关节点的个数，rootdegree是深度优先搜索树根的度，这在后来决定根是否是关节点时是需要的。（2）接着深度优先搜索从根开始着手，对于每一个访问的顶点v，α(v)和β(v)用predfn来初始化。（3）在搜索从某顶点w退回到v时，要做两件事，首先，如果发现β(w)比β(v)小，β(v)被设置为β(w)，其次，如果β(w)≥α(v)，那么这就指出v是一个关节点，因为从w到v的祖先顶点必须经过v。这说明在图9.4种，可以看到，从以w为根的子树到u的任何路径必定包括v，因此v是一个关节点。以w为根的子树包含一个或多个连通分支。在这个图中，根u是关节点，因为它的度大于1。见例9.3。edcbfahgijabcdefghij1,12,13,34,35,36,17,18,89,810,8（1）初始化各个顶点；（2）从a-e开始搜索，一直到e均是正常搜索，各个数值依次递增增长；（3）搜索到e时，找到一个回边(e,c)，则e的β(e)=min{a[c]=3；a[e]=5,β[c]=3}=3；（4）回退至d点时，该点的β[d]=3;(原来是4);(5)回退到c点，β[c]=3，由于β[d]>=a[c]，所以该结点是关节点。(6)回退到b结点，β[c]>=a[b]，所以b也是一个关节点。此时，发现b结点还有一个分支，继续搜索该分支。（1）探测到（j,h）是一个回边，所以将

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

edcbfahgijabcdefghij1,12,13,34,35,36,17,18,79,710,7给出一个有向图G=(V,E)，G中的强连通分支是它顶点的极大集，在该集中，每一对顶点间都存在一条路径。下面的算STRONGCONNECTCOMP用深度优先搜索来确定在有向图中的所有的强连通分支。9.3.4强连通分支算法9.3STRONGCONNECTCOMPINPUT:有向图G=(V,E)OUTPUT:G中的强连通分支1.在图G上执行深度优先搜索，对每一个顶点赋给相应的postdfn值。2.颠倒图G中边的方向，构成一个新的图3.从具有最大postdfn数值的顶点开始，在上执行深度优先搜索，如果深度优先搜索不能到达所有的顶点，则在余下的顶点中找出一个postdfn数值最大的顶点，开始下一次深度优先搜索。

4.在最终得到的森林中的每一棵树对应一个强连通分支。见例9.4。cdebaf原图abefcdafebcd1,42,33,14,25,66,51,42,23,14,35,66,5深度优先搜索结果图cdeafb将原图翻转图adecbf最后的结果1、在广度优先搜索中，当访问了一个顶点v后，接下来访问邻接于v的所有顶点，产生出来的树称为广度优先搜索树。2、这种遍历的方法可以通过用一个队列存储没有检查过的顶点来实现（先进先出）。3、广度优先的算法BFS能够用到有向和无向图中。初始的时候，所有的顶点都标上未访问，计数器bfn初始为0，它表示顶点从队列中移出的序。在无向图的情况下，一条边或者是树边或者是横跨边；如果图是有向的，那么边可以是树边、回边或横跨边，不存在前向边。9.4广度优先搜索算法9.1BFSInput:有向或无向图G=(V,E)。Output:广度优先搜索次序中顶点的编号。1.bfn02.For每个顶点v∈V3.标记v未访问4.Endfor5.For每个顶点v∈V6.Ifv未访问thenbfs(v)7.Endfor过程bfs(v)1.Q{v}//被访问顶点进队列2.标记v已访问3.WhileQ≠{}4.vPop(Q)