7 基本检索与周游.ppt

第七章基本检索与周游 1 检索与周游检索 以某种方法检查给定的数据对象 找出满足某些给定性质的结点的过程称为检索 周游 当检索过程必须检索到数据对象的每一个结点时 则该检索过程称为周游 访问结点 当算法对一个结点的信息段进行处理时 称该结点被访问 2 二元树周游 遍历 1 周游次序在二元树的周游中 以D L R分别代表访问结点的信息段 访问左子树 访问右子树 则可能的顺序有 LDR 中根次序周游 中根遍历 LRD 后根次序周游 后根遍历 DLR 先根次序周游 先根遍历 RDL 逆中根次序周游 RLD 逆后根次序周游 DRL 逆先根次序周游 2 二元树周游算法 中根次序周游算法7 1中根次序周游的递归表示procedureINORDER T T是一棵二元树 T的每个结点有三个信息段 LCHILD DATA RCHILD ifT 0thencallINORDER LCHILD T callVISIT T callINORDER RCHILD T endifendINORDER 先根次序周游算法7 2先根次序周游的递归表示procedurePREORDER T T是一棵二元树 T的每个结点有三个信息段 LCHILD DATA RCHILD ifT 0thencallVISIT T callPREORDER LCHILD T callPREORDER RCHILD T endifendPREORDER 后根次序周游算法7 2后根次序周游的递归表示procedurePOSTORDER T T是一棵二元树 T的每个结点有三个信息段 LCHILD DATA RCHILD ifT 0thencallPOSTORDER LCHILD T callPOSTORDER RCHILD callVISIT T endifendPREORDER 左图中 中根次序周游的输出是 FDHGIBEAC先根次序周游的输出是 ABDFGHIEC后根次序周游的输出是 FHIGDEBCA 注 一棵二元树可由中根遍历序列 先根遍历序列 或中根遍历序列 后根遍历序列唯一确定 但不能由先根遍历序列 后根遍历序列唯一确定 如已知一棵二元树的中根遍历次序是 DGBEAFHC先根遍历次序是 ABDGECFH则这棵二元树唯一确定如下 定理7 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 3 树的周游1 树的子树顺序无序 有序2 森林F的周游 树的先根次序周游A 若F为空 则返回B 访问F的第一棵树的根C 按树先根次序周游F的第一棵树的子树D 按树先根次序周游F的其它树 树的中根次序周游 树的后根次序周游 树转换成二元树方法 设有一棵树T 它的根是T1 人为安排它的子树有序且设为T11 T12 T1K 用T1做二元树的根 T11做T1的左子树 然后T1i做T1i 1的右子树 2 i k 设T是由森林F转换成的二元树则 T的先根次序周游相当于按树先根次序周游访问FT的中根次序周游相当于按树中根次序周游访问F对T的后根次序周游无类似的自然对应 4 图的检索和周游4 1宽度优先检索和周游1 宽度优先检索 从结点v开始 给v标上已到达 或访问 标记 此时称结点v还没有被检测 而当算法访问了邻接于某结点的所有结点时 称该结点被检测了 访问邻接于v且尚未被访问的所有结点 这些结点是新的未被检测的结点 将这些结点依次放置到一未检测结点表 队列Q 中 末端插入 标记v已被检测 若未检测结点表为空 则算法终止 否则 从未检测结点表的表头取一结点作为下一个待检测结点 重复上述过程 宽度优先算法 自始至终一直通过已找到和未找到顶点之间的边界向外扩展 就是说 算法首先搜索和v距离为k的所有顶点 然后再去搜索和v距离为k 1的其他顶点 算法7 6宽度优先检索算法procedureBFS v 宽度优先检索G 它从结点v开始 所有已访问结点被标记为VISITED i 1 VISITED v 1 u v VISITED n 是一个标示数组 初始值VISITED i 0 1 i n 将Q初始化为空 Q是未检测结点的队列 loopfor邻接于u的所有结点wdoifVISITED w 0then w未被检测 callADDQ w Q ADDQ将w加入到队列Q的末端 VISITED w 1 同时标示w已被访问 endifrepeatifQ为空thenreturnendifcallDELETEQ u Q DELETEQ取出队列Q的表头 并赋给变量u repeatendBFS 定理7 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在这之前未被访问 则此刻将被访问到 由上 定理得证 定理7 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 这一结论与使用邻接表或邻接矩阵无关 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 使用邻接矩阵表示 2 宽度优先周游算法7 7宽度优先图的周游算法procedureBFT G n G的宽度优先周游 intVISITED n fori 1tondoVISITED i 0repeatfori 1tondo 反复调用BFS ifVISITED i 0thencallBFS i endifrepeatendBFT注 若G是无向连通图或强连通有向图 则一次调用BFS即可完成对T的周游 否则 需要多次调用 图周游算法的应用 判定图G的连通性 若调用BFS的次数多于1次 则G为非连通的 生成图G的连通分图 一次调用BFS中可以访问到的所有结点及连接这些结点的边构成一个连通分图 无向图自反传递闭包矩阵A 宽度优先生成树向前边 BFS中由u达到未访问结点w的边 u w 称为向前边 记T是BFS中所处理的所有向前边集合 宽度优先生成树 若G是连通图 则BFS终止时 T构成一棵生成树 定理7 4修改算法BFS 在第1行和第6行分别增加语句T 和T T u w 修改后的算法称为BFS 若v是无向图中任一结点 调用BFS 算法终止时 T中的边组成G的一棵生成树 procedureBFS v VISITED v 1 u vT 将Q初始化为空loopfor邻接于u的所有结点wdoifVISITED w 0then w未被检测 T T u w callADDQ w Q ADDQ将w加入到队列Q的末端 VISITED w 1 同时标示w已被访问 endifrepeatifQ为空thenreturnendifcallDELETEQ u Q DELETEQ取出队列Q的表头 并赋给变量u repeatendBFS 证明 若G是n个结点的连通图 则这n个结点都要被访问 除起始点v以外 其它n 1个结点都将被放且仅将被放到队列Q上一次 从而T将正好包含n 1条边 且这些边是各不相同的 即T是关于n个结点n 1边的无向图 同时 对于连通图G T将包含由起始结点v到其它结点的路径 所以T是连通的 则T是G的一棵生成树 注 对于n个结点且正好有n 1条边的连通图是一棵树 4 2深度优先检索和周游1 深度优先检索从结点v开始 首先给v标上已到达 或访问 标记 同时中止对v的检测 并开始对邻接于v且尚未被访问的结点u检测 在这样的u均被检测后 再恢复对v的检测 当所有可到达的结点全部被检测完毕后 算法终止 算法7 8图的深度优先检索procedureDFS v 已知一个n结点的无向 或有向 图G V E 以及初值已置为零的数组VISITED 1 n 这个算法访问由v可以到达的所有结点 VISITED v 1for邻接于v的每个结点wdoifVISITED w 0thencallDFS w endifrepeatendDFS 深度优先搜索 depth firstsearch 简称DFS 基本思想 访问一个顶点V 然后访问该顶点邻接到的未被访问过的顶点V 再从V 出发递归地按照深度优先的方式周游 当遇到一个所有邻接于它的顶点都被访问过了的顶点U时 则回到已访问顶点序列中最后一个拥有未被访问的相邻顶点的顶点W 再从W出发递归地按照深度优先的方式周游 最后 当任何已被访问过的顶点都没有未被访问的相邻顶点时 则周游结束 性质 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的连通性 连通分图 无向图自反传递闭包矩阵 深度优先生成树 深度优先生成树算法procedureDFS v T VISITED v 1for邻接于v的每个结点wdoifVISITED w 0thenT T u w callDFS w endifrepeatendDFS 4 3BFS DFS D Search算法比较BFS 使用队列保存未被检测的结点 结点按照宽度优先的次序被访问和进 出队列 DFS 使用栈保存未被检测的结点 结点按照深度优先的次序被访问并依次被压入栈中 并以相反的次序出栈进行新的检测 D Search 使用栈保存未被检测的结点 结点按照宽度优先的次序被访问并被依次压入栈中 然后以相反的次序出栈进行新的检测 新的检测结点是最新被访问但未被检测的结点 BFS访问序列 12345678DFS访问序列 12485637D Search访问序列 12367845检测序列 13785462 7 3双连通分图与深度优先检索 通信网 图中结点表示通信站 边表示通信线路 关节点 无向连通图中某结点a以及a相关联的所有边删除 得到两个或两个以上的非空分图 则a称为G的关节点 双连通图 如果无向连通图G不含关节点 则称G为双连通图 目标 1 设计一个算法测试某个连通图是否双连通2 不是双连通的 找出所有的关节点3 确定一个适当的边集加到G上 将其变为一个双连通图概念 双连通分图 最大双连通子图称为双连通分图 双连通分图性质 1 两个双连通分图至多有一个公共结点 且这个结点是关节点2 任何一条边不可能同时在两个不同的连通分图中 因为这需要两个公共结点 因此 得到把图G变成双连通图的方法 For每一个关节点ado设B1 B2 B3 BK是包含结点a的双连通分图设Vi是Bi的一个结点 且Vi a 1 i k将 vi vi 1 1 i k 加到GRepeat图5 11中关节点3 增加边 4 10 10 9 关节点2 增加边 1 5 关节点5 增加边 6 7 将G变为双连通图 注意 此方法增加的总的边数比将G变成双连通图所需要的最小边数大 1 4 3 10 9 2 5 6 7 8 1 2 3 4 5 6 7 8 9 10 图7 11中图的一棵深度优先生成树 利用深度优先检索解决图的关节点与双连通分图的识别问题 深度优先数 DFN DFN 1 1 DFN 2 6树边 实线边 代表生成树的边逆边 虚线边 代表不在生成树中的边 深度优先生成树的性质 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是一个关节点 各结点的最低深度优先数是L 1 10 1 1 1 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 计算L u 的方法 按后根次序访问深度优先生成树的结点确定G的关节点的工作 1 完成对G的深度优先搜索 产生G的深度优先生成树T2 按后根次序访问树T的结点 算法5 11计算DFN和L的算法ProcedureART u v u是开始结点 在深度优先生成树中 u若有父亲 则v是其父亲 Num 1 GlobalDFN n L n num nDFN u num L u num num num 1For每个邻接于u的结点wdoifDFN w 0thencallART w u 还没访问w L u min L u L w elseifw vthenL u min L u DFN w endifendifRepeatEndART 算法分析 设图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不适用 7 4与 或图 很多复杂问题很难或没法直接求解 但可以分解成一系列 类型不同 的子问题 而这些子问题又可反复细分成一些更小的子问题 一直到分成一些可普通求解的 相当基本的问题为止 然后让这些分解成的子问题的全部或部分解在导出原问题的解 例 洗衣服问题某人一星期洗一次衣服 要做的事可以分为收集脏衣服 洗衣服 干燥 熨衣服 叠好衣服并放入衣柜 其中 某些事可采用不同的方法 如洗衣服可以是手洗或者是机器洗 干燥可以是晾干或者机器烘干 对于上述问题 可以用与 或图来表示 与 或图是一个有向图 结点表示问题 一个结点的子孙代表与其相关联的子问题 用一条弧将那些可以联合导出其解的子结点连结在一起 如下图 a 中表示问题A可以通过求解子问题B和C来解出 或者可由单个求解子问题D或E来解出 为使结点含义单一化 即它的解或者需要求解它所有的子孙得到 或者求解它的一个子孙便可得到 通过引入图 b 中虚结点可达到此目的 前一类结点称为与结点 后一类结点称为或结点 下图为洗衣服问题的与 或图 图中 没有子孙的结点是终结点 它代表基本问题并标记上可解或不可解 可解的终结点用方框表示 洗衣服问题 收集脏衣服 洗 干燥 熨 叠好并归堆 手洗 机器洗 适当的更换 装入并开始 晾干 机器烘干 适当的更换 装入并开始 图7 17洗衣服问题对应的与 或图 概念 解图是由与 或图中一些可解结点组成的子图 它表示对问题求解 根据问题的与 或树判断该问题是否可解方法 对与 或树作后根次序周游就可得出答案 在算法执行过程中 一旦发现某与结点的一个儿子结点不可解 或者发现某或结点的一个儿子结点可解 就立即终止该算法 这可减少算法的工作量且对结果无任何影响 判断与 或树是否可解的算法ProcedureSOLVE T T是一棵其根为T的与 或树 T 0 如果问题可解则返回1 否则返回0 CASE T是终结点 ifT可解thenreturn 1 elsereturn 0 endif T是与结点 forT的每个儿子SdoifSOLVE S 0thenreturn 0 endifrepeatreturn 1 else forT的每个儿子Sdo 或结点 ifSOLVE S 1thenreturn 1 endifrepeatreturn 0 EndcaseEndSOLVE 目标 求出问题的解树 即不仅需要知道此问题是否可解 而且希望知道如果问题可解 那么问题的解是由哪些基本问题 沿着什么样的途径所导出的 方法 在生成与 或树结点算法的基础上加上一些对结点可解性的判断和删除措施而获得 说明 1 假定问题的分解方法用函数F