Graph traversal - Wikipedia

In computer science, graph traversal refers to the process of visiting (checking and/or updating) each vertex in a graph. Such traversals are classified by ... Graphtraversal FromWikipedia,thefreeencyclopedia Jumptonavigation Jumptosearch "Graphsearch"redirectshere.NottobeconfusedwithFacebookGraphSearch. Thisarticleneedsadditionalcitationsforverification.Pleasehelpimprovethisarticlebyaddingcitationstoreliablesources.Unsourcedmaterialmaybechallengedandremoved.Findsources: "Graphtraversal" – news ·newspapers ·books ·scholar ·JSTOR(October2014)(Learnhowandwhentoremovethistemplatemessage) Graphandtreesearchalgorithms α–β A* B* Backtracking Beam Bellman–Ford Best-first Bidirectional Borůvka Branch&bound BFS BritishMuseum D* DFS Dijkstra Edmonds Floyd–Warshall Fringesearch Hillclimbing IDA* Iterativedeepening Johnson Jumppoint Kruskal LexicographicBFS LPA* Prim SMA* Listings Graphalgorithms Searchalgorithms Listofgraphalgorithms Relatedtopics Dynamicprogramming Graphtraversal Treetraversal Searchgames Graphcoloring vte Incomputerscience,graphtraversal(alsoknownasgraphsearch)referstotheprocessofvisiting(checkingand/orupdating)eachvertexinagraph.Suchtraversalsareclassifiedbytheorderinwhichtheverticesarevisited.Treetraversalisaspecialcaseofgraphtraversal. Contents 1Redundancy 2Graphtraversalalgorithms 2.1Depth-firstsearch 2.1.1Pseudocode 2.2Breadth-firstsearch 2.2.1Pseudocode 3Applications 4Graphexploration 5Universaltraversalsequences 6References 7Seealso Redundancy[edit] Unliketreetraversal,graphtraversalmayrequirethatsomeverticesbevisitedmorethanonce,sinceitisnotnecessarilyknownbeforetransitioningtoavertexthatithasalreadybeenexplored.Asgraphsbecomemoredense,thisredundancybecomesmoreprevalent,causingcomputationtimetoincrease;asgraphsbecomemoresparse,theoppositeholdstrue. Thus,itisusuallynecessarytorememberwhichverticeshavealreadybeenexploredbythealgorithm,sothatverticesarerevisitedasinfrequentlyaspossible(orintheworstcase,topreventthetraversalfromcontinuingindefinitely).Thismaybeaccomplishedbyassociatingeachvertexofthegraphwitha"color"or"visitation"stateduringthetraversal,whichisthencheckedandupdatedasthealgorithmvisitseachvertex.Ifthevertexhasalreadybeenvisited,itisignoredandthepathispursuednofurther;otherwise,thealgorithmchecks/updatesthevertexandcontinuesdownitscurrentpath. Severalspecialcasesofgraphsimplythevisitationofotherverticesintheirstructure,andthusdonotrequirethatvisitationbeexplicitlyrecordedduringthetraversal.Animportantexampleofthisisatree:duringatraversalitmaybeassumedthatall"ancestor"verticesofthecurrentvertex(andothersdependingonthealgorithm)havealreadybeenvisited.Boththedepth-firstandbreadth-firstgraphsearchesareadaptationsoftree-basedalgorithms,distinguishedprimarilybythelackofastructurallydetermined"root"vertexandtheadditionofadatastructuretorecordthetraversal'svisitationstate. Graphtraversalalgorithms[edit] Note.—Ifeachvertexinagraphistobetraversedbyatree-basedalgorithm(suchasDFSorBFS),thenthealgorithmmustbecalledatleastonceforeachconnectedcomponentofthegraph.Thisiseasilyaccomplishedbyiteratingthroughalltheverticesofthegraph,performingthealgorithmoneachvertexthatisstillunvisitedwhenexamined. Anon-verbaldescriptionofthreegraphtraversalalgorithms:randomly,depth-firstsearch,andbreadth-firstsearch. Depth-firstsearch[edit] Mainarticle:Depth-firstsearch Adepth-firstsearch(DFS)isanalgorithmfortraversingafinitegraph.DFSvisitsthechildverticesbeforevisitingthesiblingvertices;thatis,ittraversesthedepthofanyparticularpathbeforeexploringitsbreadth.Astack(oftentheprogram'scallstackviarecursion)isgenerallyusedwhenimplementingthealgorithm. Thealgorithmbeginswithachosen"root"vertex;ittheniterativelytransitionsfromthecurrentvertextoanadjacent,unvisitedvertex,untilitcannolongerfindanunexploredvertextotransitiontofromitscurrentlocation.Thealgorithmthenbacktracksalongpreviouslyvisitedvertices,untilitfindsavertexconnectedtoyetmoreunchartedterritory.Itwillthenproceeddownthenewpathasithadbefore,backtrackingasitencountersdead-ends,andendingonlywhenthealgorithmhasbacktrackedpasttheoriginal"root"vertexfromtheveryfirststep. DFSisthebasisformanygraph-relatedalgorithms,includingtopologicalsortsandplanaritytesting. Pseudocode[edit] Input:AgraphGandavertexvofG. Output:Alabelingoftheedgesintheconnectedcomponentofvasdiscoveryedgesandbackedges. procedureDFS(G,v)is labelvasexplored foralledgeseinG.incidentEdges(v)do ifedgeeisunexploredthen w←G.adjacentVertex(v,e) ifvertexwisunexploredthen labeleasadiscoverededge recursivelycallDFS(G,w) else labeleasabackedge Breadth-firstsearch[edit] Mainarticle:Breadth-firstsearch Thissectionneedsexpansion.Youcanhelpbyaddingtoit.(October2012) Abreadth-firstsearch(BFS)isanothertechniquefortraversingafinitegraph.BFSvisitsthesiblingverticesbeforevisitingthechildvertices,andaqueueisusedinthesearchprocess.Thisalgorithmisoftenusedtofindtheshortestpathfromonevertextoanother. Pseudocode[edit] Input:AgraphGandavertexvofG. Output:Theclosestvertextovsatisfyingsomeconditions,ornullifnosuchvertexexists. procedureBFS(G,v)is createaqueueQ enqueuevontoQ markv whileQisnotemptydo w←Q.dequeue() ifwiswhatwearelookingforthen returnw foralledgeseinG.adjacentEdges(w)do x←G.adjacentVertex(w,e) ifxisnotmarkedthen markx enqueuexontoQ returnnull Applications[edit] Breadth-firstsearchcanbeusedtosolvemanyproblemsingraphtheory,forexample: findingallverticeswithinoneconnectedcomponent; Cheney'salgorithm; findingtheshortestpathbetweentwovertices; testingagraphforbipartiteness; Cuthill–McKeealgorithmmeshnumbering; Ford–Fulkersonalgorithmforcomputingthemaximumflowinaflownetwork; serialization/deserializationofabinarytreevsserializationinsortedorder(allowsthetreetobere-constructedinanefficientmanner); mazegenerationalgorithms; floodfillalgorithmformarkingcontiguousregionsofatwodimensionalimageorn-dimensionalarray; analysisofnetworksandrelationships. Graphexploration[edit] Theproblemofgraphexplorationcanbeseenasavariantofgraphtraversal.Itisanonlineproblem,meaningthattheinformationaboutthegraphisonlyrevealedduringtheruntimeofthealgorithm.Acommonmodelisasfollows:givenaconnectedgraphG=(V,E)withnon-negativeedgeweights.Thealgorithmstartsatsomevertex,andknowsallincidentoutgoingedgesandtheverticesattheendoftheseedges—butnotmore.Whenanewvertexisvisited,thenagainallincidentoutgoingedgesandtheverticesattheendareknown.Thegoalistovisitallnverticesandreturntothestartingvertex,butthesumoftheweightsofthetourshouldbeassmallaspossible.Theproblemcanalsobeunderstoodasaspecificversionofthetravellingsalesmanproblem,wherethesalesmanhastodiscoverthegraphonthego. Forgeneralgraphs,thebestknownalgorithmsforbothundirectedanddirectedgraphsisasimplegreedyalgorithm: Intheundirectedcase,thegreedytourisatmostO(lnn)-timeslongerthananoptimaltour.[1]Thebestlowerboundknownforanydeterministiconlinealgorithmis10/3.[2] Unitweightundirectedgraphscanbeexploredwithacompetitiverationof2−ε,[3]whichisalreadyatightboundonTadpolegraphs.[4] Inthedirectedcase,thegreedytourisatmost(n−1)-timeslongerthananoptimaltour.Thismatchesthelowerboundofn−1.[5]AnanalogouscompetitivelowerboundofΩ(n)alsoholdsforrandomizedalgorithmsthatknowthecoordinatesofeachnodeinageometricembedding.Ifinsteadofvisitingallnodesjustasingle"treasure"nodehastobefound,thecompetitiveboundsareΘ(n2)onunitweightdirectedgraphs,forbothdeterministicandrandomizedalgorithms. Universaltraversalsequences[edit] Thissectionneedsexpansion.Youcanhelpbyaddingtoit.(December2016) Auniversaltraversalsequenceisasequenceofinstructionscomprisingagraphtraversalforanyregulargraphwithasetnumberofverticesandforanystartingvertex.AprobabilisticproofwasusedbyAleliunasetal.toshowthatthereexistsauniversaltraversalsequencewithnumberofinstructionsproportionaltoO(n5)foranyregulargraphwithnvertices.[6]Thestepsspecifiedinthesequencearerelativetothecurrentnode,notabsolute.Forexample,ifthecurrentnodeisvj,andvjhasdneighbors,thenthetraversalsequencewillspecifythenextnodetovisit,vj+1,astheithneighborofvj,where1≤i≤d. References[edit] ^Rosenkrantz,DanielJ.;Stearns,RichardE.;Lewis,II,PhilipM.(1977)."AnAnalysisofSeveralHeuristicsfortheTravelingSalesmanProblem".SIAMJournalonComputing.6(3):563–581.doi:10.1137/0206041. ^Birx,Alexander;Disser,Yann;Hopp,AlexanderV.;Karousatou,Christina(May2021)."Animprovedlowerboundforcompetitivegraphexploration".TheoreticalComputerScience.868:65–86.arXiv:2002.10958.doi:10.1016/j.tcs.2021.04.003. ^Miyazaki,Shuichi;Morimoto,Naoyuki;Okabe,Yasuo(2009)."TheOnlineGraphExplorationProblemonRestrictedGraphs".IEICETransactionsonInformationandSystems.E92-D(9):1620–1627.doi:10.1587/transinf.E92.D.1620.hdl:2433/226939. ^Brandt,Sebastian;Foerster,Klaus-Tycho;Maurer,Jonathan;Wattenhofer,Roger(November2020)."Onlinegraphexplorationonarestrictedgraphclass:Optimalsolutionsfortadpolegraphs".TheoreticalComputerScience.839:176–185.arXiv:1903.00581.doi:10.1016/j.tcs.2020.06.007. ^Foerster,Klaus-Tycho;Wattenhofer,Roger(December2016)."Loweranduppercompetitiveboundsforonlinedirectedgraphexploration".TheoreticalComputerScience.655:15–29.doi:10.1016/j.tcs.2015.11.017. ^Aleliunas,R.;Karp,R.;Lipton,R.;Lovász,L.;Rackoff,C.(1979)."Randomwalks,universaltraversalsequences,andthecomplexityofmazeproblems".20thAnnualSymposiumonFoundationsofComputerScience(SFCS1979):218–223.doi:10.1109/SFCS.1979.34. Seealso[edit] Externalmemorygraphtraversal Retrievedfrom"https://en.wikipedia.org/w/index.php?title=Graph_traversal&oldid=1037177746" Categories:GraphalgorithmsHiddencategories:CS1:longvolumevalueArticlesneedingadditionalreferencesfromOctober2014AllarticlesneedingadditionalreferencesArticlestobeexpandedfromOctober2012AllarticlestobeexpandedArticlesusingsmallmessageboxesArticlestobeexpandedfromDecember2016Articleswithexamplepseudocode Navigationmenu Personaltools NotloggedinTalkContributionsCreateaccountLogin Namespaces ArticleTalk Variants expanded collapsed Views ReadEditViewhistory More expanded collapsed Search Navigation MainpageContentsCurrenteventsRandomarticleAboutWikipediaContactusDonate Contribute HelpLearntoeditCommunityportalRecentchangesUploadfile Tools WhatlinkshereRelatedchangesUploadfileSpecialpagesPermanentlinkPageinformationCitethispageWikidataitem Print/export DownloadasPDFPrintableversion Languages DeutschفارسیFrançais한국어MagyarPolskiСрпски/srpskiУкраїнськаTiếngViệt中文 Editlinks