2009-7-27
第五章 基本检索与周游
1.检索与周游检索,以某种方法检查给定的数据对象，找出满足某些给定性质的结点的过程称为 检索周游,当检索过程必须检索到数据对象的每一个结点时，
则该检索过程称为 周游访问结点,当算法对一个结点的信息段进行处理时，称该结点 被访问 。
2009-7-27
2,二元树周游（遍历）
1）周游次序在二元树的周游中，以 D,L,R分别代表访问结点的信息段、访问左子树、访问右子树。则可能的顺序有：
★ LDR：中根次序周游（中根遍历）
★ LRD：后根次序周游（后根遍历）
★ DLR：先根次序周游（先根遍历）
★ RDL：逆中根次序周游
★ RLD：逆后根次序周游
★ DRL：逆先根次序周游
2009-7-27
2）二元树周游算法
⑴ 中根次序周游算法 5.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
2009-7-27
⑵ 先根次序周游算法 5.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
2009-7-27
⑵ 后根次序周游算法 5.2 后根次序周游的递归表示
procedure POSTORDER(T)
//T是一棵二元树。 T的每个结点有三个信息段,LCHILD,
DATA,RCHILD//
if T≠0 then
call POSTORDER(LCHILD(T))
call POSTORDER(RCHILD)
call VISIT(T)
endif
end PREORDER
2009-7-27
A
B C
D E
F G
H I
左图中：
中根次序周游的输出是：
FDHGIBEAC
先根次序周游的输出是：
ABDFGHIEC
后根次序周游的输出是：
FHIGDEBCA
2009-7-27
注：
一棵二元树可由中根遍历序列＋先根遍历序列、或中根遍历序列＋后根遍历序列 唯一 确定。但 不能 由先根遍历序列＋后根遍历序列唯一确定。
如已知一棵二元树的中根遍历次序是,DGBEAFHC
先根遍历次序是,ABDGECFH
则这棵二元树唯一确定如下,A
B
D E
G
C
F
H
2009-7-27
定理 5.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)≤c 1。
归纳法证明 t(n)≤c 2n+c1，其中 c2是一使得 c2≥2c 1的常数。
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}
≤max n1{c2n1+c1+c2(n-n1-1)+c1+c1}
＝ maxn1{c2n+3c1-c2}
≤c 2n+c1
同理，存在 c'2和 c'1有 t(n)≥c' 2n+c'1。所以 t(n)=Θ(n)
空间,若 T的深度为 d，则所需空间为 Θ(d),d≤n,所以 s(n)=Θ(n)。
2009-7-27
3,树的周游
1) 树的子树顺序无序 → 有序
2)森林 F的周游
⑴ 树的先根次序周游
A.若 F为空，则返回
B.访问 F的第一棵树的根
C.按树先根次序周游 F的第一棵树的子树
D.按树先根次序周游 F的其它树
⑵ 树的中根次序周游
⑶ 树的后根次序周游
2009-7-27
树转换成二元树方法：
设有一棵树 T(它的根是 T1)，人为安排它的子树有序且设为
T11,T12,…,T 1K。用 T1做二元树的根,T11做 T1的左子树，然后 T1i
做 T1i-1的右子树,2≤i≤k 。
T1
T11 T12 T1K…
T1
T11
T12
T1K
…设 T是由森林 F转换成的二元树则：
T的先根次序周游相当于按树先根次序周游访问 F
T的中根次序周游相当于按树中根次序周游访问 F
对 T的后根次序周游无类似的自然对应
2009-7-27
4,图的检索和周游
4.1 宽度优先检索和周游
1) 宽度优先检索
① 从结点 v开始，给 v标上 已到达 （或 访问 ）标记 ——此时称结点 v还没有被 检测,而当算法访问了邻接于某结点的所有结点时，
称该结点被检测了。
② 访问邻接于 v且尚未被访问的所有结点 ——这些结点是新的未被检测的结点。将这些结点依次放置到一 未检测结点表 (队列
Q)中（末端插入） 。
③ 标记 v已被 检测 。
④ 若未检测结点表为空，则算法终止；否则
⑤ 从未检测结点表的表头取一结点作为下一个待检测结点，
重复上述过程。
2009-7-27
算法 5.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)←1 //同时标示 w已被访问 //
endif
repeat
if Q 为空 then return endif
call DELETEQ(u,Q) //DELETEQ取出队列 Q的表头，并赋给变量 u//
repeat
end BFS
2009-7-27
定理 5.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在这之前未被访问，则此刻将被访问到。
由上，定理得证
2009-7-27
定理 5.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)—— 这一结论与使用邻接表或邻接矩阵无关。
2009-7-27
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) 使用邻接矩阵表示
2009-7-27
2) 宽度优先周游算法 5.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的周游。否则，需要 多次 调用。
2009-7-27
图周游算法的应用
●判定图 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的宽度优先生成树
2009-7-27
定理 5.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)←1 //同时标示 w已被访问 //
endif
repeat
if Q 为空 then return endif
call DELETEQ(u,Q) //DELETEQ取出队列 Q的表头，并赋给变量 u//
repeat
end BFS*
2009-7-27
证明：
若 G是 n个结点的连通图，则这 n个结点都要被访问。除起始点
v以外，其它 n-1个结点都将被放且仅将被放到队列 Q上一次，从而
T将正好包含 n-1条边，且这些边是各不相同的。即 T是关于 n个结点 n-1边的无向图。
同时，对于连通图 G,T将包含由起始结点 v到其它结点的路径，
所以 T是 连通 的。
则 T是 G的一棵 生成树 。
注：对于 n个结点且正好有 n-1条边的连通图是一棵 树 。
2009-7-27
4.2 深度优先检索和周游
1) 深度优先检索从结点 v开始，首先给 v标上 已到达 （或 访问 ）标记，同时中止对 v的检测，
并开始对邻接于 v且尚未被访问的结点 u检测。在这样的 u均被检测后，再恢复对 v的检测。当所有可到达的结点全部被检测完毕后，算法终止。
算法 5.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
2009-7-27
性质：
① 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的连通性
② 连通分图
③ 无向图自反传递闭包矩阵
④ 深度优先生成树
2009-7-27
深度优先生成树算法
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*
2009-7-27
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的深度优先生成树
2009-7-27
4.3 BFS,DFS,D_Search算法比较
BFS：使用 队列 保存未被检测的结点。结点按照 宽度优先 的次序被访问和进、出队列。
DFS：使用 栈 保存未被检测的结点，结点按照 深度优先 的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。
D_Search：使用 栈 保存未被检测的结点，结点按照 宽度优先的次序被访问并被依次压入栈中，然后以相反的次序出栈进行新的检测。新的检测结点是最新被访问但未被检测的结点。
BFS检测序列,1 2 3 4 5 6 7 8
DFS检测序列,1 2 4 8 5 6 3 7
D_Search检测序列,1 3 7 8 5 4 6 2
1
2 3
4 5 6 7
8 无向图 G
2009-7-27
5.3 双连通分图与深度优先检索
【 通信网 】 图中结点表示通信站，边表示通信线路。
1
4 2
3
10 9
5
6
7
8
图 5.11一个连通图
1 2
4 3
图 5.12一个双连通图关节点,无向连通图中某结点 a以及 a相关联的所有边删除，得到两个或两个以上的非空分图，则 a称为 G的关节点。
双连通图,如果无向连通图 G不含关节点，则称 G为双连通图。
2009-7-27
目标：
1.设计一个算法测试某个连通分图是否双连通
2.不是双连通的，找出所有的关节点
3.确定一个适当的边集加到 G上，将其变为一个双连通图概念：
双连通分图：最大双连通子图称为双连通分图
1
4 2
3
3
10
3
9
5
6
5
2 7
8
1
4 2
3
10 9
5
6
7
8
图 5.11一个连通图
2009-7-27
双连通分图性质：
1.两个双连通分图至多有一个公共结点，且这个结点是关节点
2.任何一条边不可能同时在两个不同的连通分图中（因为这需要两个公共结点）
因此，得到把图 G变成双连通图的方法,
For 每一个关节点 a do
设 B1,B2,B3,…,B K是包含结点 a的双连通分图设 Vi是 Bi的一个结点，且 Vi≠a,1≤i≤k
将（ vi,vi+1）,1≤i<k,加到 G
Repeat
图 5.11中关节点 3：增加边（ 4,10），（ 10,9）
关节点 2：增加边（ 1,5）
关节点 5：增加边（ 6,7）
将 G变为双连通图
1
4 2
3
10 9
5
6
7
8
图 5.11一个连通图
2009-7-27
1
4 2
3
10 9
5
6
7
8
图 5.11一个连通图
1
2
3
4 5
6
7
8
9
10
1
4
3
10 9 2
5
6
7
8
1
2
3
4 5 6
7
8
9
10
图 5.11中图的一棵深度优先生成树利用深度优先检索解决图的关节点与双连通分图的识别问题深度优先数（ DFN）,DFN(1)=1,DFN(2)=6
树边,实线边，代表生成树的边逆边,虚线边，代表不在生成树中的边
2009-7-27
深度优先生成树的性质：
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是一个关节点。
2009-7-27
各结点的最低深度优先数是
L(1:10)＝ (1,1,3,1,6,8,6,6,5,4)
关节点,
结点 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
4
3
10 9 2
5
6
7
8
1
2
3
4 5 6
7
8
9
10
2009-7-27
计算 L(u)的方法：按后根次序访问深度优先生成树的结点确定 G的关节点的工作：
1.完成对 G的深度优先搜索，产生 G的深度优先生成树 T
2.按后根次序访问树 T的结点算法 5.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
endif
Repeat
End ART
2009-7-27
算法分析：
设图 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不适用。
2009-7-27
5.4 与 /或图很多复杂问题很难或没法直接求解，但可以分解成一系列（类型不同）的子问题，而这些子问题又可反复细分成一些更小的子问题，一直到分成一些可普通求解的，相当与基本的问题为止。然后让这些分解成的子问题的全部或部分解在导出原问题的解。
例：洗衣服问题某人一星期洗一次衣服，要做的事可以分为收集脏衣服、洗衣服、干燥、熨衣服、叠好衣服并放入衣柜。其中，某些事可采用不同的方法，如洗衣服可以是手洗或者是机器洗。干燥可以是晾干或者机器烘干。
2009-7-27
对于上述问题，可以用 与 /或图 来表示。
与 /或图是一个有向图：结点表示问题，一个结点的子孙代表与其相关联的子问题。用一条弧将那些可以联合导出其解的子结点连结在一起。如下图 (a)中表示问题 A可以通过求解子问题 B和 C来解出，或者可由单个求解子问题 D或 E来解出。
为使结点含义单一化，即它的解或者需要求解它所有的子孙得到，或者求解它的一个子孙便可得到，通过引入图 (b)中虚结点可达到此目的。前一类结点称为 与结点,后一类结点称为 或结点 。
A
B C D E
(a)
A
A’ A’’
B C D E
(b)
2009-7-27
下图为洗衣服问题的与 /或图。图中，没有子孙的结点是终结点，它代表基本问题并标记上可解或不可解。可解的终结点用方框表示。
洗衣服问题收集脏衣服 洗 干燥 熨叠好并归堆手洗 机器洗适当的更换装入并开始晾干机器烘干适当的更换 装入并开始图 5.17洗衣服问题对应的 与 /或图
2009-7-27
概念：
解图 是由与 /或图中一些可解结点组成的子图，它表示对问题求解。
根据问题的与 /或树判断该问题是否可解方法：
对与 /或树作后根次序周游就可得出答案。
在算法执行过程中，一旦发现某与结点的一个儿子结点不可解，或者发现某或结点的一个儿子结点可解，就立即终止该算法，这可减少算法的工作量且对结果无任何影响。
2009-7-27
判断与 /或树是否可解的算法
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)
endif
repeat
return(1)
:else,for T的每个儿子 S do //或结点 //
if SOLVE(S)=1 then return(1) endif
repeat
return(0)
Endcase
End SOLVE
2009-7-27
目标,求出问题的解树。即不仅需要知道此问题是否可解，
而且希望知道如果问题可解，那么问题的解是由哪些基本问题、沿着什么样的途径所导出的。
方法,在生成与 /或树结点算法的基础上加上一些对结点可解性的判断和删除措施而获得。
说明,
1.假定问题的分解方法用函数 F来表示，即用 F生成结点的所有儿子
2.生成结点的次序既可按宽度优先也可按深度优先的次序生成。注意，一棵与 /或树可能有无穷的深度。采用深度优先生成算法时，要对生成深度作出限制。如生成的深度只准达到某个 d，凡在深度 d处的非终止结点都标记为不可解。宽度优先生成算法无此缺点，它必将找到一棵具有最小深度的解树。
2009-7-27
过程 BFGEN是一个解树的宽度优先生成算法。
1.与 /或树是在结点 T开始，应用儿子生成函数 F得到
2.采用与 SOLVE类似的算法 ASOLVE(T)。该子算法对部分生成的与 /
或树作一次后根次序周游，并且将结点标上可解、不可解或可能可解的标记。
说明,
1,T不是一棵完整的与 /或树，因此它有三类叶子结点。
2,第一类结点是非终止叶子结点。由于非终止叶子结点还没检测，因此对其可解性暂时无法断定，故将其标记为可能有解。其它两类叶子结点是完整与 /或树的叶子，故根据叶子结点所代表问题的可解性标上可解或不可解。
3,如果一个非叶子结点是与结点，则只有它有一个儿子不可解它就不可解；如果是或结点，若它至少有一个儿子有解，则该结点是可解的。所求得的所有不可解的结点都从 T中删去。
4,对于任何不可解结点 P的子孙，没有必要检测，因为，即使某些子孙可解,P也不能解出，于是可以删去 P的所有还没有检测的子孙；
对已求出其可解的结点，则没有必要进一步检测那些还没有检测的子孙。
2009-7-27
宽度优先生成解树算法
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
第五章 基本检索与周游
1.检索与周游检索,以某种方法检查给定的数据对象，找出满足某些给定性质的结点的过程称为 检索周游,当检索过程必须检索到数据对象的每一个结点时，
则该检索过程称为 周游访问结点,当算法对一个结点的信息段进行处理时，称该结点 被访问 。
2009-7-27
2,二元树周游（遍历）
1）周游次序在二元树的周游中，以 D,L,R分别代表访问结点的信息段、访问左子树、访问右子树。则可能的顺序有：
★ LDR：中根次序周游（中根遍历）
★ LRD：后根次序周游（后根遍历）
★ DLR：先根次序周游（先根遍历）
★ RDL：逆中根次序周游
★ RLD：逆后根次序周游
★ DRL：逆先根次序周游
2009-7-27
2）二元树周游算法
⑴ 中根次序周游算法 5.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
2009-7-27
⑵ 先根次序周游算法 5.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
2009-7-27
⑵ 后根次序周游算法 5.2 后根次序周游的递归表示
procedure POSTORDER(T)
//T是一棵二元树。 T的每个结点有三个信息段,LCHILD,
DATA,RCHILD//
if T≠0 then
call POSTORDER(LCHILD(T))
call POSTORDER(RCHILD)
call VISIT(T)
endif
end PREORDER
2009-7-27
A
B C
D E
F G
H I
左图中：
中根次序周游的输出是：
FDHGIBEAC
先根次序周游的输出是：
ABDFGHIEC
后根次序周游的输出是：
FHIGDEBCA
2009-7-27
注：
一棵二元树可由中根遍历序列＋先根遍历序列、或中根遍历序列＋后根遍历序列 唯一 确定。但 不能 由先根遍历序列＋后根遍历序列唯一确定。
如已知一棵二元树的中根遍历次序是,DGBEAFHC
先根遍历次序是,ABDGECFH
则这棵二元树唯一确定如下,A
B
D E
G
C
F
H
2009-7-27
定理 5.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)≤c 1。
归纳法证明 t(n)≤c 2n+c1，其中 c2是一使得 c2≥2c 1的常数。
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}
≤max n1{c2n1+c1+c2(n-n1-1)+c1+c1}
＝ maxn1{c2n+3c1-c2}
≤c 2n+c1
同理，存在 c'2和 c'1有 t(n)≥c' 2n+c'1。所以 t(n)=Θ(n)
空间,若 T的深度为 d，则所需空间为 Θ(d),d≤n,所以 s(n)=Θ(n)。
2009-7-27
3,树的周游
1) 树的子树顺序无序 → 有序
2)森林 F的周游
⑴ 树的先根次序周游
A.若 F为空，则返回
B.访问 F的第一棵树的根
C.按树先根次序周游 F的第一棵树的子树
D.按树先根次序周游 F的其它树
⑵ 树的中根次序周游
⑶ 树的后根次序周游
2009-7-27
树转换成二元树方法：
设有一棵树 T(它的根是 T1)，人为安排它的子树有序且设为
T11,T12,…,T 1K。用 T1做二元树的根,T11做 T1的左子树，然后 T1i
做 T1i-1的右子树,2≤i≤k 。
T1
T11 T12 T1K…
T1
T11
T12
T1K
…设 T是由森林 F转换成的二元树则：
T的先根次序周游相当于按树先根次序周游访问 F
T的中根次序周游相当于按树中根次序周游访问 F
对 T的后根次序周游无类似的自然对应
2009-7-27
4,图的检索和周游
4.1 宽度优先检索和周游
1) 宽度优先检索
① 从结点 v开始，给 v标上 已到达 （或 访问 ）标记 ——此时称结点 v还没有被 检测,而当算法访问了邻接于某结点的所有结点时，
称该结点被检测了。
② 访问邻接于 v且尚未被访问的所有结点 ——这些结点是新的未被检测的结点。将这些结点依次放置到一 未检测结点表 (队列
Q)中（末端插入） 。
③ 标记 v已被 检测 。
④ 若未检测结点表为空，则算法终止；否则
⑤ 从未检测结点表的表头取一结点作为下一个待检测结点，
重复上述过程。
2009-7-27
算法 5.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)←1 //同时标示 w已被访问 //
endif
repeat
if Q 为空 then return endif
call DELETEQ(u,Q) //DELETEQ取出队列 Q的表头，并赋给变量 u//
repeat
end BFS
2009-7-27
定理 5.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在这之前未被访问，则此刻将被访问到。
由上，定理得证
2009-7-27
定理 5.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)—— 这一结论与使用邻接表或邻接矩阵无关。
2009-7-27
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) 使用邻接矩阵表示
2009-7-27
2) 宽度优先周游算法 5.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的周游。否则，需要 多次 调用。
2009-7-27
图周游算法的应用
●判定图 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的宽度优先生成树
2009-7-27
定理 5.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)←1 //同时标示 w已被访问 //
endif
repeat
if Q 为空 then return endif
call DELETEQ(u,Q) //DELETEQ取出队列 Q的表头，并赋给变量 u//
repeat
end BFS*
2009-7-27
证明：
若 G是 n个结点的连通图，则这 n个结点都要被访问。除起始点
v以外，其它 n-1个结点都将被放且仅将被放到队列 Q上一次，从而
T将正好包含 n-1条边，且这些边是各不相同的。即 T是关于 n个结点 n-1边的无向图。
同时，对于连通图 G,T将包含由起始结点 v到其它结点的路径，
所以 T是 连通 的。
则 T是 G的一棵 生成树 。
注：对于 n个结点且正好有 n-1条边的连通图是一棵 树 。
2009-7-27
4.2 深度优先检索和周游
1) 深度优先检索从结点 v开始，首先给 v标上 已到达 （或 访问 ）标记，同时中止对 v的检测，
并开始对邻接于 v且尚未被访问的结点 u检测。在这样的 u均被检测后，再恢复对 v的检测。当所有可到达的结点全部被检测完毕后，算法终止。
算法 5.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
2009-7-27
性质：
① 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的连通性
② 连通分图
③ 无向图自反传递闭包矩阵
④ 深度优先生成树
2009-7-27
深度优先生成树算法
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*
2009-7-27
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的深度优先生成树
2009-7-27
4.3 BFS,DFS,D_Search算法比较
BFS：使用 队列 保存未被检测的结点。结点按照 宽度优先 的次序被访问和进、出队列。
DFS：使用 栈 保存未被检测的结点，结点按照 深度优先 的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。
D_Search：使用 栈 保存未被检测的结点，结点按照 宽度优先的次序被访问并被依次压入栈中，然后以相反的次序出栈进行新的检测。新的检测结点是最新被访问但未被检测的结点。
BFS检测序列,1 2 3 4 5 6 7 8
DFS检测序列,1 2 4 8 5 6 3 7
D_Search检测序列,1 3 7 8 5 4 6 2
1
2 3
4 5 6 7
8 无向图 G
2009-7-27
5.3 双连通分图与深度优先检索
【 通信网 】 图中结点表示通信站，边表示通信线路。
1
4 2
3
10 9
5
6
7
8
图 5.11一个连通图
1 2
4 3
图 5.12一个双连通图关节点,无向连通图中某结点 a以及 a相关联的所有边删除，得到两个或两个以上的非空分图，则 a称为 G的关节点。
双连通图,如果无向连通图 G不含关节点，则称 G为双连通图。
2009-7-27
目标：
1.设计一个算法测试某个连通分图是否双连通
2.不是双连通的，找出所有的关节点
3.确定一个适当的边集加到 G上，将其变为一个双连通图概念：
双连通分图：最大双连通子图称为双连通分图
1
4 2
3
3
10
3
9
5
6
5
2 7
8
1
4 2
3
10 9
5
6
7
8
图 5.11一个连通图
2009-7-27
双连通分图性质：
1.两个双连通分图至多有一个公共结点，且这个结点是关节点
2.任何一条边不可能同时在两个不同的连通分图中（因为这需要两个公共结点）
因此，得到把图 G变成双连通图的方法,
For 每一个关节点 a do
设 B1,B2,B3,…,B K是包含结点 a的双连通分图设 Vi是 Bi的一个结点，且 Vi≠a,1≤i≤k
将（ vi,vi+1）,1≤i<k,加到 G
Repeat
图 5.11中关节点 3：增加边（ 4,10），（ 10,9）
关节点 2：增加边（ 1,5）
关节点 5：增加边（ 6,7）
将 G变为双连通图
1
4 2
3
10 9
5
6
7
8
图 5.11一个连通图
2009-7-27
1
4 2
3
10 9
5
6
7
8
图 5.11一个连通图
1
2
3
4 5
6
7
8
9
10
1
4
3
10 9 2
5
6
7
8
1
2
3
4 5 6
7
8
9
10
图 5.11中图的一棵深度优先生成树利用深度优先检索解决图的关节点与双连通分图的识别问题深度优先数（ DFN）,DFN(1)=1,DFN(2)=6
树边,实线边，代表生成树的边逆边,虚线边，代表不在生成树中的边
2009-7-27
深度优先生成树的性质：
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是一个关节点。
2009-7-27
各结点的最低深度优先数是
L(1:10)＝ (1,1,3,1,6,8,6,6,5,4)
关节点,
结点 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
4
3
10 9 2
5
6
7
8
1
2
3
4 5 6
7
8
9
10
2009-7-27
计算 L(u)的方法：按后根次序访问深度优先生成树的结点确定 G的关节点的工作：
1.完成对 G的深度优先搜索，产生 G的深度优先生成树 T
2.按后根次序访问树 T的结点算法 5.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
endif
Repeat
End ART
2009-7-27
算法分析：
设图 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不适用。
2009-7-27
5.4 与 /或图很多复杂问题很难或没法直接求解，但可以分解成一系列（类型不同）的子问题，而这些子问题又可反复细分成一些更小的子问题，一直到分成一些可普通求解的，相当与基本的问题为止。然后让这些分解成的子问题的全部或部分解在导出原问题的解。
例：洗衣服问题某人一星期洗一次衣服，要做的事可以分为收集脏衣服、洗衣服、干燥、熨衣服、叠好衣服并放入衣柜。其中，某些事可采用不同的方法，如洗衣服可以是手洗或者是机器洗。干燥可以是晾干或者机器烘干。
2009-7-27
对于上述问题，可以用 与 /或图 来表示。
与 /或图是一个有向图：结点表示问题，一个结点的子孙代表与其相关联的子问题。用一条弧将那些可以联合导出其解的子结点连结在一起。如下图 (a)中表示问题 A可以通过求解子问题 B和 C来解出，或者可由单个求解子问题 D或 E来解出。
为使结点含义单一化，即它的解或者需要求解它所有的子孙得到，或者求解它的一个子孙便可得到，通过引入图 (b)中虚结点可达到此目的。前一类结点称为 与结点,后一类结点称为 或结点 。
A
B C D E
(a)
A
A’ A’’
B C D E
(b)
2009-7-27
下图为洗衣服问题的与 /或图。图中，没有子孙的结点是终结点，它代表基本问题并标记上可解或不可解。可解的终结点用方框表示。
洗衣服问题收集脏衣服 洗 干燥 熨叠好并归堆手洗 机器洗适当的更换装入并开始晾干机器烘干适当的更换 装入并开始图 5.17洗衣服问题对应的 与 /或图
2009-7-27
概念：
解图 是由与 /或图中一些可解结点组成的子图，它表示对问题求解。
根据问题的与 /或树判断该问题是否可解方法：
对与 /或树作后根次序周游就可得出答案。
在算法执行过程中，一旦发现某与结点的一个儿子结点不可解，或者发现某或结点的一个儿子结点可解，就立即终止该算法，这可减少算法的工作量且对结果无任何影响。
2009-7-27
判断与 /或树是否可解的算法
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)
endif
repeat
return(1)
:else,for T的每个儿子 S do //或结点 //
if SOLVE(S)=1 then return(1) endif
repeat
return(0)
Endcase
End SOLVE
2009-7-27
目标,求出问题的解树。即不仅需要知道此问题是否可解，
而且希望知道如果问题可解，那么问题的解是由哪些基本问题、沿着什么样的途径所导出的。
方法,在生成与 /或树结点算法的基础上加上一些对结点可解性的判断和删除措施而获得。
说明,
1.假定问题的分解方法用函数 F来表示，即用 F生成结点的所有儿子
2.生成结点的次序既可按宽度优先也可按深度优先的次序生成。注意，一棵与 /或树可能有无穷的深度。采用深度优先生成算法时，要对生成深度作出限制。如生成的深度只准达到某个 d，凡在深度 d处的非终止结点都标记为不可解。宽度优先生成算法无此缺点，它必将找到一棵具有最小深度的解树。
2009-7-27
过程 BFGEN是一个解树的宽度优先生成算法。
1.与 /或树是在结点 T开始，应用儿子生成函数 F得到
2.采用与 SOLVE类似的算法 ASOLVE(T)。该子算法对部分生成的与 /
或树作一次后根次序周游，并且将结点标上可解、不可解或可能可解的标记。
说明,
1,T不是一棵完整的与 /或树，因此它有三类叶子结点。
2,第一类结点是非终止叶子结点。由于非终止叶子结点还没检测，因此对其可解性暂时无法断定，故将其标记为可能有解。其它两类叶子结点是完整与 /或树的叶子，故根据叶子结点所代表问题的可解性标上可解或不可解。
3,如果一个非叶子结点是与结点，则只有它有一个儿子不可解它就不可解；如果是或结点，若它至少有一个儿子有解，则该结点是可解的。所求得的所有不可解的结点都从 T中删去。
4,对于任何不可解结点 P的子孙，没有必要检测，因为，即使某些子孙可解,P也不能解出，于是可以删去 P的所有还没有检测的子孙；
对已求出其可解的结点，则没有必要进一步检测那些还没有检测的子孙。
2009-7-27
宽度优先生成解树算法
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
