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

第五章 基本检索与周游方法 一般方法 许多问题的解法涉及到对二元树、树和图的处理。这种处理往拄要求我们确定满足某一性质的那些给定数据对象中的一个结点或结点子集。 这通常在数据对象中以检索的方式来进行。 当这种植索必须包括对检索的数据对象的每一个结点进行检查叭就把它称之为周游。 一般方法 这些方法分三类： 前二类只能分别适用于二元树和树。这些方法将检查给定数据对象中的每一个结点。因此这些方法称为周游方法。 第三类是适用于图的一些方法(也适用于树和二元树)。但这些检索方法不能检查所有的结点，因此只称为检索方法。 双连通分图和深度优先检索 几个基本概念 关节点： 如果把无向连通图G中某结点a以及与a相关联的所有边删去，得到二个或二个以上的非空分图，那末结点a就称为G的关节点。 双连通图： 如果无向连通图G根本不包含关节点，则称G为双连通图。 双连通分图： 最大双连通子图 把图G变成一个双连通图 E1 for每一个关节点 a do E2 设B1,B2,…,Bk是包含结点a的双 连通分图 E3 设vi是Bi的一个结点 E4 将(vi,vi+1)加到G E5 repeat 把图G变成一个双连通图 关节点和双连通分图的识别 几个概念： 深度优先数 树边 逆边 交叉边 关节点和双连通分图的识别 关节点的识别 两条重要的性质： 若(u,v)是G中任一条边，则相对于深度优先生成树T，或者u是v的祖先，或者v是u的祖先。 当且仅当一棵深度优先生成树的根结点至少有两个儿子时，此根结点是关节点，如果u是除根外的任一结点，那么当且仅当由u的每一个儿子w出发，若只通过w的子孙组成的一条路径和一条逆边就可到达u的某个祖先时，则u就不是关节点。 关节点的识别 对没给结点u，有L(u)定义如下： L(u)={DFN(u),min{L(w)|w是u的儿子} min{DFN(w)|(u,w)是一条逆边}} 显然，L(u)是u通过一条子孙路径且至多后随一条逆边所可能到达的最低深度优先数。 连通分图的识别 要是在第3行调用ART之后有L(w)＞L(u)，就可断定u或者是根，或者是关节点。 不管u是否为根，也不管u有一个或是多个儿子，将边(u，w)和对ART的这次调用期间遇到的所有树边和逆边加在一起(除了包含在子树w中其它双连通分图的边以外)，构成一个双连通分图。 对策树 拾火柴棍游戏 假定盘上放有n支火柴，由奕者A和B两个人参加比赛。 比赛规则是：两名奕者轮流从盘中取走火柴，每次从盘中取走1,2或3支火柴均为合法着。否则，为非法着；拿走盘中最后一支火柴的奕者则负了这一局，当然另一名奕者则胜这一局。 对策树 任何时刻盘中剩下的火柴数表示此时刻的棋局。 拾火柴棍游戏在任一时刻的状态则由此时的棋局和轮到走下一着的奕者一起所决定。 结局是表示胜局、负局或和局情况的棋局。其它棋局都是非终止棋局。 棋居序列C1,C2,…,Cm称为有效期局序列： C1是开始棋局； Ci(0im)是非终止棋局； 由Ci得到Ci+1是走下述棋着实现的：若i是奇数，则A者走一合法棋着；若i是偶数，则B者走一合法棋着。 对策树 估价函数E(X) E(X)以数值形式表示弈者则棋局X下获胜机会的大小。 对于对策树结点比较少的的搏弈游戏，E(X)为： E(X)={1,-1| 若X为胜局，E(X)=1， 若X为负局，E(X)=-1} 一般情况： * * 几个概念：连通图、无向连通图、双连通图、关节点、双连通分图 10 9 4 1 3 2 5 8 7 6 1 5 4 2 3 A B 10 9 4 1 3 2 5 8 7 6 双连通分图 深度优先生成树 V(X)= max{V(ci)} 若X是方形结点，1≤i≤d min{V(ci)} 若X是圆形结点，1≤i≤d *