第4章基本搜索和遍历方法

1

第4章基本搜索和遍历方法4.1基本概念4.2图的搜索和遍历4.3双连通分量4.4与或图×4.1基本概念2搜索和遍历是计算机问题求解最常用的技术之一。搜索（search）是一种通过系统地检查给定数据对象的每个结点，寻找一条从开始结点到答案结点的路径，最终输出问题解的求解方法。遍历(traversal)要求系统地检查数据对象的每个结点。根据被遍历的数据对象的结构不同，可分成树遍历和图遍历。4.1基本概念状态空间用于描述所求问题的各种可能的情况，每一种情况对应于状态空间中的一个状态。初始状态：代表搜索开始。目标状态（答案状态）：一个或多个状态代表已经求得问题解的情况。问题的状态空间常用一棵树或一个图表示。树（图）中的一个结点代表问题的一个状态，问题的状态空间中的所有状态形成一棵状态空间树（图）。问题的求解过程:从起始状态出发，以某种次序系统地检查状态空间中的每一个状态，搜索代表问题解的答案状态的过程。3一般来说，使用搜索技术来求解计算机问题，需要使用状态空间的概念精确地描述问题。无知搜索（盲目搜索或穷举搜索），是最简单的搜索状态空间树的方法。按照事先约定的某种次序，系统地在状态空间中搜索目标状态，而无须对状态空间有较多了解。4有知搜索：运用问题的相关知识，克服无知搜索的盲目性，有效地指导搜索过程，使之尽快到达答案状态。启发式搜索：采用经验法则的搜索方法。启发式方法一边搜索，一边评估达到目标状态的剩余距离，这种评估依赖于已有的关于问题领域的知识和经验规则。4.2图的搜索和遍历4.2.1搜索方法在树形结构中，一个结点的直接后继结点是它的孩子结点。在图形结构中，一个结点的后继结点是邻接于该结点的所有邻接点。5遍历：遵循某种次序，系统地访问一个数据结构的全部元素。实现遍历运算的关键是规定结点被访问的次序。6为深入认识搜索算法的特点，将被搜索的结点按其状态分成4类：未访问、未检测、已检测和正扩展。未访问状态：一个结点x尚未访问；未检测状态：结点x自身已访问，但x的后继结点尚未全部访问；已检测状态：当算法访问了x的所有后继结点时，就称x已由此算法检测；正扩展状态：算法正从结点x出发，访问x的某个后继结点,x被称为扩展结点，简称E-结点。在算法执行的任何时刻，最多只有一个结点为E-结点，但可以有多个结点处于未检测状态。由于一个搜索算法总是从一个未检测结点出发，获取下一个被访问的结点，因此，保存所有未检测结点对于搜索算法是十分重要的。活结点：指未检测结点。死结点：指已检测结点。在搜索算法的执行中，需要有一个数据结构保存这些活结点，被称为活结点表。7依据如何选择E-结点的规则不同，得到两种不同的搜索算法：深度优先搜索和广度优先搜索。8

4.2.2邻接表类设有向图G=(V,E)有n个结点。图4-1(b)给出了图4-1(a)的邻接表存储结构。4.2.3广度优先搜索9广度优先搜索：一个结点x一旦成为E结点，算法将依次访问完它的全部未访问的后继结点。每访问一个结点，就将它加入活结点表。直到x检测完毕，算法才从活结点表另选一个活结点作为E结点。广度优先搜索以队列作为活结点表，因而也被称为FIFO搜索。10为了实现搜索，也为了形象地刻画图搜索算法的执行过程，算法中使用白色、灰色和黑色分别代表结点处于未访问、未检测和已检测三种不同状态。E结点是灰色结点，任何时刻至多有一个灰色结点处于扩展状态。使用结点的颜色替代标志位标记一个结点是否已访问。为了保持搜索的轨迹，广度优先搜索为每个顶点着色：白色、灰色或黑色。算法开始前所有顶点都是白色，随着搜索的进行，各顶点会逐渐变成灰色，然后成为黑色。1.广度优先遍历算法

11

假设初始时图G的所有结点都为白色结点，那么从图中某个结点u出发的广度优先搜索图的过程可以描述为：访问结点u，结点u着灰色；然后依次访问u的各个白色邻接点，将它们着灰色；访问完结点u的所有白色邻接点，结点u着黑色；接着再依次访问分别与这些邻接点相邻接的白色结点……队列Q保存搜索过程中产生的活结点。12

举例：广度优先搜索在一个无向图（结点S开始）上的执行过程132.广度优先树14

算法BFS同时可生成一棵广度优先树（森林）。初始时，树中只包含搜索的源结点作为根结点。在搜索中，对于E结点u，每发现一个白色结点v，便将结点v和边<u,v>添加到树中。在广度优先树中，称结点u是结点v的双亲结点。如果结点v是从根结点到结点w的路径上的一个结点，则称v是w的祖先，w是v的后裔。由于从一个给定的起始结点u出发的广度优先搜索，只能访问从u出发有路径可达的那些结点。如果要遍历整个有向图，还需从图中另选未访问的结点作为起始结点，再次进行广度优先搜索。15图4-2给出了以结点0为起点，广度优先遍历图4-1(a)的有向图G所得到的广度优先森林，它包含两棵广度优先树。返回01236540123654图G的广度优先森林课堂练习对于下面一个图及其存储结构，写出以v2、v8为起始点的广度优先遍历序列，并画出广度优先树。16v1v2v3v4v5v6v7v801v12v23v34v45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v517参考答案：以v2为起始点：v2-v1-v4-v5-v3-v8-v6-v7以v8为起始点：v8-v4-v5-v2-v1-v3-v6-v7v1v2v3v4v5v6v7v8v1v2v3v4v5v6v7v84.2.4深度优先搜索18

深度优先搜索：访问E结点x的某个后继结点y后，立即使y成为新的E结点，去访问y的后继结点，直到完全检测结点y后，x才能再次成为E结点，继续访问x的其他未访问的后继结点。深度优先搜索使用堆栈为活结点表。1.深度优先遍历算法

19

初始时，图G的所有结点都为白色结点，从图中某个结点u出发的深度优先搜索过程DFS可以描述为：（1）访问结点u,对结点u着灰色；（2）依次从u的白色邻接点出发，深度优先搜索图G。为了访问有向图中的所有结点，必须从图中另选白色结点为起始结点，再次进行深度优先搜索。可能需要重复多次，直到图中结点均已访问。20为便于分析深度优先搜索算法的执行情况，在搜索中为每个结点添加时间戳。深度优先搜索对每个结点u加盖两个时间戳d[u]和f[u]：第1个时间：当结点u着灰色时，由d[u]记录；第2个时间：当结点u着黑色时，由f[u]记录。在时刻d[u]之前结点u为白色，在时刻d[u]和f[u]之间为灰色，f[u]以后变为黑色。初始时，对所有结点u，d[u]=f[u]=0，时钟的初值为0.21图2说明了深度优先搜索在有向图（u出发）上的执行过程。2223加粗的实线边--树枝虚线边--非树枝的边，分别标明B、C、F以表示反向边、交叉边、正向边。2.深度优先树24

算法同时可生成一棵深度优先树。初始时，树中只包含搜索的源结点作为根结点。在搜索中，一个结点，每发现一个白色结点，便将结点及边添加到树中。对比01236540123654图G的深度优先森林254.深度优先搜索的性质定理4-2括号定理在对有向图或无向图G=(V,E)的任何深度优先搜索中，对于图中任意两结点u和v，下述三个条件中有且仅有一条成立：(1)区间[d[u],f[u]]和区间[d[v],f[v]]是完全分离的，且在深度优先森林中，u和v互不为后裔；(2)区间[d[u],f[u]]完全包含区间[d[v],f[v]]，且在深度优先树中v是u的后裔；(3)区间[d[v],f[v]]完全包含区间[d[u],f[u]]，且在深度优先树中u是v的后裔；5.边的分类26

（1）树边(treeedge)：深度优先森林的边。（2）反向边B(backedge)：深度优先树中从后裔到祖先的边，环也被认为是反向边。（3）正向边F(forwardedge)：深度优先树中从祖先到后裔的非树边。（4）交叉边C(crossedge)：其余的边。当一条边既是反向边又是正向边时，则认为它是反向边。课堂练习对于下图及其邻接表，写出以v2、v8为起始点的深度优先遍历序列，并画出深度优先树，标出边的分类。2701v12v23v34v45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1v2v3v4v5v6v7v8参考答案：以v2为起始点：v2-v1-v3-v6-v7-v4-v8-v5以v8为起始点：v8-v4-v2-v1-v3-v6-v7-v528v1v2v3v4v5v6v7v8BBv1v2v3v4v5v6v7v8BB294.3双连通分量4.3.1基本概念

双连通图：一个无向图的任意两个结点之间至少有两条不同的路径相通。针对无向图关节点：在一个无向连通图G=(V,E)中，可能存在某个（或多个）结点a，使得一旦删除a及其相关联的边，图G不再是连通图，则结点a称为图G的关节点。桥：如果删除图G的某条边b,该图分离成两个非空子图，则称边b是图G的桥。30

图4-5(a)中的图G有哪些关节点？哪条边是桥？(a)无向连通图G01326547(b)删除图G的关节点1(c)删除图G的桥<6,1>03265470132654731

双连通分量：无向连通图G的极大双连通子图。一个无向图可以分成多个双连通分量，它们将图中的边划分为若干个子集（不是将结点划分子集）。双连通图：无向连通图G中不包含任何关节点。0132654732

从图中可以看出：1.两个双连通分量至多有一个公共结点，且此结点必为关节点。2.两个双连通分量不可能共有同一条边。3.每个双连通分量至少包含两个结点（除非无向图只有一个结点）(a)无向连通图G01326547双连通分量1246571603233对于一个无向连通图G，下列说法是等价的：（1）图G是双连通的；（2）图G的任意两个结点之间存在简单回路；（3）图G中不包含关节点。简单回路：在一个回路中，出现的边互不相同。4.3.2发现关节点在网络应用中，通常不希望网络中存在关节点。因为这意味着一旦在这些位置出现故障，势必导致大面积的通信中断。因此判定一个无向图是否双连通图，在图中发现关节点及求图的双连通分量是很有实际意义的问题。34一个无向连通图不是双连通图的充要条件是图中存在关节点。在无向图中识别关节点的最简单做法是：从图G中删除一个结点a和该结点的关联边，再检查图G的连通性。如果图G因此而不再是连通图，则结点a是关节点。35需借助图的深度优先生成树来识别关节点。

假设从某个顶点V0出发对连通图进行深度优先搜索，则可得到一棵深度优先生成树，树上包含图的所有顶点。36ahgcbfde1abcdefgh2345678例如:下列连通图中的关节点？结点a,c是关节点深度优先生成树(a为根结点)结点的深度优先数，记录了结点被访问的先后次序37

性质4-3

给定无向连通图G=(V,E),S=(V,T)是图G的一棵深度优先树，图中结点a是一个关节点，当且仅当（1）a是根，且a至少有两个孩子。（2）或者a不是根，且a的某棵子树上没有指向a的祖先的反向边。求图G关节点的算法38

深度优先数：在深度优先搜索中对每个结点u加盖两个时间戳。其中，d[u]记录结点u被访问的时间，也称为结点的深度优先数；为了实现这一算法，需要对图中每个结点定义一个与优先数有关的量Low。最低深度优先数：Low[u]表示从结点u出发，经过某条路径可以达到深度优先树其他结点的最小优先数；39

从结点u出发，有两种途径可以达到树中其他结点：一、自结点u经过一条反向边到达某个结点x；二、自结点u出发，经过u的某个孩子w，以及一条由w出发的由树边组成的一条路径和反向边到达某个结点y；Low[u]是结点u通过一条子孙路径和至多随后一条反向边所能到达的结点的最低深度优先数。40

定义4-1：Low[u]定义如下：Low[u]=min{d[u],

min{Low[w]|w是u的孩子}，min{d[x]|(u,x)是一条反向边}}图4-9深度优先搜索和深度优先数0132654707123456如果u不是根，当且仅当结点u有一个孩子w，其Low[w]≥d[u]时，u是一个关节点41

图中每个结点边上的偶对(d,Low)代表该结点的相应值。例如，结点2边上的(1,0)代表d[2]=1，Low[2]=0.图4-10结点的d和Low值01326547(0,0)(6,4)(5,4)(4,4)(3,1)(2,1)(1,0)(7,0)4.3.3构造双连通图42

发现关节点和求双连通分量的