计算机算法基础(第五章).ppt

第五章基本检索与周游,1.检索与周游检索：以某种方法检查给定的数据对象，找出满足某些给定性质的结点的过程称为检索周游：当检索过程必须检索到数据对象的每一个结点时，则该检索过程称为周游访问结点：当算法对一个结点的信息段进行处理时，称该结点被访问。,2.二元树周游（遍历）1）周游次序在二元树的周游中，以D、L、R分别代表访问结点的信息段、访问左子树、访问右子树。则可能的顺序有：LDR：中根次序周游（中根遍历）LRD：后根次序周游（后根遍历）DLR：先根次序周游（先根遍历）RDL：逆中根次序周游RLD：逆后根次序周游DRL：逆先根次序周游,2）二元树周游算法中根次序周游算法5.1中根次序周游的递归表示procedureINORDER(T)/T是一棵二元树。T的每个结点有三个信息段:LCHILD,DATA,RCHILD/ifT0thencallINORDER(LCHILD(T)callVISIT(T)callINORDER(RCHILD(T)endifendINORDER,先根次序周游算法5.2先根次序周游的递归表示procedurePREORDER(T)/T是一棵二元树。T的每个结点有三个信息段:LCHILD,DATA,RCHILD/ifT0thencallVISIT(T)callPREORDER(LCHILD(T)callPREORDER(RCHILD(T)endifendPREORDER,后根次序周游算法5.2后根次序周游的递归表示procedurePOSTORDER(T)/T是一棵二元树。T的每个结点有三个信息段:LCHILD,DATA,RCHILD/ifT0thencallPOSTORDER(LCHILD(T)callPOSTORDER(RCHILD)callVISIT(T)endifendPREORDER,左图中：中根次序周游的输出是：FDHGIBEAC先根次序周游的输出是：ABDFGHIEC后根次序周游的输出是：FHIGDEBCA,注：一棵二元树可由中根遍历序列先根遍历序列、或中根遍历序列后根遍历序列唯一确定。但不能由先根遍历序列后根遍历序列唯一确定。如已知一棵二元树的中根遍历次序是：DGBEAFHC先根遍历次序是：ABDGECFH则这棵二元树唯一确定如下:,定理5.1当输入的树T有n0个结点时，设t(n)和s(n)分别表示这些周游算法中的任意一个算法所需要的最大时间和空间。如果访问一个结点所需要的时间和空间是(1)，则t(n)=(n),s(n)=(n)。证明：时间：由于已知访问一个结点所需要的时间是(1)，故可用常数c1限界。设T的左子树中的结点数是n1，则t(n)有：t(n)=maxn1t(n1)+t(n-n1-1)+c1n1其中，t(0)c1。归纳法证明t(n)c2n+c1，其中c2是一使得c22c1的常数。1)当n=0时，成立2)假定当n=0,1,m-1时均成立。则当n=m时有，设T是一棵有m个结点的树，T左子树结点数为n1,则t(n)maxn1t(n1)+t(n-n1-1)+c1maxn1c2n1+c1+c2(n-n1-1)+c1+c1maxn1c2n+3c1-c2c2n+c1同理，存在c2和c1有t(n)c2n+c1。所以t(n)=(n)空间：若T的深度为d，则所需空间为(d),dn，所以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的右子树，2ik。,设T是由森林F转换成的二元树则：T的先根次序周游相当于按树先根次序周游访问FT的中根次序周游相当于按树中根次序周游访问F对T的后根次序周游无类似的自然对应,4.图的检索和周游4.1宽度优先检索和周游1)宽度优先检索从结点v开始，给v标上已到达（或访问）标记此时称结点v还没有被检测，而当算法访问了邻接于某结点的所有结点时，称该结点被检测了。访问邻接于v且尚未被访问的所有结点这些结点是新的未被检测的结点。将这些结点依次放置到一未检测结点表(队列Q)中（末端插入）。标记v已被检测。若未检测结点表为空，则算法终止；否则从未检测结点表的表头取一结点作为下一个待检测结点，重复上述过程。,算法5.6宽度优先检索算法procedureBFS(v)/宽度优先检索G，它从结点v开始。所有已访问结点被标记为VISITED(i)=1。/VISITED(v)1;uv/VISITED(n)是一个标示数组，初始值VISITED(i)=0,1in/将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,定理5.2算法BFS可以访问由v可到达的所有结点证明：设G=(V,E)是一个(有向或无向)图，vV。归纳法证明定理结论正确。记d(v,w)是由v到达某一可到达结点w(wV)的最短路径长度。若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被访问到。假设uv,且r1。根据BFS的处理规则，u将在被访问之前的某个时刻被放到未被检测结点队列Q上，而在另一时刻u将从队列Q中移出。此时，所有邻接于u且尚未被访问的结点将被访问。若结点w在这之前未被访问，则此刻将被访问到。由上，定理得证,定理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，wV且wv,仅在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)宽度优先周游算法5.7宽度优先图的周游算法procedureBFT(G,n)/G的宽度优先周游/intVISITED(n)fori1tondoVISITED(i)0repeatfori1tondo/反复调用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构成一棵生成树。,定理5.4修改算法BFS，在第1行和第6行分别增加语句T和TT(u,w)。修改后的算法称为BFS*。若v是无向图中任一结点，调用BFS*，算法终止时，T中的边组成G的一棵生成树。procedureBFS*(v)VISITED(v)1;uvT将Q初始化为空loopfor邻接于u的所有结点wdoifVISITED(w)=0then/w未被检测/TT(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的检测。当所有可到达的结点全部被检测完毕后，算法终止。算法5.8图的深度优先检索procedureDFS(v)/已知一个n结点的无向（或有向）图G(V,E)以及初值已置为零的数组VISITED(1:n)。这个算法访问由v可以到达的所有结点。/VISITED(v)1for邻接于v的每个结点wdoifVISITED(w)0thencallDFS(w)endifrepeatendDFS,性质：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)TVISITED(v)1for邻接于v的每个结点wdoifVISITED(w)0thenTT(u,w)callDFS(w)endifrepeatendDFS*,4.3BFS、DFS、D_Search算法比较BFS：使用队列保存未被检测的结点。结点按照宽度优先的次序被访问和进、出队列。DFS：使用栈保存未被检测的结点，结点按照深度优先的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。D_Search：使用栈保存未被检测的结点，结点按照宽度优先的次序被访问并被依次压入栈中，然后以相反的次序出栈进行新的检测。新的检测结点是最新被访问但未被检测的结点。,BFS检测序列：12345678DFS检测序列：12485637D_Search检测序列：13785462,5.3双连通分图与深度优先检索,【通信网】图中结点表示通信站，边表示通信线路。,关节点：无向连通图中某结点a以及a相关联的所有边删除，得到两个或两个以上的非空分图，则a称为G的关节点。双连通图：如果无向连通图G不含关节点，则称G为双连通图。,目标：1.设计一个算法测试某个连通分图是否双连通2.不是双连通的，找出所有的关节点3.确定一个适当的边集加到G上，将其变为一个双连通图概念：双连通分图：最大双连通子图称为双连通分图,双连通分图性质：1.两个双连通分图至多有一个公共结点，且这个结点是关节点2.任何一条边不可能同时在两个不同的连通分图中（因为这需要两个公共结点）因此，得到把图G变成双连通图的方法：For每一个关节点ado设B1,B2,B3,BK是包含结点a的双连通分图设Vi是Bi的一个结点，且Via,1ik将（vi,vi+1），1ik,加到GRepeat图5.11中关节点3：增加边（4，10），（10，9）关节点2：增加边（1，5）关节点5：增加边（6，7）将G变为双连通图,1,4,3,10,9,2,5,6,7,8,1,2,3,4,5,6,7,8,9,10,图5.11中图的一棵深度优先生成树,利用深度优先检索解决图的关节点与双连通分图的识别问题,深度优先数（DEN）：DEN(1)=1,DEN(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)=minDFN(u),minL(W)|W是u的儿子,minDFN(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;numnum+1For每个邻接于u的结点wdoifDFN(w)=0thencallART(w,u)/还没访问w/L(u)min(L(u),L(w)elseifwvthenL(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)DFN(u)，就可断定u或者是根，或者是关节点。不管u是否是根，也不管u有一个或是多个儿子，将边(u,w)和对ART的这次调用期间遇到的所有树边和逆边加在一起，构成一个双连通分图。对ART作一些修改即可生成该算法，算法略,注意：上述算法要在相对于生成树，所给定的图没有交叉边。而相对于宽度优先生成树，一些图可能有交叉边，此时算法ART对BFS不适用。,5.4与/或图,很多复杂问题很难或没法直接求解，但可以分解成一系列（类型不同）的子问题，而这些子问题又可反复细分成一些更小的子问题，一直到分成一些可普通求解的，相当与基本的问题为止。然后让这些分解成的子问题的全部或部分解在导出原问题的解。例：洗衣服问题某人一星期洗一次衣服，要做的事可以分为收集脏衣服、洗衣服、干燥、熨衣服、叠好衣服并放入衣柜。其中，某些事可采用不同的方法，如洗衣服可以是手洗或者是机器洗。干燥可以是晾干或者机器烘干。,对于上述问题，可以用与/或图来表示。与/或图是一个有向图：结点表示问题，一个结点的子孙代表与其相关联的子问题。用一条弧将那些可以联合导出其解的子结点连结在一起。如下图(a)中表示问题A可以通过求解子问题B和C来解出，或者可由单个求解子问题D或E来解出。为使结点含义单一化，即它的解或者需要求解它所有的子孙得到，或者求解它的一个子孙便可得到，通过引入图(b)中虚结点可达到此目的。前一类结点称为与结点，后一类结点称为或结点。,下图为洗衣服问题的与/或图。图中，没有子孙的结点是终结点，它代表基本问题并标记上可解或不可解。可解的终结点用方框表示。,洗衣服问题,收集脏衣服,洗,干燥,熨,叠好并归堆,手洗,机器洗,适当的更换,装入并开始,晾干,机器烘干,适当的更换,装入并开始,图5.17洗衣服问题对应的与/或图,概念：解图是由与/或图中一些可解结点组成的子图，它表示对问题求解。根据问题的与/或树判断该问题是否可解方法：对与/或树作后根次序周游就可得出答案。在算法执行过程中，一旦发现某与结点的一个儿子结点不可解，或者发现某或结点的一个儿子结点可解，就立即终止该算法，这可减少算法的工作量且对结果无任何影响。,判断与/或树是否可解的算法ProcedureSOLVE(T)/T是一棵其根为T的与/或树，T0。如果问题可解则返回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来表示，即用F生成结点的所有儿子2.生成结点的次序既可按宽