搜索
2020/1/13第五章基本检索与周游1.检索与周游(基本概念、一般方法)检索：以某种方法检查给定的数据对象，找出满足某些给定性质的结点的过程称为检索周游：当检索过程必须检索到数据对象的每一个结点时，则该检索过程称为周游访问结点：当算法对一个结点的信息段进行处理时，称该结点被访问。2020/1/132.二元树周游（遍历）1）周游次序在二元树的周游中，以D、L、R分别代表访问结点的信息段、访问左子树、访问右子树。则可能的顺序有：★LDR：中根次序周游（中根遍历）★LRD：后根次序周游（后根遍历）★DLR：先根次序周游（先根遍历）★RDL：逆中根次序周游★RLD：逆后根次序周游★DRL：逆先根次序周游2020/1/132）二元树周游算法⑴中根次序周游算法5.1中根次序周游的递归表示procedureINORDER(T)//T是一棵二元树。T的每个结点有三个信息段:LCHILD,DATA,RCHILD//ifT≠0thencallINORDER(LCHILD(T))callVISIT(T)callINORDER(RCHILD(T))endifendINORDER2020/1/13⑵先根次序周游算法5.2先根次序周游的递归表示procedurePREORDER(T)//T是一棵二元树。T的每个结点有三个信息段:LCHILD,DATA,RCHILD//ifT≠0thencallVISIT(T)callPREORDER(LCHILD(T))callPREORDER(RCHILD(T))endifendPREORDER2020/1/13⑵后根次序周游算法5.2后根次序周游的递归表示procedurePOSTORDER(T)//T是一棵二元树。T的每个结点有三个信息段:LCHILD,DATA,RCHILD//ifT≠0thencallPOSTORDER(LCHILD(T))callPOSTORDER(RCHILD(T))callVISIT(T)endifendPREORDER2020/1/13ABCDEFGHI左图中：中根次序周游的输出是：FDHGIBEAC先根次序周游的输出是：ABDFGHIEC后根次序周游的输出是：FHIGDEBCA2020/1/13注：一棵二元树可由中根遍历序列＋先根遍历序列、或中根遍历序列＋后根遍历序列唯一确定。但不能由先根遍历序列＋后根遍历序列唯一确定。如已知一棵二元树的中根遍历次序是：DGBEAFHC先根遍历次序是：ABDGECFH则这棵二元树唯一确定如下:ABDEGCFH2020/1/13树转换成二元树方法：设有一棵树T(它的根是T1)，人为安排它的子树有序且设为T11,T12,…,T1K。用T1做二元树的根，T11做T1的左子树，然后T1i做T1i-1的右子树，2≤i≤k。T1T11T12T1K…T1T11T12T1K…设T是由森林F转换成的二元树则：T的先根次序周游相当于按树先根次序周游访问FT的中根次序周游相当于按树中根次序周游访问F对T的后根次序周游无类似的自然对应2020/1/134.图的检索和周游4.1宽度优先检索和周游1)宽度优先检索①从结点v开始，给v标上已到达（或访问）标记——此时称结点v还没有被检测，而当算法访问了邻接于某结点的所有结点时，称该结点被检测了。②访问邻接于v且尚未被访问的所有结点——这些结点是新的未被检测的结点。将这些结点依次放置到一未检测结点表(队列Q)中（末端插入）。③标记v已被检测。④若未检测结点表为空，则算法终止；否则⑤从未检测结点表的表头取一结点作为下一个待检测结点，重复上述过程。2020/1/13算法5.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//repeatendBFS2020/1/13定理5.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在这之前未被访问，则此刻将被访问到。由上，定理得证2020/1/13定理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，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)——这一结论与使用邻接表或邻接矩阵无关。2020/1/132)时间分析●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)使用邻接矩阵表示2020/1/132)宽度优先周游算法5.7宽度优先图的周游算法procedureBFT(G,n)//G的宽度优先周游//intVISITED(n)fori←1tondoVISITED(i)←0repeatfori←1tondo//反复调用BFS//ifVISITED(i)=0thencallBFS(i)endifrepeatendBFT注：若G是无向连通图或强连通有向图，则一次调用BFS即可完成对T的周游。否则，需要多次调用。2020/1/13图周游算法的应用●判定图G的连通性：若调用BFS的次数多于1次，则G为非连通的●生成图G的连通分图：一次调用BFS中可以访问到的所有结点及连接这些结点的边构成一个连通分图。●无向图自反传递闭包矩阵A*●宽度优先生成树向前边：BFS中由u达到未访问结点w的边(u,w)称为向前边。记T是BFS中所处理的所有向前边集合。宽度优先生成树：若G是连通图，则BFS终止时，T构成一棵生成树。12345678无向图G12345678G的宽度优先生成树2020/1/13定理5.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/1/13证明：若G是n个结点的连通图，则这n个结点都要被访问。除起始点v以外，其它n-1个结点都将被放且仅将被放到队列Q上一次，从而T将正好包含n-1条边，且这些边是各不相同的。即T是关于n个结点n-1边的无向图。同时，对于连通图G，T将包含由起始结点v到其它结点的路径，所以T是连通的。则T是G的一棵生成树。注：对于n个结点且正好有n-1条边的连通图是一棵树。2020/1/134.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)endifrepeatendDFS2020/1/13性质：①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/1/13深度优先生成树算法procedureDFS*(v)T←ΦVISITED(v)←1for邻接于v的每个结点wdoifVISITED(w)＝0thenT←T∪{(u,w)}callDFS(w)endifrepeatendDFS*2020/1/1312345678无向图G12345678G的宽度优先生成树12345678G的深度优先生成树2020/1/134.3BFS、DFS、D_Search算法比较BFS：使用队列保存未被检测的结点。结点按照宽度优先的次序被访问和进、出队列。DFS：使用栈保存未被检测的结点，结点按照深度优先的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。D_Search：使用栈保存未被检测的结点，结点按照宽度优先的次序被访问并被依次压入栈中，然后以相反的次序出栈进行新的检测。新的检测结点是最新被访问但未被检测的结点。BFS检测序列：12345678DFS检测序列：12485637D_Search检测序列：1378546212345678无向图G2020/1/135.3双连通分图与深度优先检索【通信网】图中结点表示通信站，边表示通信线路。14231095678图5.11一个连通图1243图5.12一个双连通图关