BFS-DFS算法分析

7.3.1DFSDFS(G)ForeachvertexuinV(G)Docolor[u]WHITE[u]Niltime0ForeachvertexuinV(G)doifcolor[u]=WHITEthenDFS-Visit(u)DFS-Visit(u)color[u]GRAYd[u]timetime+1foreachvinAdj[u]doifcolor[v]=WHITEthen[v]uDFS-Visit(v)color[u]BLACKf[u]timetime+11/1/2/1/2/3/1/2/3/4/1/2/3/4/1/2/3/4/51/2/3/64/51/2/73/64/51/82/73/64/51/82/79/3/64/51/82/79/3/64/51/82/79/3/64/51/82/79/3/64/510/1/82/79/3/64/510/111/82/79/123/64/510/11ThisisaDAG!ACDBFGEdiscoveredDepthFirstSearchinalphabeticalorderDigraphwithcyclesACDBFGEexploredACDBFGENowheretoexplore!Deadend!ACDBFGEfinishedThebridgeisexploredandbacktrackedoverACDBFGEACDBFGEDiscovered!Findacycle!ACDBFGEcheckedACDBFGEFinished!ACDBFGEcheckedWell,Ihavetoback!ACDBFGEfinishedBacktrackACDBFGEfinishedBacktrackACDBFGEFinished!ACDBFGEcheckedACDBFGEACDBFGEDiscovered!ACDBFGEcheckedACDBFGEFinished!ACDBFGEfinisheddiscoveredcheckedACDBFGEfinishedfinishedfinishedBacktrackACDBFGETheDFSisfinished,thoughsomeislandsareneverexplored.7.3.2BFSBFS(G,s)ForeachvertexuinV(G)-{s}Docolor[u]WHITEd[u][u]NilQ{s}WhileQnonemptydouhead(Q)foreachvinAdj[u]doifcolor[v]=WHITEthencolor[v]=GRAYthend[v]d[u]+1[v]uEnqueue(Q,u)Dequeue(Q)color[u]BLACK0FIFOQueue:ssrtuxywv0011FIFOQueue:wrsrtuxywv1102211FIFOQueue:rtxsrtuxywv122022112FIFOQueue:txvsrtuxywv2220232112FIFOQueue:xvusrtuxywv22302321312FIFOQueue:vuysrtuxywv23302321312FIFOQueue:srtuxywvuy3302321312FIFOQueue:srtuxywv3y02321312FIFOQueue:emptysrtuxywv7.4.3DepthfirstsearchtreesDefinitionsinDFSdfstreeanddfsforestAncestorProperancestor,parentEdgesofadirectedgraphGareclassifiedasTreeedgeBackedgeDescendantedgeCrossedge7.4.4AgeneralDFSskeletonColorpolicyforvertices:WhiteGrayBlackAlgorithm7.3Visiteachundiscoveredvertex–eachvertexVisiteachadjVertices:eacheadeDfs(adjvertices,color,v)1Color[v]gray2Preorderprocessingofv3remAdjadjVertices[v]4WhileremAdjisnotempty5wfirstoneinRemAdj6ifcolor[w]iswhite7explorationprocessingfortreeedgevw8wAnsdfs(adjvertices,color,w)9Backtrackprocessingfortreeedgevw10else11checkingfornontreeedgevw12remAdjrest(remAdj)13Postorderprocessingofv14color[v]black15returnAlgorithm7.37.4.5StructureofDFSDefinitionsactive(v)istheinterval[discoverTime(v),finishTime(v)]vDefinitionsactive(v)istheinterval[discoverTime(v),finishTime(v)]vdiscoverTimeDefinitionsactive(v)istheinterval[discoverTime(v),finishTime(v)]vDefinitionsactive(v)istheinterval[discoverTime(v),finishTime(v)]vDefinitionsactive(v)istheinterval[discoverTime(v),finishTime(v)]vDefinitionsactive(v)istheinterval[discoverTime(v),finishTime(v)]vDefinitionsactive(v)istheinterval[discoverTime(v),finishTime(v)]vDefinitionsactive(v)istheinterval[discoverTime(v),finishTime(v)]vDefinitionsactive(v)istheinterval[discoverTime(v),finishTime(v)]vDefinitionsactive(v)istheinterval[discoverTime(v),finishTime(v)]vDefinitionsactive(v)istheinterval[discoverTime(v),finishTime(v)]vfinishTimeTheorem7.1For(v,w)inG(V,E),1.wisadescendantofviffactive(w)isasubsetofactive(v)2.Ifvandwhavenoancestor/descendantrelationship,thentheiractivesaredisjoint3.IfvwinE,vwisacrossedgeiffactive(w)precedesactive(v);vwisdescendantedgeiffthereissomethirdvertexxsuchthatactive(w)\subsetactive(x)\subsetactive(v);vwisatreeedgeiffactive(w)\subsetactive(v),andthereisnothirdvertexxsuchthatactive(w)\subsetactive(x)\subsetactive(v);vwisabackedgeiffactive(v)\subsetactive(w)Corollary7.2TheverticesthatarediscoveredwhilevisactiveareexactlythedescendantofvinitsDFStreeTheorem7.3(whitepaththeorem)InanydfsofagraphG,avertexwisadescendantofavertexvinadfstreeifandonlyifatthetimevertexvisdiscovered,thereisapathinGfromvtowconsistingentirelyofwhitevertices.Proof.Onlyif:ifwisadescendantofv,thepathfromvtowisawhitepathIf:useinductiononthelengthkofawhitepathfromvtow.Ifk=0,thatis,v=w.Ifwehaveshownthatifthereexistsawhitepathoflengthkfromvtow,thenwisadescendantofv.NowsupposethatthereisawhitepathP=v,x1,…,xk,xk+1=w,inwhichifxiisdiscoveredearliestduringvisgray,thenthepathlengthofeitherv,x1,…,xiorpathxi,xi+1,…,wislessthank+1,bytheassumptionwisadescendantofxi,andadescendantofv.7.4.6DAGProblem:topologicalorderistotestifthereexistacycleinadigraph.Def.Topologicalorderistoassignnumber1,2,…,nsuccessivelytotheverticesofagraphsuchthatforeachedge(v,w),thenumberassignedtovislessthanthattow.ThereversetopologicalorderisthesameexceptthenumberassignedtovisgreaterthanthattowLemma7.4IfadigraphGhasacycle,thenGhasnotopologicalorder.Dfs(adjvertices,color,v)1Color[v]gray2Preorderprocessingofv3remAdjadjVertices[v]4WhileremAdjisnotempty5wfirstoneinRemAdj6ifcolor[w]iswhite7explorationprocessingfortreeedgevw8wAnsdfs(adjvertices,color,w)9Backtrackprocessingfortreeedgevw10else11checkingfornontreeedgevw12remAdjrest(remAdj)13PostorderprocessingofvtopoNum++,topo[v]=topoNum14color[v]black15returnAlgorithm7.5topoNum=0Theorem7.5IfGisaDAGwithnvertices,thenAlgorithm7.5computesareversetopologicalorderforGinthearraytopology.ThereforeeveryDAGhasareversetopologicalorderandatopologicalorder.231678945231678945Reverseedges2316789451/2316789451/2/32316789451/42/323167