Lecture4-Properties of DFS

《Lecture4-Properties of DFS》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Lectrue4-PropertiesofDFSPropertiesofDFSClassificationofedgesTopologicalsort2004SDUPropertiesofDFSDefinition:Inarootedforest(especially,depth-firstforest),anyvertexuonthesimplepathfromtheroottoviscalledanancestorofv,andviscalledadescendantofu.Note:u=[v]ifandonlyifD

2、FS-VISIT(v)wascalledduringasearchofu’sadjacencylist.uiscalledtheparentofv.So:Vertexvisadescendantofvertexuinthedepth-firstforestifandonlyifvisdiscoveredduringthetimeinwhichuisgray(whenvisdiscovered,DFS-VISIT([v])iscalled,DFS-VISIT([v]),…DFS-VISIT(u))iscalled).20

3、04SDUPropertiesofDFS(Cont.)ParenthesisTheorem:InanyDFSofagraph(directedorundirected),foreachpairofverticesu,v,exactlyoneofthefollowingconditionsholds:uisadescendantofv,and[d[u],f[u]]isasubintervalof[d[v],f[v]].uisanancestorofv,and[d[v],f[v]]isasubintervalof[d[u],f[u

4、]].Neitheruisadescendantofvnorvisadescendantofu,and[d[u],f[u]]and[d[v],f[v]]aredisjoint.Page:1662004SDUProofItisobviousthateachpairu,vsatisfiesexactlyoneofthefollowing:uisadescendantofvvisadescendantofuneitherisdescendantoftheotherItisenoughtoprovethat1holdsifandon

5、lyif[d[u],f[u]]isasubintervalof[d[v],f[v]];2holdsifandonlyif[d[v],f[v]]isasubintervalof[d[u],f[u]];3holdsifandonlyif[d[u],f[u]]and[d[v],f[v]]aredisjoint.2004SDUProof(Continued)If1holds,thenumustbediscoveredwhenvisgray,thatmeansd[v]d[u]

6、v]d[u]

7、d[u],f[u]]isdisjointwith[d[v],f[v]].Intheopposite,if[d[u],f[u]]and[d[v],f[v]]aredisjoint,thenneitherisdiscoveredwhentheotherisgray,so,neitherisdescendantoftheother.2004SDUNestingofdescendants’intervalsCorollary:Vertexvisaproperdescendantofvertexuinthedepth-firstfor

8、estforagraphGifandonlyifd[u]