Depth First Search (DFS) Algorithm - Programiz

Python, Java and C/C++ Examples CourseIndex ExploreProgramiz Python JavaScript C C++ Java Kotlin Swift C# DSA StartLearningDSA PopularTutorials QuicksortAlgorithm MergeSortAlgorithm LinkedListDataStructure HashTableDataStructure DynamicProgramming Python JavaScript C C++ Java Kotlin Swift C# DSA StartLearningDSA PopularTutorials QuicksortAlgorithm MergeSortAlgorithm LinkedListDataStructure HashTableDataStructure DynamicProgramming Viewalltutorials Python JavaScript C C++ Java Kotlin ExplorePythonExamples PopularExamples Addtwonumbers Checkprimenumber Findthefactorialofanumber PrinttheFibonaccisequence Checkleapyear Viewallexamples DSAIntroduction Whatisanalgorithm? DataStructureandTypes WhylearnDSA? AsymptoticNotations MasterTheorem DivideandConquerAlgorithm DataStructures(I) Stack Queue TypesofQueue CircularQueue PriorityQueue Deque DataStructures(II) LinkedList LinkedListOperations TypesofLinkedList HashTable HeapDataStructure FibonacciHeap DecreaseKeyandDeleteNodeOperationsonaFibonacciHeap TreebasedDSA(I) TreeDataStructure TreeTraversal BinaryTree FullBinaryTree PerfectBinaryTree CompleteBinaryTree BalancedBinaryTree BinarySearchTree AVLTree TreebasedDSA(II) BTree InsertioninaB-tree DeletionfromaB-tree B+Tree InsertiononaB+Tree DeletionfromaB+Tree Red-BlackTree Red-BlackTreeInsertion Red-BlackTreeDeletion GraphbasedDSA GraphDataStructure SpanningTree StronglyConnectedComponents AdjacencyMatrix AdjacencyList DFSAlgorithm Breadth-firstSearch BellmanFord'sAlgorithm SortingandSearchingAlgorithms BubbleSort SelectionSort InsertionSort MergeSort Quicksort CountingSort RadixSort BucketSort HeapSort ShellSort LinearSearch BinarySearch GreedyAlgorithms GreedyAlgorithm Ford-FulkersonAlgorithm Dijkstra'sAlgorithm Kruskal'sAlgorithm Prim'sAlgorithm HuffmanCoding DynamicProgramming DynamicProgramming Floyd-WarshallAlgorithm LongestCommonSequence OtherAlgorithms BacktrackingAlgorithm Rabin-KarpAlgorithm RelatedTopics Breadthfirstsearch AdjacencyList GraphDataStucture StronglyConnectedComponents Dijkstra'sAlgorithm AdjacencyMatrix DepthFirstSearch(DFS) Inthistutorial,youwilllearnaboutdepthfirstsearchalgorithmwithexamplesandpseudocode.Also,youwilllearntoimplementDFSinC,Java,Python,andC++. DepthfirstSearchorDepthfirsttraversalisarecursivealgorithmforsearchingalltheverticesofagraphortreedatastructure.Traversalmeansvisitingallthenodesofagraph. DepthFirstSearchAlgorithm AstandardDFSimplementationputseachvertexofthegraphintooneoftwocategories: Visited NotVisited Thepurposeofthealgorithmistomarkeachvertexasvisitedwhileavoidingcycles. TheDFSalgorithmworksasfollows: Startbyputtinganyoneofthegraph'sverticesontopofastack. Takethetopitemofthestackandaddittothevisitedlist. Createalistofthatvertex'sadjacentnodes.Addtheoneswhicharen'tinthevisitedlisttothetopofthestack. Keeprepeatingsteps2and3untilthestackisempty. DepthFirstSearchExample Let'sseehowtheDepthFirstSearchalgorithmworkswithanexample.Weuseanundirectedgraphwith5vertices. Undirectedgraphwith5verticesWestartfromvertex0,theDFSalgorithmstartsbyputtingitintheVisitedlistandputtingallitsadjacentverticesinthestack. VisittheelementandputitinthevisitedlistNext,wevisittheelementatthetopofstacki.e.1andgotoitsadjacentnodes.Since0hasalreadybeenvisited,wevisit2instead. Visittheelementatthetopofstack Vertex2hasanunvisitedadjacentvertexin4,soweaddthattothetopofthestackandvisitit. Vertex2hasanunvisitedadjacentvertexin4,soweaddthattothetopofthestackandvisitit.Vertex2hasanunvisitedadjacentvertexin4,soweaddthattothetopofthestackandvisitit.Afterwevisitthelastelement3,itdoesn'thaveanyunvisitedadjacentnodes,sowehavecompletedtheDepthFirstTraversalofthegraph. Afterwevisitthelastelement3,itdoesn'thaveanyunvisitedadjacentnodes,sowehavecompletedtheDepthFirstTraversalofthegraph.DFSPseudocode(recursiveimplementation) ThepseudocodeforDFSisshownbelow.Intheinit()function,noticethatweruntheDFSfunctiononeverynode.Thisisbecausethegraphmighthavetwodifferentdisconnectedpartssotomakesurethatwecovereveryvertex,wecanalsoruntheDFSalgorithmoneverynode. DFS(G,u) u.visited=true foreachv∈G.Adj[u] ifv.visited==false DFS(G,v) init(){ Foreachu∈G u.visited=false Foreachu∈G DFS(G,u) } DFSImplementationinPython,JavaandC/C++ ThecodefortheDepthFirstSearchAlgorithmwithanexampleisshownbelow.Thecodehasbeensimplifiedsothatwecanfocusonthealgorithmratherthanotherdetails. Python Java C C++ #DFSalgorithminPython #DFSalgorithm defdfs(graph,start,visited=None): ifvisitedisNone: visited=set() visited.add(start) print(start) fornextingraph[start]-visited: dfs(graph,next,visited) returnvisited graph={'0':set(['1','2']), '1':set(['0','3','4']), '2':set(['0']), '3':set(['1']), '4':set(['2','3'])} dfs(graph,'0') //DFSalgorithminJava importjava.util.*; classGraph{ privateLinkedListadjLists[]; privatebooleanvisited[]; //Graphcreation Graph(intvertices){ adjLists=newLinkedList[vertices]; visited=newboolean[vertices]; for(inti=0;i(); } //Addedges voidaddEdge(intsrc,intdest){ adjLists[src].add(dest); } //DFSalgorithm voidDFS(intvertex){ visited[vertex]=true; System.out.print(vertex+""); Iteratorite=adjLists[vertex].listIterator(); while(ite.hasNext()){ intadj=ite.next(); if(!visited[adj]) DFS(adj); } } publicstaticvoidmain(Stringargs[]){ Graphg=newGraph(4); g.addEdge(0,1); g.addEdge(0,2); g.addEdge(1,2); g.addEdge(2,3); System.out.println("FollowingisDepthFirstTraversal"); g.DFS(2); } } //DFSalgorithminC #include #include structnode{ intvertex; structnode*next; }; structnode*createNode(intv); structGraph{ intnumVertices; int*visited; //Weneedint**tostoreatwodimensionalarray. //Similary,weneedstructnode**tostoreanarrayofLinkedlists structnode**adjLists; }; //DFSalgo voidDFS(structGraph*graph,intvertex){ structnode*adjList=graph->adjLists[vertex]; structnode*temp=adjList; graph->visited[vertex]=1; printf("Visited%d\n",vertex); while(temp!=NULL){ intconnectedVertex=temp->vertex; if(graph->visited[connectedVertex]==0){ DFS(graph,connectedVertex); } temp=temp->next; } } //Createanode structnode*createNode(intv){ structnode*newNode=malloc(sizeof(structnode)); newNode->vertex=v; newNode->next=NULL; returnnewNode; } //Creategraph structGraph*createGraph(intvertices){ structGraph*graph=malloc(sizeof(structGraph)); graph->numVertices=vertices; graph->adjLists=malloc(vertices*sizeof(structnode*)); graph->visited=malloc(vertices*sizeof(int)); inti; for(i=0;iadjLists[i]=NULL; graph->visited[i]=0; } returngraph; } //Addedge voidaddEdge(structGraph*graph,intsrc,intdest){ //Addedgefromsrctodest structnode*newNode=createNode(dest); newNode->next=graph->adjLists[src]; graph->adjLists[src]=newNode; //Addedgefromdesttosrc newNode=createNode(src); newNode->next=graph->adjLists[dest]; graph->adjLists[dest]=newNode; } //Printthegraph voidprintGraph(structGraph*graph){ intv; for(v=0;vnumVertices;v++){ structnode*temp=graph->adjLists[v]; printf("\nAdjacencylistofvertex%d\n",v); while(temp){ printf("%d->",temp->vertex); temp=temp->next; } printf("\n"); } } intmain(){ structGraph*graph=createGraph(4); addEdge(graph,0,1); addEdge(graph,0,2); addEdge(graph,1,2); addEdge(graph,2,3); printGraph(graph); DFS(graph,2); return0; } //DFSalgorithminC++ #include #include usingnamespacestd; classGraph{ intnumVertices; list*adjLists; bool*visited; public: Graph(intV); voidaddEdge(intsrc,intdest); voidDFS(intvertex); }; //Initializegraph Graph::Graph(intvertices){ numVertices=vertices; adjLists=newlist[vertices]; visited=newbool[vertices]; } //Addedges voidGraph::addEdge(intsrc,intdest){ adjLists[src].push_front(dest); } //DFSalgorithm voidGraph::DFS(intvertex){ visited[vertex]=true; listadjList=adjLists[vertex]; cout<::iteratori; for(i=adjList.begin();i!=adjList.end();++i) if(!visited[*i]) DFS(*i); } intmain(){ Graphg(4); g.addEdge(0,1); g.addEdge(0,2); g.addEdge(1,2); g.addEdge(2,3); g.DFS(2); return0; } ComplexityofDepthFirstSearch ThetimecomplexityoftheDFSalgorithmisrepresentedintheformofO(V+E),whereVisthenumberofnodesandEisthenumberofedges. ThespacecomplexityofthealgorithmisO(V). ApplicationofDFSAlgorithm Forfindingthepath Totestifthegraphisbipartite Forfindingthestronglyconnectedcomponentsofagraph Fordetectingcyclesinagraph TableofContents Introduction DFSalgorithm DFSexample DFSpseudocode(recursiveimplementation) Python,JavaandC/C++Examples PreviousTutorial: AdjacencyList NextTutorial: Breadth-firstSearch Shareon: Didyoufindthisarticlehelpful? Sorryaboutthat. Howcanweimproveit? Feedback* Leavethisfieldblank RelatedTutorialsDS&AlgorithmsBreadthfirstsearchDS&AlgorithmsAdjacencyListDS&AlgorithmsStronglyConnectedComponentsDS&AlgorithmsGraphDataStucture