第六章 基本检索与周游方法.

Presentation on theme: "第六章 基本检索与周游方法."— Presentation transcript:

1 第六章 基本检索与周游方法

2 问题描述 许多涉及到二元树、树和图的问题 涉及问题中数据结点的访问和处理 有的问题需要访问结构中所有结点，有的访问结构的部分结点。 本章介绍的方法将适用于树、二元树，有些方法可以用于图 、树、二元树

3 6.1 一般方法 1.检索与周游 检索：以某种方法检查给定的数据对象，找出满足某些给定性质的结点的过程称为检索
周游：当检索过程必须检索到数据对象的每一个结点时，则该检索过程称为周游 访问结点：当算法对一个结点的信息段进行处理时，称该结点被访问。 结点被访问可以是结点被打印、或作某种处理

4 2. 二元树周游（遍历） 1）周游次序 在二元树的周游中，以D、L、R分别代表访问结点的信息段、访问左子树、访问右子树。则可能的顺序有：
★ LDR：中根次序周游（中根遍历） ★ LRD：后根次序周游（后根遍历） ★ DLR：先根次序周游（先根遍历） ★ RDL：逆中根次序周游 ★ RLD：逆后根次序周游 ★ DRL：逆先根次序周游

5 2）二元树周游算法 ⑴ 中根次序周游 算法6.1 中根次序周游的递归表示 procedure INORDER(T)
//T是一棵二元树。T的每个结点有三个信息段:LCHILD,DATA,RCHILD// if T≠0 then call INORDER(LCHILD(T)) call VISIT(T) call INORDER(RCHILD(T)) endif end INORDER

6 ⑵先根次序周游 算法6.2 先根次序周游的递归表示 procedure PREORDER(T) //T是一棵二元树。T的每个结点有三个信息段:LCHILD, DATA,RCHILD// if T≠0 then call VISIT(T) call PREORDER(LCHILD(T)) call PREORDER(RCHILD(T)) endif end PREORDER

7 ⑵后根次序周游 算法6.3 后根次序周游的递归表示 procedure POSTORDER(T) //T是一棵二元树。T的每个结点有三个信息段:LCHILD,DATA,RCHILD// if T≠0 then call POSTORDER(LCHILD(T)) call POSTORDER(RCHILD(T)) call VISIT(T) endif end PREORDER

8 中根次序周游：FDHGIBEAC 先根次序周游: ABDFGHIEC 后根次序周游: FHIGDEBCA A B D E G C H F I

9 一棵二元树可由中根遍历序列＋先根遍历序列、或中根遍历序列＋后根遍历序列唯一确定。但不能由先根遍历序列＋后根遍历序列唯一确定。
注： 一棵二元树可由中根遍历序列＋先根遍历序列、或中根遍历序列＋后根遍历序列唯一确定。但不能由先根遍历序列＋后根遍历序列唯一确定。 如已知一棵二元树的中根遍历次序是：DGBEAFHC 先根遍历次序是：ABDGECFH 则这棵二元树唯一确定如下: A B D E G C F H

10 时间:由于已知访问一个结点所需时间是Θ(1),故可用常数c1限界。 设T的左子树中的结点数是n1，则t(n)有：
定理6.1 当输入的树T有n≥0个结点时，设t(n)和s(n)分别表示这些周游算法中的任意一个算法所需要的最大时间和空间。如果访问一个结点所需要的时间和空间是Θ(1)，则t(n)=Θ(n), s(n)=Θ(n)。 证明： 时间:由于已知访问一个结点所需时间是Θ(1),故可用常数c1限界。 设T的左子树中的结点数是n1，则t(n)有： t(n)=maxn1{t(n1)+t(n-n1-1)+c1} n≥1 其中，t(0)≤c1。 归纳法证明t(n)≤c2n+c1，其中c2是一使得c2≥2c1的常数。 1)当n=0时，成立 2)假定当n=0,1,…,m-1时均成立。则当n=m时有， 设T是一棵有m个结点的树，T左子树结点数为n1,则 t(n)＝maxn1{t(n1)+t(n-n1-1)+c1} ≤maxn1{c2n1+c1+c2(n-n1-1)+c1+c1} ＝maxn1{c2n+3c1-c2} ≤c2n+c1 同理，存在c'2和c'1有t(n)≥c'2n+c'1。所以t(n)=Θ(n) 空间：若T的深度为d，则所需空间为Θ(d), d≤n，所以s(n)=Θ(n)。 算法所需空间是为了保存局部变量及递归调用之用。

11 3. 树的周游 1) 树的子树顺序 无序→有序 2)森林F的周游 ⑴ 树的先根次序周游 A.若F为空，则返回 B.访问F的第一棵树的根
C.按树先根次序周游F的第一棵树的子树 D.按树先根次序周游F的其它树 ⑵ 树的中根次序周游 ⑶ 树的后根次序周游

12 T的先根次序周游相当于按树先根次序周游访问F T的中根次序周游相当于按树中根次序周游访问F 对T的后根次序周游无类似的自然对应
树转换成二元树方法： 设有一棵树T(它的根是T1)，人为安排它的子树有序且设为T11,T12,…,T1K。用T1做二元树的根，T11做T1的左子树，然后T1i做T1i-1的右子树，2≤i≤k。 T1 T11 T12 T1K … T1 T11 T12 T1K … 设T是由森林F转换成的二元树,则： T的先根次序周游相当于按树先根次序周游访问F T的中根次序周游相当于按树中根次序周游访问F 对T的后根次序周游无类似的自然对应

13 4. 图的检索和周游 4.1 宽度优先检索和周游 1) 宽度优先检索
① 从结点v开始，给v标上已到达（或访问）标记——此时称结点v还没有被检测，而当算法访问了邻接于某结点v的所有结点时，称该结点被检测了。 ② 访问邻接于v且尚未被访问的所有结点——这些结点是新的未被检测的结点。将这些结点依次放置到一未检测结点表(队列Q)中（末端插入） 。 ③ 标记v已被检测。 ④ 若未检测结点表为空，则算法终止；否则 ⑤ 从未检测结点表的表头取一结点作为下一个待检测结点， 重复上述过程。

14 //宽度优先检索G，它从结点v开始。所有已访问结点被标记为VISITED(i)=1。//
算法6.6 宽度优先检索算法 procedure BFS(v) //宽度优先检索G，它从结点v开始。所有已访问结点被标记为VISITED(i)=1。// VISITED(v)←1;u←v //VISITED(n)是一个标示数组，初始值 VISITED(i)=0, 1≤i≤n // 将Q初始化为空 //Q是未检测结点的队列// loop for 邻接于u的所有结点w do if VISITED(w)=0 then //w未被检测// call ADDQ(w,Q) //ADDQ将w加入到队列Q的末端// VISITED(w)← //同时标示w已被访问// endif repeat if Q 为空 then return endif call DELETEQ(u,Q) //DELETEQ取出队列Q的表头，并赋给变量u// end BFS

15 定理6.2 算法BFS可以访问由v可到达的所有结点
证明：设G=(V,E)是一个(有向或无向)图，v∈V。 归纳法证明定理结论正确。 记d(v,w)是由v到达某一可到达结点w(w∈V)的最短路径长度 ⑴ 若d(v,w)≤1，则显然这样的所有w都将被访问。 ⑵ 假设对所有d(v,w)≤r的结点都可被访问。则当d(v,w)=r+1时有： 设w是V中d(v,w)=r+1的一个结点 设u是从v到w的最短路径上紧挨着w的前一个结点。则有 d(v,u)=r。 所以，u可通过BFS被访问到。 假设u≠v,且r≥1。根据BFS的处理规则，u将在被访问之前的某个时刻被放到未被检测结点队列Q上，而在另一时刻u将从队列Q中移出。此时，所有邻接于u且尚未被访问的结点将被访问。若结点w在这之前未被访问，则此刻将被访问到。 由上，定理得证

16 定理6.3 设t(n,e)和s(n,e)是算法BFS在任一具有n个结点和e条边的图G上所花的最大时间和最大附加空间。
● 若G由邻接表表示，则t(n,e)=Θ(n+e)和s(n,e)=Θ(n)。 ● 若G由邻接矩阵表示，则t(n,e)=Θ(n2)和s(n,e)=Θ(n) 证明：1)空间分析 根据算法的处理规则，结点v不会放到队列Q中。结点w，w∈V且w≠v,仅在VISITED(w)=0时由ADDQ(w,Q)加入队列，并置VISITED(w)=1，所以每个结点（除v)至多只有一次被放入队列Q中。 至多有n-1个这样的结点考虑，故总共至多做n-1次结点加入队列的操作。需要的队列空间至多是n-1。所以s(n,e)=Ο(n)(其余变量所需的空间为Ο(1)) 当G是一个具有v与其余的n-1个结点相连的图，则邻接于v地全部n-1个结点都将在“同一时刻”被放在队列上（Q至少应有Ω(n)的空间）。 同时，VISITED(n)本身需要Θ(n) 的空间。 所以s(n,e)=Θ(n)——这一结论与使用邻接表或邻接矩阵无关。

17 2) 时间分析 ● G采用邻接表表示 判断邻接于u的结点将在d(u)时间内完成：若G是无向图，则d(u)是u的度；若G是有向图，则d(u)是u的出度。 > 所有结点的处理时间：Ο(Σd(u))=Ο(e)。 注：嵌套循环中对G中的每一个结点至多考虑一次。 > VISITED数组的初始化时间：Ο(n) > 算法总时间：Ο(n+e)。 ● G采用邻接矩阵表示 > 判断邻接于u的所有结点需要的时间：Θ(n) > 所有结点的处理时间：Ο(n2) > 算法总时间：Ο(n2) ● 如果G是一个由v可到达所有结点的图，则将检测到V中的所有结点，所以上两种情况所需的总时间至少应是Ω(n+e)和Ω(n2)。 所以，t(n,e)=Θ(n+e) 使用邻接表表示 或， t(n,e)=Θ(n2) 使用邻接矩阵表示

18 2) 宽度优先图周游 算法6.7 宽度优先图的周游算法 procedure BFT(G,n) //G的宽度优先周游// int VISITED(n) for i←1 to n do VISITED(i)←0 repeat for i←1 to n do //反复调用BFS// if VISITED(i)=0 then call BFS(i) endif repeat end BFT 注：若G是无向连通图或强连通有向图，则一次调用BFS即可完成对T的周游。否则，需要多次调用。

19 ●判定图G的连通性：若调用BFS的次数多于1次，则G为非连通的
图周游算法的应用 ●判定图G的连通性：若调用BFS的次数多于1次，则G为非连通的 ●生成图G的连通分图：一次调用BFS中可以访问到的所有结点及连接这些结点的边构成一个连通分图。 ●无向图自反传递闭包矩阵A* ●宽度优先生成树 向前边：BFS中由u达到未访问结点w的边(u,w)称为向前边。 记T是BFS中所处理的所有向前边集合。 宽度优先生成树：若G是连通图，则BFS终止时，T构成一棵生成树。 1 2 3 4 5 6 7 8 G的宽度优先生成树 1 2 3 4 5 6 7 8 无向图G

20 定理6. 4 修改算法BFS，在第1行和第6行分别增加语句T←Φ和T←T∪{(u,w)}。修改后的算法称为BFS
定理6.4 修改算法BFS，在第1行和第6行分别增加语句T←Φ和T←T∪{(u,w)}。修改后的算法称为BFS*。若v是无向图中任一结点，调用BFS*，算法终止时，T中的边组成G的一棵生成树。 procedure BFS*(v) VISITED(v)←1;u←v T←Φ 将Q初始化为空 loop for 邻接于u的所有结点w do if VISITED(w)=0 then //w未被检测// T←T∪{(u,w)} call ADDQ(w,Q) //ADDQ将w加入到队列Q的末端// VISITED(w)← //同时标示w已被访问// endif repeat if Q 为空 then return endif call DELETEQ(u,Q) //DELETEQ取出队列Q的表头，并赋给变量u// end BFS*

21 证明： 若G是n个结点的连通图，则这n个结点都要被访问。除起始点v以外，其它n-1个结点都将被放且仅将被放到队列Q上一次，从而T将正好包含n-1条边，且这些边是各不相同的。即T是关于n个结点n-1边的无向图。 同时，对于连通图G，T将包含由起始结点v到其它结点的路径，所以T是连通的。 则T是G的一棵生成树。 注：对于n个结点且正好有n-1条边的连通图是一棵树。

22 if VISITED(w)＝0 then call DFS(w) endif repeat end DFS
4.2 深度优先检索和周游 1) 深度优先检索 从结点v开始，首先给v标上已到达（或访问）标记，同时中止对v的检测，并开始对邻接于v且尚未被访问的结点u检测。在这样的u均被检测后，再恢复对v的检测。当所有可到达的结点全部被检测完毕后，算法终止。 算法6.8 图的深度优先检索 procedure DFS(v) //已知一个n结点的无向（或有向）图G＝(V,E)以及初值已置为零的数组VISITED(1:n)。 这个算法访问由v可以到达的所有结点。// VISITED(v)←1 for 邻接于v的每个结点w do if VISITED(w)＝0 then call DFS(w) endif repeat end DFS

23 性质： ① DFS可以访问由v可到达的所有结点 ② 如果t(n,e)和s(n,e)表示DFS对一n结点e条边的图所花的最大时间和最大附加空间，则 ● s(n,e)=Θ(n) ● t(n,e)= Θ(n+e) G采用邻接表表示，或 ● t(n,e)= Θ(n2) G采用邻接矩阵表示 2) 深度优先周游算法DFT 反复调用DFS,直到所有结点均被检测到。 应用： ① 判定图G的连通性 ② 连通分图 ③ 无向图自反传递闭包矩阵 ④ 深度优先生成树

24 深度优先生成树算法 procedure DFS*(v) T←Φ VISITED(v)←1 for 邻接于v的每个结点w do
if VISITED(w)＝0 then T←T∪{(u,w)} call DFS(w) endif repeat end DFS*

25 1 2 3 4 5 6 7 8 G的深度优先生成树 1 2 3 4 5 6 7 8 无向图G 1 2 3 4 5 6 7 8 G的宽度优先生成树

26 4.3 BFS、DFS、D_Search算法比较 BFS：使用队列保存未被检测的结点。结点按照宽度优先的次序被访问和进、出队列。
1 2 3 4 5 6 7 8 无向图G

27 6.3 双连通分图与深度优先检索 【通信网】图中结点表示通信站，边表示通信线路。
1 4 2 3 10 9 5 6 7 8 图6.11一个连通图 1 2 4 3 图6.12一个双连通图 关节点：无向连通图中某结点a以及a相关联的所有边删除，得到两个或两个以上的非空分图，则a称为G的关节点。 双连通图：如果无向连通图G不含关节点，则称G为双连通图。

28 3.确定一个适当的边集加到G上，将其变为一个双连通图 概念： 双连通分图：最大双连通子图称为双连通分图
目标： 1.设计一个算法测试某个连通图是否双连通 2.不是双连通的，找出所有的关节点 3.确定一个适当的边集加到G上，将其变为一个双连通图 概念： 双连通分图：最大双连通子图称为双连通分图 1 4 2 3 10 9 5 6 7 8 图6.11一个连通图 1 4 2 3 10 9 5 6 7 8

29 1.两个双连通分图至多有一个公共结点，且这个结点是关节点 2.任何一条边不可能同时在两个不同的连通分图中（因为这需要两个公共结点）
双连通分图性质： 1.两个双连通分图至多有一个公共结点，且这个结点是关节点 2.任何一条边不可能同时在两个不同的连通分图中（因为这需要两个公共结点） 因此，得到把图G变成双连通图的方法： For 每一个关节点a do 设B1,B2,B3,…,BK是包含结点a的双连通分图 设Vi是Bi的一个结点，且Vi≠a,1≤i≤k 将（vi,vi+1）， 1≤i<k ,加到G Repeat 图6.11中 关节点3：增加边（4，10），（10，9） 关节点2：增加边（1，5） 关节点5：增加边（6，7） 将G变为双连通图 1 4 2 3 10 9 5 6 7 8 图6.11一个连通图 注意：此方法增加的总的边数比将G变成双连通图所需要的最小边数大

30 利用深度优先检索解决图的关节点与双连通分图的识别问题
1 1 1 4 2 3 10 9 5 6 7 8 图6.11一个连通图 2 4 3 3 6 4 5 10 9 2 7 5 9 7 8 6 10 8 图6.11中图的一棵深度优先生成树 深度优先数（DFN）：DFN(1)=1,DFN(2)=6 树边：实线边，代表生成树的边 逆边：虚线边，代表不在生成树中的边

31 深度优先生成树的性质： 1.若（u,v）是G中任一条边，则相对于深度优先生成树T，或者u是v的祖先，或者v是u的祖先。即没有交叉边。 （u,v）是一条相对于生成树T的交叉边指的是u不是v的祖先，v也不是u的祖先。 2.当且仅当一棵深度优先生成树的根结点至少有两个儿子时，此根结点是关节点；如果u是除根外的任一结点，那么，当且仅当由u的每一个儿子w出发，若只通过w的子孙组成的一条路径和一条逆边就可到达u的某个祖先时，则u就不是关节点。 识别关节点的规则： L(u)=min{DFN(u),min{L(W)|W是u的儿子}, min{DFN(w)| (u,w)是一条逆边}} 显然，L(u)是u通过一条子孙路径且至多后随一条逆边所可能到达的最低深度优先数。如果u不是根，那么当且仅当u有一个使得L(w) ≥ DFN(u)的儿子w时，u是一个关节点。

32 结点3：它的儿子结点10有L(10)＝4而DFN(3)=3。
关节点： 结点3：它的儿子结点10有L(10)＝4而DFN(3)=3。 结点2：儿子结点5有L(5)=6而DFN(2)＝6 结点5：儿子结点6有L(6)＝8而DFN(5)＝7 1 1 2 4 3 3 6 4 5 10 9 2 7 5 9 7 8 6 10 8

33 计算L(u)的方法：按后根次序访问深度优先生成树的结点
确定G的关节点的工作： 1.完成对G的深度优先搜索，产生G的深度优先生成树T 2.按后根次序访问树T的结点 算法6.11计算DFN和L的算法 Procedure ART(u,v) //u是开始结点。在深度优先生成树中，u若有父亲，则v是其父亲。Num=1// Global DFN(n),L(n),num,n DFN(u) ← num; L(u) ← num; num← num+1 For 每个邻接于u的结点w do if DFN(w)=0 then call ART(w,u) //还没访问w// L(u) ← min(L(u),L(w)) else if w ≠ v then L(u) ← min(L(u)，DFN(w)) endif Repeat End ART

34 ` 算法分析： 设图G有n个结点e条边，G由邻接表表示，那么ART的计算时间为O(n+e)。因此L(1:n)可在时间O(n+e)内算出。一旦算出L(1:n)，G的关节点就能在O(n)时间内识别出来。因此识别关节点的总时间不超过O(n+e) 判断G的双连通分图方法： 在第三行调用ART之后有L(w) ≥L(u)，就可断定u或者是根，或者是关节点。不管u是否是根，也不管u有一个或是多个儿子，将边(u,w)和对ART的这次调用期间遇到的所有树边和逆边加在一起，构成一个双连通分图。 对ART作一些修改即可生成该算法，算法略 注意：上述算法要在相对于生成树，所给定的图没有交叉边。而相对于宽度优先生成树，一些图可能有交叉边，此时算法ART对BFS不适用。

35 5.4与/或图 很多复杂问题很难或没法直接求解，但可以分解成一系列（类型不同）的子问题，而这些子问题又可反复细分成一些更小的子问题，一直到分成一些可普通求解的，相当与基本的问题为止。然后让这些分解成的子问题的全部或部分解在导出原问题的解。 例：洗衣服问题 某人一星期洗一次衣服，要做的事可以分为收集脏衣服、洗衣服、干燥、熨衣服、叠好衣服并放入衣柜。其中，某些事可采用不同的方法，如洗衣服可以是手洗或者是机器洗。干燥可以是晾干或者机器烘干。

36 对于上述问题，可以用与/或图来表示。 与/或图是一个有向图：结点表示问题，一个结点的子孙代表与其相关联的子问题。用一条弧将那些可以联合导出其解的子结点连结在一起。如下图(a)中表示问题A可以通过求解子问题B和C来解出，或者可由单个求解子问题D或E来解出。 为使结点含义单一化，即它的解或者需要求解它所有的子孙得到，或者求解它的一个子孙便可得到，通过引入图(b)中虚结点可达到此目的。前一类结点称为与结点，后一类结点称为或结点。 A A’ A’’ B C D E (b) A B C D E (a)

37 下图为洗衣服问题的与/或图。图中，没有子孙的结点是终结点，它代表基本问题并标记上可解或不可解。可解的终结点用方框表示。
收集 脏衣服 叠好并 归堆 洗 干燥 熨 手洗 机器洗 机器烘干 晾干 适当的更换 装入并 开始 适当的更换 装入并 开始 图6.17洗衣服问题对应的与/或图

38 概念： 解图是由与/或图中一些可解结点组成的子图，它 表示对问题求解。 根据问题的与/或树判断该问题是否可解方法： 对与/或树作后根次序周游就可得出答案。 在算法执行过程中，一旦发现某与结点的一个儿子结点不可解，或者发现某或结点的一个儿子结点可解，就立即终止该算法，这可减少算法的工作量且对结果无任何影响。

39 :T是终结点： if T可解 then return(1) else return(0) endif
判断与/或树是否可解的算法 Procedure SOLVE(T) //T是一棵其根为T的与/或树，T ≠0。如果问题可解则返回1，否则返回0// CASE :T是终结点： if T可解 then return(1) else return(0) endif :T是与结点： for T的每个儿子S do if SOLVE(S)=0 then return(0) repeat return(1) :else: for T的每个儿子S do //或结点// if SOLVE(S)=1 then return(1) endif return(0) Endcase End SOLVE

40 目标：求出问题的解树。即不仅需要知道此问题是否可解，而且希望知道如果问题可解，那么问题的解是由哪些基本问题、沿着什么样的途径所导出的。
方法：在生成与/或树结点算法的基础上加上一些对结点可解性的判断和删除措施而获得。 说明： 1.假定问题的分解方法用函数F来表示，即用F生成结点的所 有儿子 2.生成结点的次序既可按宽度优先也可按深度优先的次序生成。注意，一棵与/或树可能有无穷的深度。采用深度优先生成算法时，要对生成深度作出限制。如生成的深度只准达到某个d，凡在深度d处的非终止结点都标记为不可解。宽度优先生成算法无此缺点，它必将找到一棵具有最小深度的解树。

41 过程BFGEN是一个解树的宽度优先生成算法。
1.与/或树是在结点T开始，应用儿子生成函数F得到 2.采用与SOLVE类似的算法ASOLVE(T)。该子算法对部分生成的与/或树作一次后根次序周游，并且将结点标上可解、不可解或可能可解的标记。 说明： T不是一棵完整的与/或树，因此它有三类叶子结点。 第一类结点是非终止叶子结点。由于非终止叶子结点还没检测，因此对其可解性暂时无法断定，故将其标记为可能有解。其它两类叶子结点是完整与/或树的叶子，故根据叶子结点所代表问题的可解性标上可解或不可解。 如果一个非叶子结点是与结点，则只有它有一个儿子不可解它就不可解；如果是或结点，若它至少有一个儿子有解，则该结点是可解的。所求得的所有不可解的结点都从T中删去。 对于任何不可解结点P的子孙，没有必要检测，因为，即使某些子孙可解，P也不能解出，于是可以删去P的所有还没有检测的子孙；对已求出其可解的结点，则没有必要进一步检测那些还没有检测的子孙。

42 宽度优先生成解树算法 Procedure BFGEN(T,F) //F生成T中的儿子结点；T是根结点。终止时，如果存在解树，则T是这解树的根// Loop 用F生成V的那些儿子 //检测V// if V没有儿子 then 标记 V为不可解 else ①将V的所有不是叶子结点的儿子放入队列Q， 将那些叶子结点分别标上可解或不可解 ②把V的所有儿子加入树T endif call ASOLVE(T) 从树T删去所有标记为不可解的结点 if 根结点T标记为可解 then return(T) endif 从队列Q中删去以下所有的结点：它们在T中曾有一个祖先被标记 为不可解或者在T中有一个标记为可解的祖先 if Q为空 then print(“no solution”); stop endif 删去队列Q的第一个元素；设此结点为V Repeat End BFGEN