Explain BFS and DFS in terms of backtracking - Stack Overflow

Is BFS is possible using backtracking? - Stack Overflow Home Public Questions Tags Users Collectives ExploreCollectives FindaJob Jobs Companies Teams StackOverflowforTeams –Collaborateandshareknowledgewithaprivategroup. CreateafreeTeam WhatisTeams? Teams CreatefreeTeam CollectivesonStackOverflow Findcentralized,trustedcontentandcollaboratearoundthetechnologiesyouusemost. Learnmore Teams Q&Aforwork Connectandshareknowledgewithinasinglelocationthatisstructuredandeasytosearch. Learnmore ExplainBFSandDFSintermsofbacktracking AskQuestion Asked 11years,8monthsago Active 1year,5monthsago Viewed 25ktimes 25 22 WikipediaaboutDepthFirstSearch: Depth-firstsearch(DFS)isan algorithmfortraversingorsearching atree,treestructure,orgraph.One startsattheroot(selectingsome nodeastherootinthegraphcase) andexploresasfaraspossiblealong eachbranchbeforebacktracking. SowhatisBreadthFirstSearch? "analgorithmthatchooseastarting node,checksallnodesbacktracks, choosestheshortestpath,choseneighbournodesbacktracks, chosetheshortestpath,finally findstheoptimalpathbecauseof traversingeachpathduetocontinuous backtracking. Regexfind'spruning--backtracking? Thetermbacktrackingconfusesduetoitsvarietyofuse.UNIX'sfindpruninganSO-userexplainedwithbacktracking.RegexBuddyusestheterm"catastrophicbacktracking"ifyoudonotlimitthescopeofyourRegexes.Itseemstobeatoowidelyusedumbrella-term.So: Howdoyoudefine"backtracking"specificallyforGraphTheory? Whatis"backtracking"inBreadthFirstSearchandDepthFirstSearch? [Added] Gooddefinitionsaboutbacktrackingandexamples TheBrute-forcemethod Stallman's(?)inventedterm"dependency-directedbacktracking" Backtrackingandregexexample DepthFirstSearchdefinition. graphbacktrackingdepth-first-searchbreadth-first-search Share Improvethisquestion Follow editedJul28'20at6:36 AndrewHolmgren 95811goldbadge77silverbadges1515bronzebadges askedApr25'10at16:57 hhhhhh 46.6k5757goldbadges166166silverbadges261261bronzebadges Addacomment  |  1Answer 1 Active Oldest Votes 39 Theconfusioncomesinbecausebacktrackingissomethingthathappensduringsearch,butitalsoreferstoaspecificproblem-solvingtechniquewherealotofbacktrackingisdone.Suchprogramsarecalledbacktrackers. Picturedrivingintoaneighborhood,alwaystakingthefirstturnyousee(let'sassumetherearenoloops)untilyouhitadeadend,atwhichpointyoudrivebacktotheintersectionofthenextunvisitedstreet.Thisthe"first"kindofbacktracking,andit'sroughlyequivalenttocolloquialusageoftheword. Themorespecificusagereferstoaproblem-solvingstrategythatissimilartodepth-firstsearchbutbacktrackswhenitrealizesthatit'snotworthcontinuingdownsomesubtree. Putanotherway--anaiveDFSblindlyvisitseachnodeuntilitreachesthegoal.Yes,it"backtracks"onleafnodes.Butabacktrackeralsobacktracksonuselessbranches.OneexampleissearchingaBoggleboardforwords.Eachtileissurroundedby8others,sothetreeishuge,andnaiveDFScantaketoolong.Butwhenweseeacombinationlike"ZZQ,"wecansafelystopsearchingfromthispoint,sinceaddingmoreletterswon'tmakethataword. IlovetheselecturesbyProf.JulieZelenski.Shesolves8queens,asudokupuzzle,andanumbersubstitutionpuzzleusingbacktracking,andeverythingisnicelyanimated. ProgrammingAbstractions,Lecture10 ProgrammingAbstractions,Lecture11 Atreeisagraphwhereanytwoverticesonlyhaveonepathbetweenthem.Thiseliminatesthepossibilityofcycles.Whenyou'researchingagraph,youwillusuallyhavesomelogictoeliminatecyclesanyway,sothebehavioristhesame.Also,withadirectedgraph,youcan'tfollowedgesinthe"wrong"direction. FromwhatIcantell,intheStallmanpapertheydevelopedalogicsystemthatdoesn'tjustsay"yes"or"no"onaquerybutactuallysuggestsfixesforincorrectqueriesbymakingthesmallestnumberofchanges.Youcankindofseewherethefirstdefinitionofbacktrackingmightcomeintoplay. Share Improvethisanswer Follow editedOct10'16at21:42 answeredJul1'10at8:41 johncipjohncip 1,9991616silverbadges2020bronzebadges 1 Thisisveryhelpful,butdoesn'tdescribeBFSatall,asfarasIcantell. – RobinAndrews Nov11'21at13:34 Addacomment  |  YourAnswer ThanksforcontributingananswertoStackOverflow!Pleasebesuretoanswerthequestion.Providedetailsandshareyourresearch!Butavoid…Askingforhelp,clarification,orrespondingtootheranswers.Makingstatementsbasedonopinion;backthemupwithreferencesorpersonalexperience.Tolearnmore,seeourtipsonwritinggreatanswers. Draftsaved Draftdiscarded Signuporlogin SignupusingGoogle SignupusingFacebook SignupusingEmailandPassword Submit Postasaguest Name Email Required,butnevershown PostYourAnswer Discard Byclicking“PostYourAnswer”,youagreetoourtermsofservice,privacypolicyandcookiepolicy Nottheansweryou'relookingfor?Browseotherquestionstaggedgraphbacktrackingdepth-first-searchbreadth-first-searchoraskyourownquestion. TheOverflowBlog Episode404:Podcastnotfound;) TheGreatResignationishere.Whatdoesthatmeanfordevelopers? FeaturedonMeta ProvidingaJavaScriptAPIforuserscripts Congratulationstothe59sitesthatjustleftBeta Linked 136 What'sthedifferencebetweenbacktrackinganddepthfirstsearch? Related 197 BreadthFirstVsDepthFirst 152 HowdoesaBreadth-FirstSearchworkwhenlookingforShortestPath? 2 IsbacktrackingabsolutelynecessaryforcycledetectionusingDFSindirectedgraph? 62 WhatisdifferencebetweenBFSandDijkstra'salgorithmswhenlookingforshortestpath? 3 EquivalenceofagraphandaBFSandDFStree 10 InwhatcaseswouldBFSandDFSbemoreefficientthanA*searchalgorithm? 0 IsDFSfasterthanBFSwhensearchingaspecificnodeinSSC? 1 ConfusedwithDFSimplementation HotNetworkQuestions DospelleffectsthattriggerwhenyouarehitstilltriggeriftheydonotpenetrateyouractiveArcaneWard? howcalculatedamageingame? WhydoIneedtherootpasswordwhenmountinganinternaldriveinLinux? WhatisthecriterionforachesssettobeusedinFIDEtournaments? Isthereabenchmarkpaperthattakesintoaccounthowofteneachmoleculeisstudied? HowcouldGiantshunt? Whichmethodismoresuitable?overfittingoftraningdataorlowaccuracy? Bestwaytostoreverysmallamountofdata? HowcanImakemyskirtlookmorelikethepicture? WhydoGameBoyColorsnotwantnickel-cadmiumbatteries? Whydoesn'tthe"watch"commandworkonanalias? Howtoshowthatthisintegralofthenormaldistributionisfinite? HowcouldHarryhaveopenedHedwig'scageifhedidn'thavehiswand? QGISHowchangelinethicknessformultiplelayerswithoutchangingtheirindividualsettings? UsingNDSolveValueforSolvingaparabolicPDEnumerically Is"Iwilldoyogaforgood"ambiguousbecauseofthephrase"forgood"? Meaningofthestatement-test-x/usr/bin/find||exit0 NextGreaterNumber Ischangingsomewordsplagiarism? Tryingtounderstandanoldcustomlicense Everythingisnormallylight.Itisdarkwavesthattravelandcausedarkness-how? Reducingthezerorow/columnofamatrix Actualcasesofa"frivolousdrawoffer" Findingthemajorityelementinanarray morehotquestions Questionfeed SubscribetoRSS Questionfeed TosubscribetothisRSSfeed,copyandpastethisURLintoyourRSSreader. Yourprivacy Byclicking“Acceptallcookies”,youagreeStackExchangecanstorecookiesonyourdeviceanddiscloseinformationinaccordancewithourCookiePolicy. Acceptallcookies Customizesettings