算法设计

2020/2/241第四章基本检索与周游1.检索与周游检索：以某种方法查找给定的数据对象，找出满足某些给定性质的结点的过程称为检索周游：当检索过程必须检索到数据对象的每一个结点时，则该检索过程称为周游访问结点：当算法对一个结点的信息段进行处理时，称该结点被访问。2020/2/2422.二元树周游（遍历）1）周游次序在二元树的周游中，以D、L、R分别代表访问结点的信息段、访问左子树、访问右子树。则可能的顺序有：★LDR：中根次序周游（中根遍历）★LRD：后根次序周游（后根遍历）★DLR：先根次序周游（先根遍历）★RDL：逆中根次序周游★RLD：逆后根次序周游★DRL：逆先根次序周游先左后右先右后左2020/2/2432）二元树周游算法⑴中根次序周游算法4.1中根次序周游的递归表示procedureINORDER(T)//T是一棵二元树。T的每个结点有三个信息段:LCHILD,DATA,RCHILD//ifT≠0thencallINORDER(LCHILD(T))callVISIT(T)callINORDER(RCHILD(T))endifendINORDER2020/2/244⑵先根次序周游算法4.2先根次序周游的递归表示procedurePREORDER(T)//T是一棵二元树。T的每个结点有三个信息段:LCHILD,DATA,RCHILD//ifT≠0thencallVISIT(T)callPREORDER(LCHILD(T))callPREORDER(RCHILD(T))endifendPREORDER2020/2/245⑵后根次序周游算法4.3后根次序周游的递归表示procedurePOSTORDER(T)//T是一棵二元树。T的每个结点有三个信息段:LCHILD,DATA,RCHILD//ifT≠0thencallPOSTORDER(LCHILD(T))callPOSTORDER(RCHILD(T))callVISIT(T)endifendPREORDER2020/2/246注：一棵二元树可由中根遍历序列＋先根遍历序列、或中根遍历序列＋后根遍历序列唯一确定。但不能由先根遍历序列＋后根遍历序列唯一确定。如已知一棵二元树的中根遍历次序是：DGBEAFHC先根遍历次序是：ABDGECFH则这棵二元树唯一确定如下:ABDEGCFH2020/2/247定理4.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)。d≤n，所以s(n)=Θ(n)。2020/2/2484.图的检索和周游1)宽度优先检索①从结点v开始，给v标上已到达或访问标记——此时称结点v还没有被检测，而当算法访问了邻接于某结点的所有结点时，称该结点被检测了。②访问邻接于v且目前尚未被访问的所有结点——这些结点是新的未被检测的结点。将这些结点依次放置到一未检测结点表(队列Q)中（末端插入）。③标记v已被检测。④若未检测结点表为空，则算法终止；否则⑤从未检测结点表的表头取一结点作为下一个待检测结点，重复上述过程。2020/2/249算法4.4宽度优先检索算法procedureBFS(v)//宽度优先检索G，它从结点v开始。所有已访问结点被标记为VISITED(i)=1。//VISITED(v)←1//VISITED(n)是一个标示数组，初始值u←vVISITED(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//repeatendBFS2020/2/2410定理4.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被访问到：由上，定理得证2020/2/2411定理4.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))当v与其余的n-1个结点都有边相连时，邻接于v的全部n-1个结点都将在“同一时刻”被放在队列上，故Q至少也应有Ω(n)的空间。同时，VISITED(n)本身需要Θ(n)的空间。所以s(n,e)=Θ(n)——这一结论与使用邻接表或邻接矩阵无关。2020/2/24122)时间分析●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)●如果v可到达所有结点，则将检测到V中所有的结点，所以以上两种情况所需的总时间至少应是Ω(n+e)和Ω(n2)。所以，t(n,e)=Θ(n+e)使用邻接表表示或，t(n,e)=Θ(n2)使用邻接矩阵表示证毕2020/2/24132)宽度优先周游算法4.5宽度优先周游算法procedureBFT(G,n)//G的宽度优先周游//intVISITED(n)fori←1tondoVISITED(i)←0repeatfori←1tondo//反复调用BFS//ifVISITED(i)=0thencallBFS(i)endifrepeatendBFT注：若G是无向连通图或强连通有向图，则一次调用BFS即可完成对T的周游。否则，需要多次调用。2020/2/2414图周游算法的应用●判定图G的连通性：若调用BFS的次数多于1次，则G为非连通的●生成图G的连通分图：一次调用BFS中可以访问到的所有结点及连接这些结点的边构成一个连通分图。●宽度优先生成树向前边：BFS中由u到达未访问结点w的边(u,w)称为向前边。记T是BFS中所处理的所有向前边集合。宽度优先生成树：若G是连通图，则BFS终止时，T构成一棵生成树。12345678无向图G12345678G的宽度优先生成树2020/2/2415定理4.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*2020/2/2416证明：若G是n个结点的连通图，则这n个结点都要被访问。除起始点v以外，其它n-1个结点都将被放且仅将被放到队列Q上一次，从而T将正好包含n-1条边，且这些边是各不相同的。即T是关于n个结点n-1边的无向图。同时，对于连通图G，T将包含由起始结点v到其它结点的路径，所以T是连通的。则T是G的一棵生成树。注：对于n个结点且正好有n-1条边的连通图是一棵树。2020/2/24174.2深度优先检索和周游1)深度优先检索从结点v开始，首先给v标上已到达（或访问）标记，同时中止对v的检测，并开始对邻接于v且尚未被访问的结点u检测。在这样的u均被检测后，再恢复对v的检测。当所有可到达的结点全部被检测完毕后，算法终止。算法4.6图的深度优先检索procedureDFS(v)//已知一个n结点的无向（或有向）图G＝(V,E)以及初值已置为零的数组VISITED(1:n)。这个算法访问由v可以到达的所有结点。//VISITED(v)←1for邻接于v的每个结点wdoifVISITED(w)＝0thencallDFS(w)endifrepeatendDFS2020/2/2418性质：①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的连通性②连通分图③无向图自反传递闭包矩阵④深度优先生成树2020/2/2419深度优先生成树算法T←ΦprocedureDFS*(v,T)VISITED(v)←1for邻接于v的每个结点wdoifVISITED(w)＝0thenT←T∪{(u,w)}callDFS(w,T)endifrepeatendDFS*2020/2/242012345678无向图G12345678G的宽度优先生成树12345678G的深度优先生成树1,2,4,8,5,6,3,71,2,3,4,5,6,7,82020/2/24214.3BFS、DFS、D_Search算法比较BFS：使用队列保存未被检测的结点。结点按照宽度优先的次序被访问和进、出队列。DFS：使用栈保存未被检测的结点，结点按照深度优先的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。D_Search：使用栈保存未被检测的结点，结点按照宽度优先的次序被访问并被依次压入栈中，然后以相反的次序出栈进行新的检测。新的检测结点是最新被访问但未被检测的结点。12345678无向图G2020/2/24224.3BFS、