算法第七章周游

第七章基本检索与周游方法1、一般方法2、代码优化（略）3、双连通分图4、与或图5、对策树1/40第七章基本检索与周游方法§

1、一般方法一、定义若需要确定满足某一性质的一个结点或结点子集，需要对所有结点检索，这种检索方法称为周游。二、二叉树周游1、中根遍历：

左 、根、右procedure

inorder(T)if

T≠null

then inorder

(T.lchild)visit(T)inorder(T.rchild)endifendinorder2/40中根遍历:FDHGIBEAC前根遍历:ABDFGHIEC后根遍历:FHIGDEBCAFGHIABCDE例2:第七章基本检索与周游方法§

1、一般方法4/40••••2、前根遍历:

根、左

、右、右

、根3、后根遍历:

左4、算法分析设t(n)、s(n)分别表示上述算法对于树T（设有n个结点）所需要的最大时间和空间。•则•定理(n1

)

t(n

n1

1)

c1}t(n)

c2n

c1,

(c2

2c1)第七章基本检索与周游方法§

1、一般方法证

n=0

则成立。设n

m

1，结论成立。则n=m时t(m

max{t(n1

)

t(m

n1

1)

c1}(0

n1

m

1)

max{c2n1

c1

c2

(m

n1

1)

c1}•成立t(n)

c2n

c1又t(0)

c2m

3c1

c2

c2m

c1t(n)

(n)t(n)

c2n

c1(c2

2c1)定理c2

2c1第七章基本检索与周游方法§

1、一般方法5/402、中根遍历:3、后根遍历：按树中根遍历第一棵树的第一棵树的根按树中根遍历其余树按树后根遍历第一棵树的按树后根遍历其余树二、树的周游1、先根遍历：

第一棵树的根按树先根遍历第一棵树的按树先根遍历其余树••••••第一棵树的根第七章基本检索与周游方法§

1、一般方法6/40NG

H

J树的先根遍历：ABEGHJFCDKLMNOP树的中根遍历：GEHJBFACDLKNMPO树的后根遍历：GHJFCDEBLNPOMKADABEFKLMOPc例2：第七章基本检索与周游方法§

1、一般方法8/40例1三、应用••••••试计算一二叉树的高度procedure

high(T)if

T=null

then

return(0)else return

max(high(T.lchild),high(T.rchild))+1endifend

high第七章基本检索与周游方法§

1、一般方法四、图的宽度优先遍历以队列的结构存放•过结点的遍历方法。例12345678设置一个队列为空Queue:1、2、3、4、5、6、7、8次序：1、2、3、4、5、6、7、8第七章基本检索与周游方法§

1、一般方法9/401、算法7.6图宽度优先检索算法••line

procedure

BFS(v)//宽度优先搜索G，它在结点v开始执行时。所有已 结点都标上VISITED(i)=1。图G和数组VISITED是全程量。VISITED开始时都已置成0//•••VISITED(v)1;uv将Q初始化为空//Q是未检测结点的队列//loop4for

邻接于u的所有结点wdo•5if

VISITED(w)=0

then

callADDQ(w,Q)//w未检测//•6VISITED(w)1•7endif•8repeat•9if

Q为空

then

return

endif //不再有还未检测的结点//•10call

DELETEQ(u,Q)•11repeat•12BFS10/402、算法分析定理：设t(n,e)和s(n,e)是BFS在任一具有n个结点和e条边的图G上所花的最大时间和最大附加空间，则t(n,e)=(n+e)，s(n,e)=(n)证明：因BFS完成队列和边的检索工作，而它至多做n-1次加入队列的动作，所以s(n,e)=O(n),又因为visited操作需要（n)空间，所以s(n,e)=

(n)。如使用邻接表，则邻接于u的所有结点可以在deg(u)时间内判断，所以检测总时间为：(deg(u))(e)，visited数组初始化需要O(n),所以t(n,e)=(n+e)。如使用邻接矩阵，则检测时间为(n2),此时，t(n,e)=

(n2)第七章基本检索与周游方法§

1、一般方法3.非连通图BFS周游算法Procedure

BFT(G,n)declare

VISITED(n)for

i=1

to

n

doVISITED(i)=0repeatfor

i=1

to

n

doif

VISITED(i)=0

then BFS(i)

endifrepeatend

BFT•第七章基本检索与周游方法§

1、一般方法由v可以到达的所已置为零的数组VISITED(1:n)。这个算法有结点。G和VISITED是全程量//••12VISITED(v)1for

邻接于v的每个结点w

do•3if

VISITED(w)=0 then

call

DFS(w)

endif•4repeat•5end

DFS第七章基本检索与周游方法§

1、一般方法五、图的深度优先遍历1、图的深度优先搜索算法line

procedure

DFS(v)//已知一个n结点的无向（或有向）图G=（V,E）以及初值13/40••2、

DFS算法的执行过程图称为DFS树例 遍历过程如下图所示：7123456812345867第七章基本检索与周游方法§

1、一般方法14/40DFS(w)endifVISITED(v)1for邻接于v的每个结点w

doif

VISITED(w)=0 thencallrepeatend

DFSprocedure

DFS(v)第七章基本检索与周游方法•§3、双连通分图一、双连通分图1、定义：若在无向连通图G中，删除结点a及关联边，G变成不连通，则a称为割点，不含割点的图称为双连通图。例 为双连通图2、定义：若G'(V

',E')是双连通子图，且在G中再不存在这样的双连通子图G''(V

'',E'')

,使V

'

V

''•且E'

E''连通分图。称G

'为G的极大双连通子图，简称为双15/40例图7.1114226738310955第七章基本检索与周游方法§3、双连通分图16/4033、双连通分图的性质1）任何两个双连通分图至多只有一个公共点并且该公共点就是割点。为双连通分图，有一个公共点a，若a证明：若G1,不是割点，则通分图,与前提G1

G2。证明b，所以图,与前提若分图G1,G1

{a},

G2有两个公共点a,b，则除去a,{a}仍连通，因G1,G2

还有一公共点G1

G2。{a}

仍连通，则

G1

为双连G21GG2{a}仍连通，则

G1

为双连通分G2第七章基本检索与周游方法§3、双连通分图17/40∴G1

G2

为双连通分图这与前提2）任何一条边不能同时在两个不同的连通分图中证明：否则的话会导致该边关联的两个结点，成为两个分图的公共点，这与性质1）

。abG1G2第七章基本检索与周游方法§3、双连通分图18/40因为如此加边之后，原有的各点不再成为其割点，则要增加的边数为Bk（删除a后,

B1

仍连通），设图G有a1,a2,…,ap个割点a，i与割点 关联的ki分图数为

，p

pi

1

i

1(ki

1)

(

ki

)

p第七章基本检索与周游方法§3、双连通分图4、把非双连通图改造为双连通图算法分图E1

for

每一个割点ａ

doＥ２

设Ｂ２，B２，...,Ｂk是包含结点a的双

Ｅ3

设vi是Ｂi的一个结点，且vi

ａ，1

i

k

Ｅ4

将（vi

，vi

+1），1

i

k，加到GＥ5

repeat19/40•例如：14226755第七章基本检索与周游方法§3、双连通分图383

310

9二、深度优先生成树1、定义定义1：按深度优先检索算法遍历图时的各个结点的次序，称为该结点的数，用DFN表示，

的路径，称为该图的深度优先生成树，简称DFN树。定义1：图G中除DFN树枝以外的边称为该树的逆边。第七章基本检索与周游方法§3、双连通分图例：DFN(1)=1，DFN(10)=4336458图

.15

b7910逆边1222/40第七章基本检索与周游方法§3、双连通分图2、性质•••性质1：若(u,v)∈E(G)对于DFS树T，则u是v的祖先或v是u的祖先证：若(u,v)∈E(G)（1）当(u,v)∈E(T)，必有u是v的父亲或v是u的父亲（2）当(u,v)

E(T

)不妨设DFN(u)<DFN(v)，根据DFS遍历算法，是先

u，而对u的检测至少要完v，才能完成，因此在树T中u是v的祖先，故交叉边不存在。交叉边不存在233645789第七章基本检索与周游方法§3、双连通分图23/40•性质2：一棵DFS生成树的根T是割点，当且仅当在T树中至少有两个儿子。证明：若有两个儿子，删除T，则这两个儿子将位于两个连通分支中，反之亦然。149256781233610

4578图7.15

b9第七章基本检索与周游方法§3、双连通分图24/40性质3：设u是除根以外的任一结点，那么u为割点的充要条件是至少有一个儿子w，通过w子孙路径和一条逆边到达不了u的祖先。证明：若这样的儿子w不存在，则u就不为割点u10

45u8图7.15

b9第七章基本检索与周游方法§3、双连通分图1、定义L(u)=min{DFN(u),min{L(w)|w是u的儿子}，min{DFN(w)|(u,w)是一条逆边}}，则L(u)是u通过子孙路径且至多加一条逆边所达到的最小DFN数,按树的前根遍历算法可以计算DFN数，按树的后根遍历算法可以计算L(u）值。例：DFN(1)=1DFN(10)=4149256781233610

4578图7.15

b9第七章基本检索与周游方法§3、双连通分图L(4)=1DFN(4)=2DFN(9)=5DFN(6)=8L(10)=4DFN(3)=3DFN(2)=6DFN(7)=9L(9)=5L(5)=6L(1)=126/40DFN(5)=7DFN(8)=10L(6)=8

L(8)=6L(2)=1

L(3)=1L(7)=6转下页27/40三、割点自动识别算法结论1：对DFN计算采用先根遍历（在递归调用前计算），对L值计算采用hou根遍历（在递归调用后计算）结论2：割点判别算法

1）u为根，则DFS树根至少有两个儿子

。2）u不为根，u至少有一个儿子w使得L(w)

≥DFN(u)第七章基本检索与周游方法§3、双连通分图w,则递归调用else

if

w≠v

then

L(u)min(L(u),DFN(w))//w不是v的父亲，endif

//（u，w)是一条逆边endifrepeat•1 DFN(u)

num;L(u)num;numnum+12 for

每个邻接于u的结点w

do3 if

DFN(w)=0

then

ART(w,u);L(u)min(L(u),L(w)) //还未5678•9

end

ART三、割点自动识别算法2、DFN和L值计算算法(DFS算法的应用）line procedure

ART(u,v)//u是深度优先检索的开始结点。在深度优先生成树中，u若有父亲，那么v就是它的父亲。假设数组DFN是全程量，并将其初始化为0。num是全程变量，被初始化为1。N是G

的节点数//global

DFN(n),L(n),num,n第七章基本检索与周游方法§3、双连通分图28/40••••••••••endif//注意：若v=w或DFN(W)>DFN(u)表明(u,w)是在栈中，现（u,v)是未在栈中的树枝或逆边//if

DFN(w)=0

then

ART(w,u)

if

L(w)

≥DFN(u)then

print(“为双连通分图”)；loop

(x,y)pop(s)；print(‘(‘,x,’,’,y,’)’)until

((x,y)=(u,w)

or

(x,y)=(w,u))endifL(u)min(L(u),L(w))else

if

w

≠v

then

L(u)min(L(u),DFN(w))

endifendifrepeatend

ART3、双连通分图输出算法Procedure

ART(u,v)//u若有父亲则为v//DFN(u)num

L(u)num

numnum+1for

每一个邻接于u的结点w

doif v≠w and

DFN(W)<DFN(u) then

push(u,v)1、树枝：如w未被 ，则DFN(w)=0,此时，DFN(w)<DFN(u)成立2、逆边：DFN(w)<DFN(u)成立表示u为割点，因为u的儿子w子孙路径加一条逆边到不了u的祖先，则一个双

分图形成了三、割点自动识别算法第七章基本检索与周游方法§3、双连通分图29/40第七章基本检索与周游方法§4、与或图一、问题的提出1、复杂问题分解为一系列子问题，又可由子问题的解导出原问题的解，称为问题化简，问题化简已经在工业调度、定理证明、机器学习、 系统等方面得到广泛应用，化简过程用图表示，则图称为与或图。2、解图是由与或图中一些可解结点组成的子图30/40例如：ABCDEABCDEEFGHI实例树与或树AEBCDF与或图第七章基本检索与周游方法§4、与或图二、与或树是否可解判定算法（算法7.12）Line

procedure

SOLVE(T)//T是一棵树其根为T的与/或树，T≠0。如果问题可解则返回1，否则返回0//：T是与结点：for

T

的每个儿子S

do6endififSOLVE(S)=0

then

return

(0)repeatreturn(1):else:for

T的每个儿子S

do//或结点//if

SOLVE(S)=1

then

return

(1)

endifrepeatreturn(0)1

case2

: T是终结点：if

T可解

then

return

(1）else return(0)endif••••••••••910111213endcaseend

SOLVE32/40第七章基本检索与周游方法§4、与或图33/40三、解树生成算法设问题的解可用函数F来表示，则一个已生成的结点，可用F去生成它的所有儿子，解树生成分为深度优先或宽度优先，当生成的结点，深度可能是无限时，则必须通过限制深度来解决。1、宽度优先生成解树算法7.13Line

procedure

BFGEN(T,F)//F生成T中的儿子结点；T是根结点。终止时，如果存在解树，则T是这解树的根//第七章基本检索与周游方法§4、与或图第七章基本检索与周游方法§4、与或图•1将队列Q初始化为空；

VT•2loop•3用F生成V的那些儿子//检测V//•••4if

V没有儿子then

标记V为不可解else①将V的所有不是叶子结点的儿子放入队列Q，将那些叶子结点分别标上可解或不可解;②把V的所有儿子加入树T;5endif•6call

ASOLVE(T)•7从树T删去所有标记为不可解的结点•8if

根结点T标记为可解then

return(T)endif•••910从队列Q中删去以下的所有结点：它们在T中曾有一个祖先被标记为不可解或者在T中有一个标记为可解的祖先if

Q为空then

print(‘no

solution’);stop

endif•11删去队列Q的第一个元素；设此结点是V•12repeat•13end

BFGEN34/40第七章基本检索与周游方法§5、对策树例:

拾火柴每次至多取3根，最少取一根，拿到最后一根为败者。654314323221A3

2

1

2

1B3A1

B

2

1

B

1

B

B

1

B

BAAAAAB下棋A下棋35/4036/40小。c1,c2

,c3

,...cd例:对于终局，则第七章基本检索与周游方法§5、对策树一、估价函数1、E(x)以数值形式表示弈者在棋局X下获胜机会的大是x棋局的儿子们所表示的棋局。2、V(x)是棋局x的代价函数•••x是叶子x是方形结点，即A下棋

x是园形结点，即B下棋E(x)

1,x对A是胜局1，x对A是负局V(x)

max{V(ci

)},

1id

min{V(ci

)}

1idE(x)，对弈者B走子37/403-∞-∞+∞-∞3+∞-12-∞0-32150-322310315927弈者A走子p1,12,1pp2,3

-1p2,4p3,1p3,2p3,3p3,4p3,5p3,6maxminmaxp4,5minmaxp5,15,2pp5,3p5,45,5pp5,6p5,7p5,8p5,9p5,10p5,11p4,1p4,2p4,3p4,4A的最优棋着3

p2,2A胜A负A胜A负A负p3,7图7.20第七章基本检索与周游方法§5、对策树易见：则若A走子，e(x)=E(x)•若B走子，4、通过至多有L步棋来计算V

'(x)的算法VE(x,L)算法7.14Procedure

VE(X,L)//通过至多向前看L着棋计算V

'(x)，弈者A使用的估价38/40V

'

(x)

i1idmax{V

'

(c

)}3、最大最小递归过程e(x)，x是叶子结点e(x)=-E(x)V

'

(x)=V(x)V

'

(x)=-V(x)第七章基本检索与周游方法§5、对策树函数是e(X)。为方便起见，假定由任一不是终局的棋局X开始，此棋局的合法棋着只允许将棋局转换成棋////周游第一棵//周游其余的局

C1,C2

,

,Cd39/40if

X是终局or

L=0

then return(e(X))

endifans

VE(C1,l

1)for

i2

to

d

do•ans

max(ans,

VE(C1,l

1))repeatreturn(ans)end

VE第七章基本检索与周游方法§5、对策树从A看：由于VE(C,L-1)=-V(ci因此，结果为max{v(ci)}从B看：由于VE(C,L-1)=V(ci)因此，结果为min{v(ci)}第七章基本检索与周游方法§5、对策树二、对策树的启发性搜索1、

-截断规则如果一个求最小值位置的值，判断为小于或等于它的），那么可以停止生成这父亲的当前估价值（设为•例如图7.20所示，V(p4,1

)个求最小值位置其余儿子的值。一旦确定，p3,3

的

值就变成3，V

(p5,5

)

p3,3的

值，则不用去生成

p5,6

的值。40/40如果一个求最小值位置的值，判断为小于或等于它的父亲的当前子的值。估价值（设为

），那么可以停止生成这个求最小值位置其余儿3,34,15,6p例如，V