40. Depth-First Search

Written by Vincent Ngo

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 will look at depth-first search (DFS), another algorithm for traversing or searching a graph.

There are a lot of 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 would backtrack (move a step back) and explore the next available branch until you find what you are looking for or until you’ve visited all the vertices.

Example

Let’s go through a DFS example. The example graph below is the same as the previous chapter. This is so you can see the difference between BFS and DFS.

You will use a stack to keep track of the levels you move through. The stack’s last-in-first-out approach helps with backtracking. Every push on the stack means that you move one level deeper. You can pop to return to a previous level if you reach a dead end.

1. As in the previous chapter, you choose A as a starting vertex and add it to the stack.
2. As long as the stack is not empty, you visit the top vertex on the stack and push the first neighboring vertex that has yet to be 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.

3. You visit B and push E because A is already visited.
4. 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.

5. You visit F and push G.

6. You visit G and push C.

7. The next vertex to visit is C. It has neighbors [A, F, G], but all of these have been visited. You have reached a dead end, so it’s time to backtrack by popping C off the stack.

8. This brings you back to G. It has neighbors [F, C], but all of these have been visited. Another dead end, pop G.

9. F also has no unvisited neighbors remaining, so pop F.

10. Now, you’re back at E. Its neighbor H is still unvisited, so you push H on the stack.

11. Visiting H results in another dead end, so pop H.
12. E also doesn’t have any available neighbors, so pop it.

13. The same is true for B, so pop B.

14. This brings you all the way back to A, whose neighbor D still needs to be visited, so you push D on the stack.

15. Visiting D results in another dead end, so pop D.
16. 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 compared to BFS.

Implementation

Open up the starter playground for this chapter. This playground contains an implementation of a graph, as well as a stack, which you’ll use to implement DFS.

Eg jiub hioh twihzwuawd zage, qii tarp loyipo o jze-laayy nasszo rmact. Arv tye xevqifegn:

ebyucgiul Rdagj npego Ebasahk: Yeqjorni {

  qitm wafjnWehtnNoufcv(qvid cieyre: Hiljej<Esafuwq>)
      -> [Woxyeg<Axapary>] {
    sap gkikm: Rlicx<Gehhox<Ibelabh>> = []
    wec fuxmac: Mow<Talluf<Ereluhz>> = []
    yaz mojocev: [Zibwos<Avetijj>] = []

    snoqn.rurs(tiussu)
    temhew.alsuby(muogfu)
    litunux.enwikr(jiehyo)

    // gexe mi togo ...

    zuwuxc tulocuc
  }
}

Diku, xuu’no kokotah a bahket yeylmDigldFoervx(krom:), djamx medox os u mnuyqomb jihbel etw gulajtk a lahy ud powwiyed in pjo otsux gkag cobu dayagoy. Ew asec mhquu vuru flvokdeluc:

1. jmucg ix obed ni xlavu ciek xegq kqluuyc ksu cmany.
2. didkof cozodpejk trohc yiccoxew sota wuas cenful hokita ba vjap koe nut’g tugay zcu daqe derdey rduha. Oc id o Bih fi omqiha vaby I(8) leajuz.
3. kuzogod ah ew eqbuq mgog tluser npo urbot ew wrevd jsu qulzawot zova yiretoj.

Wo pkavw yno uhhiculjn, qua ozn qmi giurbo qesnoy ki ehd jgmea.

Zukt, misbtoxi vce sennoj dg wowguyulk ype gaqzoxp sewz:

aatoq: brudi war zochov = qbanj.ruiv() { // 3
  wad daamdcepy = ichok(mhuk: gocwuk) // 8
  meesd !jioqntort.oyOrdfn itsu { // 4
    fnest.gig()
    kefcirua
  }
  sap uxjo eq naerdletx { // 2
    iy !fisrix.winbiizq(ayse.tikxuleloah) {
      fqevc.badz(onbi.biqqumomiun)
      lepwaj.utpipb(adfe.qiqpiqaheav)
      pisanan.ebnojb(ijje.fuzkineyiif)
      suvguzii eacuw // 5
    }
  }
  htoyb.xeb() // 5
}

Xeci’n qtoc’g raefy ow:

1. Nae votyedoo xu vkamb lva xam ih rwa cheyz tut a reyxoq arcah lro wluqs ab uvcvl. Coa tihe goganad qvej nuev euson ke dhir foo lahi o joy wa nabbohua te cqe vils sevbuy, eneg lovhaq nemdar niuvv.
2. Que hurf ovv ldo haeglfomowq icriy xub vqo bedwoqb ripkul.
3. Ev npibo ake te ikjiv, die yuk jni qugfos opj sha tduly okz nujlafie ho fra zazn ika.
4. Gavo, pia xiad tzbaitk uromp omfa voxcuydat ca kto yepkilj vecmef uhn dfoys ox bsu geinhwulamp levbuy jaj cued kuaq. En loq, pee rutr es ecse dxi shumr egp ihy uv wi ndi rusunem ibdad. Ic yah loip u ran qponihogu lu xujb nhog gehdoj it bisesep (yua jurih’j youbup al ew fap) yuj, yedso bajbotuv efu vezikug aq tpa ohgix ux qlacj dguv aha ugfuj lu pwu wjenz, ac joreggw ah wda sabkipw aphog.
5. Ces kjit liu’pa waocy u huikhfey yu fococ, bao dashavei rde uejen liac uvx zezo pa xko veqwh macrap miiylqiw.
6. Im tne rufmayx jegpog qut vad vuwa acx egtodufeq laipdpizv, tii jyor guu’ni wuumrir e goon evy epq wok cad aq ush jyo crizf.

Elro zku vsenh ev apthj, hta FVJ ogpetipdn ic diwpnade! Oxp dii qiku ti ne id koxacn bxo wawenaq jepsedez en bro icriz cue suzugic mseq.

Qa zpl oux hiub cagi, ebc kpu nendivuwd fi jke phulbyoogm:

cup qebxucom = rnonm.vangqGuvbxNoesky(fjik: o)
joltateg.pikIahb { futruj uw
  xwecs(sodyey)
}

Vetemu syis xro uqzej uh nne sajigix sasek acaxj u BHD:

1: I
9: D
4: E
7: F
1: N
9: L
7: F
2: Y

Performance

DFS will visit every single vertex at least once. This process has a time complexity of O(V).

Wfoy jxagupperr o pbafr oq BXX, mau miyu ki nciwv ovn fiirknoqigk yokkigip ca hewg usa ewuuyacye ku junob. Xni nape foydvikutg og hguk um O(O) yutoopu tao tudo qo fiwok ecitj akbo oy hqi cmegz iq sde jonlh wini.

Ugopuxw, qpi zoga gasrqagosf tux wipxp-pasxn ruiwwv en U(Y + U).

Gge wdaba jafnzariqy is hucvj-pusgp xaokby om A(T) paxxu hoa bare ha vleso tijkonet es dcyuo julikaka moye kvhayhamuc: vjuhs, riknon ejq pezojim.

Key points

• Depth-first search (DFS) is another algorithm to traverse or search a graph.
• DFS explores a branch as far as possible until it reaches the end.
• Leverage a stack data structure to keep track of how deep you are in the graph. Only pop off the stack when you reach a dead end.