Depth First Search or DFS for a Graph - GeeksforGeeks

Depth First Traversal (or Search) for a graph is similar to Depth First Traversal of a tree. The only catch here is, unlike trees, graphs may ... Skiptocontent TutorialsPracticeDS&Algo.MustDoQuestionsDSATopic-wiseDSACompany-wiseAlgorithmsAnalysisofAlgorithmsAsymptoticAnalysisWorst,AverageandBestCasesAsymptoticNotationsLittleoandlittleomeganotationsLowerandUpperBoundTheoryAnalysisofLoopsSolvingRecurrencesAmortizedAnalysisWhatdoes'SpaceComplexity'mean?Pseudo-polynomialAlgorithmsPolynomialTimeApproximationSchemeATimeComplexityQuestionSearchingAlgorithmsSortingAlgorithmsGraphAlgorithmsPatternSearchingGeometricAlgorithmsMathematicalBitwiseAlgorithmsRandomizedAlgorithmsGreedyAlgorithmsDynamicProgrammingDivideandConquerBacktrackingBranchandBoundAllAlgorithmsDataStructuresArraysLinkedListStackQueueBinaryTreeBinarySearchTreeHeapHashingGraphAdvancedDataStructureMatrixStringsAllDataStructuresInterviewCornerCompanyPreparationTopTopicsPracticeCompanyQuestionsInterviewExperiencesExperiencedInterviewsInternshipInterviewsCompetititveProgrammingDesignPatternsSystemDesignTutorialMultipleChoiceQuizzesLanguagesCC++JavaPythonC#JavaScriptjQuerySQLPHPScalaPerlGoLanguageHTMLCSSKotlinCSSubjectsMathematicsOperatingSystemDBMSComputerNetworksComputerOrganizationandArchitectureTheoryofComputationCompilerDesignDigitalLogicSoftwareEngineeringGATEGATEComputerScienceNotesLastMinuteNotesGATECSSolvedPapersGATECSOriginalPapersandOfficialKeysGATE2021DatesGATECS2021SyllabusImportantTopicsforGATECSWebTechnologiesHTMLCSSJavaScriptAngularJSReactJSNodeJSBootstrapjQueryPHPSoftwareDesignsSoftwareDesignPatternsSystemDesignTutorialSchoolLearningSchoolProgrammingMathematicsNumberSystemAlgebraTrigonometryStatisticsProbabilityGeometryMensurationCalculusMathsNotes(Class8-12)Class8NotesClass9NotesClass10NotesClass11NotesClass12NotesNCERTSolutionsClass8MathsSolutionClass9MathsSolutionClass10MathsSolutionClass11MathsSolutionClass12MathsSolutionRDSharmaSolutionsClass8MathsSolutionClass9MathsSolutionClass10MathsSolutionClass11MathsSolutionClass12MathsSolutionPhysicsNotes(Class8-11)Class8NotesClass9NotesClass10NotesClass11NotesISROCSISROCSSolvedPapersISROCSOriginalPapersandOfficialKeysISROCSSyllabusforScientist/EngineerExamUGCNETCSUGCNETCSNotesPaperIIUGCNETCSNotesPaperIIIUGCNETCSSolvedPapersStudentCampusAmbassadorProgramSchoolAmbassadorProgramProjectGeekoftheMonthCampusGeekoftheMonthPlacementCourseCompetititveProgrammingTestimonialsGeekontheTopCareersInternshipJobsApplyforJobsPostaJobCourses ComewritearticlesforusandgetfeaturedLearnandcodewiththebestindustryexpertsGetaccesstoad-freecontent,doubtassistanceandmore!ComeandfindyourdreamjobwithusGeeksDigestQuizzesGeeksCampusGblogArticlesIDECampusMantri HomeSavedVideosCoursesGBlogPuzzlesWhat'sNew? ChangeLanguage DataStructuresAlgorithmsInterviewPreparationTopic-wisePracticeC++JavaPythonCompetitiveProgrammingMachineLearningWebDevelopmentPuzzlesProjectIdeasGFGSchool RelatedArticles ▲RelatedArticlesRatinaMaze|Backtracking-2CountnumberofwaystoreachdestinationinaMazeCountallpossiblepathsfromtoplefttobottomrightofamXnmatrixPrintallpossiblepathsfromtoplefttobottomrightofamXnmatrixUniquepathsinaGridwithObstaclesUniquepathscoveringeverynon-obstacleblockexactlyonceinagridDepthFirstSearchorDFSforaGraphBreadthFirstSearchorBFSforaGraphLevelOrderBinaryTreeTraversalTreeTraversals(Inorder,PreorderandPostorder)InorderTreeTraversalwithoutRecursionInorderTreeTraversalwithoutrecursionandwithoutstack!PrintPostordertraversalfromgivenInorderandPreordertraversalsConstructTreefromgivenInorderandPreordertraversalsConstructaBinaryTreefromPostorderandInorderConstructFullBinaryTreefromgivenpreorderandpostordertraversalsNQueenProblem|Backtracking-3PrintingallsolutionsinN-QueenProblemWarnsdorff’salgorithmforKnight’stourproblemTheKnight’stourproblem|Backtracking-1Dijkstra'sshortestpathalgorithm|GreedyAlgo-7GraphanditsrepresentationsPrim’sMinimumSpanningTree(MST)|GreedyAlgo-5Kruskal’sMinimumSpanningTreeAlgorithm|GreedyAlgo-2TopologicalSortingDetectCycleinaDirectedGraphBellman–FordAlgorithm|DP-23FloydWarshallAlgorithm|DP-16TableofContentsRatinaMaze|Backtracking-2CountnumberofwaystoreachdestinationinaMazeCountallpossiblepathsfromtoplefttobottomrightofamXnmatrixPrintallpossiblepathsfromtoplefttobottomrightofamXnmatrixUniquepathsinaGridwithObstaclesUniquepathscoveringeverynon-obstacleblockexactlyonceinagridDepthFirstSearchorDFSforaGraphBreadthFirstSearchorBFSforaGraphLevelOrderBinaryTreeTraversalTreeTraversals(Inorder,PreorderandPostorder)InorderTreeTraversalwithoutRecursionInorderTreeTraversalwithoutrecursionandwithoutstack!PrintPostordertraversalfromgivenInorderandPreordertraversalsConstructTreefromgivenInorderandPreordertraversalsConstructaBinaryTreefromPostorderandInorderConstructFullBinaryTreefromgivenpreorderandpostordertraversalsNQueenProblem|Backtracking-3PrintingallsolutionsinN-QueenProblemWarnsdorff’salgorithmforKnight’stourproblemTheKnight’stourproblem|Backtracking-1Dijkstra'sshortestpathalgorithm|GreedyAlgo-7GraphanditsrepresentationsPrim’sMinimumSpanningTree(MST)|GreedyAlgo-5Kruskal’sMinimumSpanningTreeAlgorithm|GreedyAlgo-2TopologicalSortingDetectCycleinaDirectedGraphBellman–FordAlgorithm|DP-23FloydWarshallAlgorithm|DP-16ImproveArticle SaveArticle LikeArticle DepthFirstSearchorDFSforaGraphDifficultyLevel: EasyLastUpdated: 30Nov,2021 DepthFirstTraversal(orSearch)foragraphissimilartoDepthFirstTraversalofatree.Theonlycatchhereis,unliketrees,graphsmaycontaincycles(anodemaybevisitedtwice).Toavoidprocessinganodemorethanonce,useabooleanvisitedarray. Example: Input:n=4,e=6 0->1,0->2,1->2,2->0,2->3,3->3 Output:DFSfromvertex1:1203 Explanation: DFSDiagram:  Input:n=4,e=6 2->0,0->2,1->2,0->1,3->3,1->3 Output:DFSfromvertex2:2013 Explanation: DFSDiagram:  Recommended:Pleasesolveiton“PRACTICE”first,beforemovingontothesolution.Prerequisites: SeethispostforallapplicationsofDepthFirstTraversal.Approach: Depth-firstsearchisanalgorithmfortraversingorsearchingtreeorgraphdatastructures.Thealgorithmstartsattherootnode(selectingsomearbitrarynodeastherootnodeinthecaseofagraph)andexploresasfaraspossiblealongeachbranchbeforebacktracking.Sothebasicideaistostartfromtherootoranyarbitrarynodeandmarkthenodeandmovetotheadjacentunmarkednodeandcontinuethisloopuntilthereisnounmarkedadjacentnode.Thenbacktrackandcheckforotherunmarkednodesandtraversethem.Finally,printthenodesinthepath.Algorithm: Createarecursivefunctionthattakestheindexofthenodeandavisitedarray.Markthecurrentnodeasvisitedandprintthenode.Traversealltheadjacentandunmarkednodesandcalltherecursivefunctionwiththeindexoftheadjacentnode.Implementation: BelowareimplementationsofsimpleDepthFirstTraversal.TheC++implementationusesanadjacencylistrepresentationofgraphs.STL’slistcontainerisusedtostorelistsofadjacentnodes.C++//C++programtoprintDFStraversalfrom //agivenvertexinagivengraph #include usingnamespacestd; //Graphclassrepresentsadirectedgraph //usingadjacencylistrepresentation classGraph{ public: mapvisited; map>adj; //functiontoaddanedgetograph voidaddEdge(intv,intw); //DFStraversalofthevertices //reachablefromv voidDFS(intv); }; voidGraph::addEdge(intv,intw) { adj[v].push_back(w);//Addwtov’slist. } voidGraph::DFS(intv) { //Markthecurrentnodeasvisitedand //printit visited[v]=true; cout<::iteratori; for(i=adj[v].begin();i!=adj[v].end();++i) if(!visited[*i]) DFS(*i); } //Drivercode intmain() { //Createagraphgivenintheabovediagram Graphg; g.addEdge(0,1); g.addEdge(0,2); g.addEdge(1,2); g.addEdge(2,0); g.addEdge(2,3); g.addEdge(3,3); cout<adj[]; //Constructor @SuppressWarnings("unchecked")Graph(intv) { V=v; adj=newLinkedList[v]; for(inti=0;ii=adj[v].listIterator(); while(i.hasNext()){ intn=i.next(); if(!visited[n]) DFSUtil(n,visited); } } //ThefunctiontodoDFStraversal. //Itusesrecursive //DFSUtil() voidDFS(intv) { //Markalltheverticesas //notvisited(setas //falsebydefaultinjava) booleanvisited[]=newboolean[V]; //Calltherecursivehelper //functiontoprintDFS //traversal DFSUtil(v,visited); } //DriverCode publicstaticvoidmain(Stringargs[]) { Graphg=newGraph(4); g.addEdge(0,1); g.addEdge(0,2); g.addEdge(1,2); g.addEdge(2,0); g.addEdge(2,3); g.addEdge(3,3); System.out.println( "FollowingisDepthFirstTraversal" +"(startingfromvertex2)"); g.DFS(2); } } //ThiscodeiscontributedbyAakashHasijaPython3#Python3programtoprintDFStraversal #fromagivengivengraph fromcollectionsimportdefaultdict #Thisclassrepresentsadirectedgraphusing #adjacencylistrepresentation classGraph: #Constructor def__init__(self): #defaultdictionarytostoregraph self.graph=defaultdict(list) #functiontoaddanedgetograph defaddEdge(self,u,v): self.graph[u].append(v) #AfunctionusedbyDFS defDFSUtil(self,v,visited): #Markthecurrentnodeasvisited #andprintit visited.add(v) print(v,end='') #Recurforallthevertices #adjacenttothisvertex forneighbourinself.graph[v]: ifneighbournotinvisited: self.DFSUtil(neighbour,visited) #ThefunctiontodoDFStraversal.Ituses #recursiveDFSUtil() defDFS(self,v): #Createasettostorevisitedvertices visited=set() #Calltherecursivehelperfunction #toprintDFStraversal self.DFSUtil(v,visited) #Drivercode #Createagraphgiven #intheabovediagram g=Graph() g.addEdge(0,1) g.addEdge(0,2) g.addEdge(1,2) g.addEdge(2,0) g.addEdge(2,3) g.addEdge(3,3) print("FollowingisDFSfrom(startingfromvertex2)") g.DFS(2) #ThiscodeiscontributedbyNeelamYadav C#//C#programtoprintDFStraversal //fromagivengraph usingSystem; usingSystem.Collections.Generic; //Thisclassrepresentsadirectedgraph //usingadjacencylistrepresentation classGraph{ privateintV;//No.ofvertices //Arrayoflistsfor //AdjacencyListRepresentation privateList[]adj; //Constructor Graph(intv) { V=v; adj=newList[v]; for(inti=0;i(); } //FunctiontoAddanedgeintothegraph voidAddEdge(intv,intw) { adj[v].Add(w);//Addwtov'slist. } //AfunctionusedbyDFS voidDFSUtil(intv,bool[]visited) { //Markthecurrentnodeasvisited //andprintit visited[v]=true; Console.Write(v+""); //Recurforallthevertices //adjacenttothisvertex ListvList=adj[v]; foreach(varninvList) { if(!visited[n]) DFSUtil(n,visited); } } //ThefunctiontodoDFStraversal. //ItusesrecursiveDFSUtil() voidDFS(intv) { //Markalltheverticesasnotvisited //(setasfalsebydefaultinc#) bool[]visited=newbool[V]; //Calltherecursivehelperfunction //toprintDFStraversal DFSUtil(v,visited); } //DriverCode publicstaticvoidMain(String[]args) { Graphg=newGraph(4); g.AddEdge(0,1); g.AddEdge(0,2); g.AddEdge(1,2); g.AddEdge(2,0); g.AddEdge(2,3); g.AddEdge(3,3); Console.WriteLine( "FollowingisDepthFirstTraversal" +"(startingfromvertex2)"); g.DFS(2); Console.ReadKey(); } } //Thiscodeiscontributedbytechno2mahiJavascriptOutput: FollowingisDepthFirstTraversal(startingfromvertex2) 2013ComplexityAnalysis: Timecomplexity:O(V+E),whereVisthenumberofverticesandEisthenumberofedgesinthegraph.SpaceComplexity:O(V),sinceanextravisitedarrayofsizeVisrequired. HandlingADisconnectedGraph:Solution: Thiswillhappenbyhandlingacornercase. Theabovecodetraversesonlytheverticesreachablefromagivensourcevertex.Alltheverticesmaynotbereachablefromagivenvertex,asinaDisconnectedgraph.TodoacompleteDFStraversalofsuchgraphs,runDFSfromallunvisitednodesafteraDFS. Therecursivefunctionremainsthesame.Algorithm: Createarecursivefunctionthattakestheindexofthenodeandavisitedarray.Markthecurrentnodeasvisitedandprintthenode.Traversealltheadjacentandunmarkednodesandcalltherecursivefunctionwiththeindexoftheadjacentnode.Runaloopfrom0tothenumberofverticesandcheckifthenodeisunvisitedinthepreviousDFS,calltherecursivefunctionwiththecurrentnode.Implementation: C++//C++programtoprintDFS //traversalforagivengiven //graph #include usingnamespacestd; classGraph{ //AfunctionusedbyDFS voidDFSUtil(intv); public: mapvisited; map>adj; //functiontoaddanedgetograph voidaddEdge(intv,intw); //printsDFStraversalofthecompletegraph voidDFS(); }; voidGraph::addEdge(intv,intw) { adj[v].push_back(w);//Addwtov’slist. } voidGraph::DFSUtil(intv) { //Markthecurrentnodeasvisitedandprintit visited[v]=true; cout<::iteratori; for(i=adj[v].begin();i!=adj[v].end();++i) if(!visited[*i]) DFSUtil(*i); } //ThefunctiontodoDFStraversal.Itusesrecursive //DFSUtil() voidGraph::DFS() { //CalltherecursivehelperfunctiontoprintDFS //traversalstartingfromallverticesonebyone for(autoi:adj) if(visited[i.first]==false) DFSUtil(i.first); } //DriverCode intmain() { //Createagraphgivenintheabovediagram Graphg; g.addEdge(0,1); g.addEdge(0,9); g.addEdge(1,2); g.addEdge(2,0); g.addEdge(2,3); g.addEdge(9,3); cout<adj[]; //Constructor @SuppressWarnings("unchecked")Graph(intv) { V=v; adj=newLinkedList[v]; for(inti=0;ii=adj[v].listIterator(); while(i.hasNext()){ intn=i.next(); if(!visited[n]) DFSUtil(n,visited); } } //ThefunctiontodoDFStraversal.Itusesrecursive //DFSUtil() voidDFS() { //Markalltheverticesasnotvisited(setas //falsebydefaultinjava) booleanvisited[]=newboolean[V]; //CalltherecursivehelperfunctiontoprintDFS //traversalstartingfromallverticesonebyone for(inti=0;i[]adj; //Constructor Graph(intv) { V=v; adj=newList[v]; for(inti=0;i(); } //Functiontoaddanedgeintothegraph voidaddEdge(intv,intw) { adj[v].Add(w);//Addwtov'slist. } //AfunctionusedbyDFS voidDFSUtil(intv,bool[]visited) { //Markthecurrent //nodeasvisitedandprintit visited[v]=true; Console.Write(v+""); //Recurforallthe //verticesadjacenttothis //vertex foreach(intiinadj[v]) { intn=i; if(!visited[n]) DFSUtil(n,visited); } } //Thefunctiontodo //DFStraversal.Itusesrecursive //DFSUtil() voidDFS() { //Markalltheverticesasnotvisited(setas //falsebydefaultinjava) bool[]visited=newbool[V]; //Calltherecursivehelper //functiontoprintDFS //traversalstartingfrom //allverticesonebyone for(inti=0;i //JavaScriptprogramtoprintDFS //traversalfromagivengiven //graph //Thisclassrepresentsa //directedgraphusingadjacency //listrepresentation classGraph { //Constructor constructor(v){ this.V=v; this.adj=newArray(v).fill([]); } //FunctiontoAddanedgeintothegraph AddEdge(v,w){ this.adj[v].push(w);//Addwtov'slist. } //AfunctionusedbyDFS DFSUtil(v,visited) { //Markthecurrent //nodeasvisitedandprintit visited[v]=true; document.write(v+""); //Recurforallthe //verticesadjacenttothis //vertex for(constnofthis.adj[v]){ if(!visited[n])this.DFSUtil(n,visited); } } //Thefunctiontodo //DFStraversal.Itusesrecursive //DFSUtil() DFS() { //Markalltheverticesasnotvisited(setas varvisited=newArray(this.V).fill(false); //Calltherecursivehelper //functiontoprintDFS //traversalstartingfrom //allverticesonebyone for(vari=0;i"); g.DFS(); //Thiscodeiscontributedbyrdtank. Output: FollowingisDepthFirstTraversal 01239ComplexityAnalysis: Timecomplexity:O(V+E),whereVisthenumberofverticesandEisthenumberofedgesinthegraph.SpaceComplexity:O(V),sinceanextravisitedarrayofsizeVisrequired.https://youtu.be/Y40bRyPQQr0 ApplicationsofDFS.Breadth-FirstTraversalforaGraphRecentArticlesonDFSWouldyoupleasewritecommentsifyoufindanythingincorrectorsharemoreinformationaboutthetopicdiscussedabove?MyPersonalNotes arrow_drop_upSave LikePreviousUniquepathscoveringeverynon-obstacleblockexactlyonceinagridNext BreadthFirstSearchorBFSforaGraphRecommendedArticlesPage:01,May1716,Mar2119,May1625,Mar1123,Oct1526,Jun2002,Jun1311,Mar1619,Jan1722,Sep1711,Jan1908,Sep2006,Jul2125,Apr1803,Aug1829,Jan1919,Feb1908,Oct1816,Dec2103,May1720,Mar1210,Aug2021,May2023,Nov21ArticleContributedBy:GeeksforGeeksVotefordifficultyCurrentdifficulty: EasyEasy Normal Medium Hard ExpertImprovedBy:speak2rk09techno2mahiprinciraj1992eshankvaishandrew1234draco_malf0ynikhil104akashgoacitisvishnudevkoushalsagar66rdtankavanitrachhadiya2155dheerajkumar33tanvimoharirbyromjomaaArticleTags:DFSgraph-basicsGraphPracticeTags:DFSGraphReportIssueWritingcodeincomment? Pleaseuseide.geeksforgeeks.org, generatelinkandsharethelinkhere. LoadCommentsWhat'sNewViewDetailsViewDetailsViewDetailsMostpopularinGraphMinimumnumberofswapsrequiredtosortanarrayTravellingSalesmanProblem|Set1(NaiveandDynamicProgramming)MinimumcosttoconnectallcitiesNumberofSimpleGraphwithNVerticesandMEdgesDisjointSet(OrUnion-Find)|Set1(DetectCycleinanUndirectedGraph)MorerelatedarticlesinGraphArticulationPoints(orCutVertices)inaGraphTravelingSalesmanProblem(TSP)ImplementationHamiltonianCycle|Backtracking-6StronglyConnectedComponentsDetectcycleinanundirectedgraph× Weusecookiestoensureyouhavethebestbrowsingexperienceonourwebsite.Byusingoursite,you acknowledgethatyouhavereadandunderstoodour CookiePolicy& PrivacyPolicy GotIt! StartYourCodingJourneyNow!Login Register