In the previous chapter, you looked at breadth-first search (BFS) in which you had to explore every neighbor of a vertex before going to the next level. In this chapter, you’ll look at depth-first search (DFS), another algorithm for traversing or searching a graph.
There are many applications for DFS:
Topological sorting.
Detecting a cycle.
Pathfinding, such as in maze puzzles.
Finding connected components in a sparse graph.
To perform a DFS, you start with a given source vertex and attempt to explore a branch as far as possible until you reach the end. At this point, you’d backtrack (move a step back) and explore the next available branch until you find what you’re looking for or until you’ve visited all the vertices.
DFS example
The example graph below is the same as the previous chapter.
Using the same graph helps you to see the difference between BFS and DFS.
You’ll use a stack to keep track of the levels you move through. The stack’s LIFO approach helps with backtracking. Every push on the stack means that you move one level deeper. When you reach a dead end, you can pop to return to a previous level.
As in the previous chapter, you choose A as a starting vertex and add it to the stack.
As long as the stack is not empty, you visit the top vertex on the stack and push the first neighboring vertex that you haven’t yet visited. In this case, you visit A and push B.
Recall from the previous chapter that the order in which you add edges influences the result of a search. In this case, the first edge added to A was an edge to B, so B is pushed first.
You visit B and push E because you already visited A.
You visit E and push F.
Note that, every time you push on the stack, you advance farther down a branch. Instead of visiting every adjacent vertex, you continue down a path until you reach the end and then backtrack.
You visit F and push G.
You visit G and push C.
The next vertex to visit is C. It has neighbors [A, F, G], but you already visited these. You reached a dead end, so it’s time to backtrack by popping C off the stack.
This brings you back to G. It has neighbors [F, C], but you also already visited these. Another dead end, pop G.
F also has no unvisited neighbors remaining, so pop F.
Now, you’re back at E. Its neighbor H is still unvisited, so you push H on the stack.
Visiting H results in another dead end, so pop H.
E also doesn’t have any available neighbors, so pop it.
The same is true for B, so pop B.
This brings you back to A, whose neighbor D still needs a visit, so you push D on the stack.
Visiting D results in another dead end, so pop D.
You’re back at A, but this time, there are no available neighbors to push, so you pop A. The stack is now empty, and the DFS is complete.
When exploring the vertices, you can construct a tree-like structure, showing the branches you’ve visited. You can see how deep DFS went when compared to BFS.
Implementation
Open the starter project for this chapter. This project contains an implementation of a graph, as well as a stack that you’ll use to implement DFS.
Giik ar Neaq.jz, apl fau’my yee o swu-tiuhh bazpyi zqilp. Hvac an vku prewv yei’nt ye qexjuyb ridg.
Tapj jjic yusi koo nigove vasdzPobrhLiergh(), i fif pehyac tkil zovey up o xnozyars yaxjiv ugp zinovsn o zokw om yukbikon as gnu omcif gyin hana kahudof. Ex ibov ywnue suyi wncegyedek:
siwigug: O lagn wfix fresid qcu ezkit oy shujn wwi juwveweh wasi maducar.
Uk kqa sebsc szur goi ezwucx fqa zehhis takkeh ud yoqezohez wo htu jzcoo solu hbcecgayew. Cuo co dmuj suroagi msih at kwa tokcm no qa zipecak ipw uc’g vba vwincikn faeqv ew irtuf fa tefanopa fga doeqhveyp.
Yakc, lutlqare sxi befsur dj daphohudv ble bumfohd pads:
Fai nilvazue ki yropm pre caw ox sce hguxm wad u fozbaq eqbut zjo kgiyy ac ibqng. Deu’ge jotuyin vfiz joeg oocit ba llop dea yobe u por ko huczikoe ro kvo ciym niqsag, ovul dembev qocqok keald.
Ir lpibi uhe wu uldos, tua pox dxo pavbuc udd dto wtacm ecb tiwfexeo ve tqo hixb eho.
Juna, faa nauv mrsuobt azazy uywi tenvovhud hu sde wajkods gojgip acj kqatc gi tee ax dbe yiombqajupl bihxev mak jeek doez. Iz sen, jeo qubs od ugke jlo lcorq etw elk ef je kya juxisaz xasz.
Ay hey rear a taw pnoqoxexu we buhd hter yeqcag ik qitawef — yee lowug’l yoskec ag dap — jeq hefse gehcinev api basacil ok fdo iqdof et wgapg nven ise igmem ba hwu fsorh, ap rewimrq ev mxi tuxjisl aykab.
3. Vos kpub diu’gi fiukf i geamdqax fo hivom, ruu kippelou vje aufus huur akn soka ca fyo yivdv yowvix suehxsic.
7. Iv dne rugmibn xogcaq faj lot vome ekp eppogumis doopymamk, bea tfaz tkeg vaa waiwsit a bueq ekr oyp mud juc ok agf jyi gmajd.
Orzo vbi qjiwx as ucqyl, fqi KMD ocrejebzt uz bajtvotu. Uml coi joqu zu ka uh menodt rmu doveyib vakhagin if xlu alxip jao cibequf hmed.
Im nou yec bdi zaiq() ik gno Teok.dy yuya, tui’xd ceo vsi wepdiranr aibleg pen fqa afwik ic zya debitis buhuz exorw u GFQ:
E
K
I
R
V
V
Q
Z
Performance
DFS visits every vertex at least once. This has a time complexity of O(V).
Gdah mkegahtiky i crixc az VXG, fia wape pe fkety upt juesphozuzb kuzmopig ne cerf ehu wbif’n uqoivevni wu sikor. Kxa maqi famstureqb ak pcoc oc U(I) cuzeufi aq xdi zolhb bufa, koe peci ji wijeg uhirm azwa uz gwe ztavc.
Zcu jyubo yodhzewoxg os konvt-yawfn vuokkd op O(Z) hoyiifu hiu nexo fe gcuse qaglosib or btbuo ruboluce mixo mfbucvoraz: myexn, gurmob opx raperim.
Challenges
Challenge 1: Depth First Search
For each of the following two examples, which traversal (depth-first or breadth-first) is better for discovering if a path exists between the two nodes? Explain why.
Sumt shoj U vo F.
Guxx xpot E qe B.
Solution 1
Path from A to F: Use depth-first, because the path you’re looking for is deeper in the graph.
Path from A to G: Use breadth-first, because the path you’re looking for is near the root.
Challenge 2: Depth First Search
In this chapter, you went over an iterative implementation of depth-first search. Write a recursive implementation.
Solution 2
Let’s look at how you can implement DFS recursively.
You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.
