资源描述：
《Depth-first Search and Linear Graph Algorithms by Robert Tarjan.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、SIAMJ.COMPUT.Vol.1,No.2,June1972DEPTH-FIRSTSEARCHANDLINEARGRAPHALGORITHMS*ROBERTTARJAN"Abstract.Thevalueofdepth-firstsearchor"bacltracking"asatechniqueforsolvingproblemsisillustratedbytwoexamples.Animprovedversionofanalgorithmforfindingthestronglyconnectedcomponentsofadi
2、rectedgraphandaralgorithmforfindingthebiconnectedcomponentsofanun-directgrapharepresented.Thespaceandtimerequirementsofbothalgorithmsareboundedbyk1V+k2Ed-kforsomeconstantskl,k2,andka,whereVisthenumberofverticesandEisthenumberofedgesofthegraphbeingexamined.Keywords.Algori
3、thm,backtracking,biconnectivity,connectivity,depth-first,graph,search,spanningtree,strong-connectivity.1.Introduction.ConsideragraphG,consistingofasetofverticesUandasetofedgesg.Thegraphmayeitherbedirected(theedgesareorderedpairs(v,w)ofvertices;visthetailandwistheheadofth
4、eedge)orundirected(theedgesareunorderedpairsofvertices,alsorepresentedas(v,w)).Graphsformasuitableabstractionforproblemsinmanyareas;chemistry,electricalengineering,andsociology,forexample.Thusitisimportanttohavethemosteconomicalalgo-rithmsforansweringgraph-theoreticalque
5、stions.Instudyinggraphalgorithmswecannotavoidatleastafewdefinitions.Thesedefinitionsaremore-or-lessstandardintheliterature.(SeeHarary[3],forinstance.)IfG(,g)isagraph,apathp’vwinGisasequenceofverticesandedgesleadingfromvtow.Apathissimpleifallitsverticesaredistinct.Apathp’
6、vviscalledaclosedpath.Aclosedpathp’vvisacycleifallitsedgesaredistinctandtheonlyvertextooccurtwiceinpisv,whichoccursexactlytwice.Twocycleswhicharecyclicpermutationsofeachotherareconsideredtobethesamecycle.Theundirectedversionofadirectedgraphisthegraphformedbyconvertingeac
7、hedgeofthedirectedgraphintoanundirectededgeandremovingduplicateedges.Anundirectedgraphisconnectedifthereisapathbetweeneverypairofvertices.A(directedrooted)treeTisadirectedgraphwhoseundirectedversionisconnected,havingonevertexwhichistheheadofnoedges(calledtheroot),andsuch
8、thatallverticesexcepttherootaretheheadofexactlyoneedge.Therelation"(v,w)isanedgeofT"isdenotedbyv-w.Ther
