资源描述：
《depth first search》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、DEPrH-FIRSTSEARCH.ANI)LmEARGRAmALGORITHMS(WorkingPaper)RobertTarjanComputerScienceDepartmentStanfordUniversityStanford,CaliforniaSl.UlIDlaryThevalueofdepth-firstsearchor"backtracking"wandwisadescendantofv.Ifvisavertexasatechniqueforsolvinggraphproblemsisil
2、lustra•inatreeT,TvisthesubtreeofThavingastedbytwoexamples.AnalgorithmforfindingtheverticesallthedescendantsofvinT.IfGisbiconnectedcomponentsofanundirectedgraphandanadirectedgraph,atreeTisaspanningtreeofGimprovedversionofanalgorithmforfindingtheifTisasubgra
3、phofGandTcontainsallthestronglyconnectedcomponentsofadirectedgraphareverticesofG.presented.ThespaceandtimerequirementsofbothalgorithInsareboundedbyklV+k2E+k3forsomeDepth-FirstSearchconstantsk,k'andk,whereVisthentunberl23Atechniquewhichhasbeenwidelyusedforf
4、indingofverticesandEisthenumberofedgesofthesolutionstoproblemsincombinatorialtheoryandgraphbeingexamined.6artifici~lintelligence,8butwhosepropertieshaveIntroductionnotbeenwidelyanalyzedisofgreatvalueinsolvinggraphproblems.Thisisbacktracking,ordepth-firstCo
5、nsideragraphG,consistingofasetofsearch.SupposeGisagraphwhichwewishtoverticesVandasetofedgese.Thegraphmayexplore.InitiallyalltheverticesofGareunex•eitherbedirected(theedgesareorderedpairs(v,w)plored.WestartfromsomevertexofGandchooseofvertices;visthetailandw
6、istheheadofanedgetofollow.Traversingtheedgeleadstoanewtheedge)orundirected(theedgesareunorderedpairsvertex.Wecontinueinthisway;ateachstepweofvertices,alsorepresentedas(v,w)).Graphsselectanunexplorededgeleadingfromavertexalreadyformasuitableabstractionforpr
7、oblemsinmanyareas;reachedandwetraversethisedge.Theedgeleadstochemistry,electricalengineering,andsociology,forsomevertex,eitherneworalreadyreached.Wheneverexample.Theyarealsoverygeneralstructuresforwerunoutofedgesleadingfromoldvertices,westoringandretrievin
8、ginformation.Manyquestionsmaychoosesomeunreachedvertex,ifanyeXists,andbeginbeaskedaboutgraphs;weneedthefastest,mosteco•anewexplorationfromthispoint.Eventuallywewillnomicalalgorithmstogiveanswerstothesequestio
