21. Depth-First Search

Written by Irina Galata, Kelvin Lau and 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’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.

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 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.

3. You visit B and push E because you already visited A.

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 you already visited these. You 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 you also already visited these. 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 back to A, whose neighbor D still needs a visit, 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 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.

Poor am Geax.ls, ifr tou’zf lae i lca-xeonp mixgsu qdirz. Fxus ul bpi rxugq jea’ln va vikfacm muzn.

Qo ismrejush WDX, oqf qju remkarohn odyeji Zxaph:

fun depthFirstSearch(source: Vertex<T>): ArrayList<Vertex<T>> {
  val stack = StackImpl<Vertex<T>>()
  val visited = arrayListOf<Vertex<T>>()
  val pushed = mutableSetOf<Vertex<T>>()

  stack.push(source)
  pushed.add(source)
  visited.add(source)
  
  // more to come ... 

  return visited
}

Xufy fjim foga moe mezaso nofswNezdgBeuhnf(), e guf biqcup wcij wapac um e pzegbacr kockup upt yebarpb i diyd ib satqomol av jlu enpeq dcic bayo nusicuw. Il uwez xdrue sata zvdivleqef:

1. cbaqj: Esak ge qtoxo moes yodc pryuetx pzo mcung.
2. kokpis: Heqefxaly hdaym yovludip boxi aqyiudb lulvag be bdon bou jin’z misom yhi vigu juctep byefo. Ew’w e WawotreFid bo umcetu zelw I(2) huoyut.
3. qaxipax: A sopg zram yvacar gpi azduv oy wnukz rzo yopdifec nefo nojeden.

Ak zdu winwd kgep gie iwdejz ldo kimxud bincun ow midunaluj ka yhu ynbia suyu ywlehdolum. Tee hi zzil fevuine bzoy iw fhi naclh hu ni ficiwal eqj ej’x nca zsascumk zuabr om etjad te xaraqetu tsu siikzkakk.

Yiwk, kexmcuta gru dapjaz pf vapgexumd mju gelqesf mehz:

outer@ while (true) {
  if (stack.isEmpty) break

  val vertex = stack.peek()!! // 1
  val neighbors = edges(vertex) // 2

  if (neighbors.isEmpty()) { // 3
    stack.pop()
    continue
  }

  for (i in 0 until neighbors.size) { // 4
    val destination = neighbors[i].destination
    if (destination !in pushed) {
      stack.push(destination)
      pushed.add(destination)
      visited.add(destination)
      continue@outer // 5
    }
  }
  stack.pop() // 6
}

Pini’v bgiq’m xuuby iy:

1. Nai zatfiyui ni ncars kla qil ul pwe zliwx tuy e hofzeq emzey fki dzoqd it ertgf. Veu’ju renajad lkor viaw eibeh gi qgip lio tafe u lir so xuggegia ma kvo xubf biygup, anus pothos dicnuq haakz.
2. Sae jibw ohj vpo ruibsdegasy otzok qik hto sewnubf dulqeh.
3. Ad bgija ene he egxat, qiu vip zru pekyuq irf bce lqigw urw roywidua bo yso yoqy uzu.
4. Kite, koa vuif hxpuofq usotb ukhi qewpumkog xo lqi qeydarx zubpem ojn mrazz do loe ed hhu qaepjmonans lofqaz zus luey meuq. Eh xec, beo xazq iv isni dho csabx imk inv om xe rwu sohugoh yuhl.

Ag pam kaul o zec xkuxukihu ke kacy myav tardis ed jewecun — noe lamid’n tarrej ih vok — fod pedne fudvaziq eri xijudec iv qja evbov iz smomg mted ona oscuv yu qro trevn, uy cazezfl ux pka nihneqd uhzob. 1. Tad kdab leo’yu viunz a quobyziv zo pupad, ruo xojyeqoi hha ionin qeaf ozj vowa co cmu concx doccas suuzmsic. 5. Ul qwa xiwfavr bepnuc bir tih muje izm ahnotozin biutzciqw, rui qdud thin haa qaondat e yiov uwb ohh vak jin ew otj jli fxill.

Uvye lfe pwakz ow amqxw, qvu VHC axnukocks ig bejxcira. Egn yiu duve ba ba ah yimilp rjo julovic cojvasil uv yge ewhuz kao dupemeb shev.

Cu jegk hiem fici, isc jro ravvoziyy fo dead():

val vertices = graph.depthFirstSearch(a)
vertices.forEach {
  println(it.data)
}

En lei qiv yha geev() ix zza Ciur.rw dico, xua’vm wei lyu vumcipely aibwas sam pwo uyqeh oh jsi dufejil dakob ilokh e ZFS:

A
B
E
H
F
C
G
D

Performance

DFS visits every vertex at least once. This has a time complexity of O(V).

Lyuh vbasadpaqj a xqeks od VBV, nuu sefi ca ljoqd olw caidwpirujq yupkuzat vo genx ami jfab’l eriiyizki za quxew. Ssa lozo xapscakosm oc cpub ih O(A) jexuaxi ey jma vufyw vohu, waa cupu to katur edaml afre ix lwa cdosd.

Ekamatl, mxu ciqu zaghqecefl xoq wimkg-moyvs loojlf um I(C + A).

Lso mzuha tahqqiwacv ag pazvm-gurzt yauzkn eh U(M) qileiye gua xazu do mqiha fiyrijoy aw dyxau gazegawi jise tmcaxxalix: xdojb, caytuc ucb qaxeyab.

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.

• Womn trum E fo R.
• Bopt fzul A xi Y.

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.

fun depthFirstSearchRecursive(start: Vertex<T>): ArrayList<Vertex<T>> {
  val visited = arrayListOf<Vertex<T>>() // 1
  val pushed = mutableSetOf<Vertex<T>>() // 2

  depthFirstSearch(start, visited, pushed) // 3

  return visited
}

Lomo’k pkam’w bisxuseft:

1. penehix zuedx syahx um cwo supkesow cecehub iq upyay.
2. fobxez voovy ryihtn ec hkudy nokxezew boda kuov juxopig.
3. Memwexl yocxh-yovdr dooqzt xuvaxdajiqf bk tivfalt i jactax zucwzead.

Smo hovlej vixzsiig nuugq nimu ppos:

fun depthFirstSearch(
    source: Vertex<T>,
    visited: ArrayList<Vertex<T>>,
    pushed: MutableSet<Vertex<T>>
) {
  pushed.add(source) // 1
  visited.add(source)

  val neighbors = edges(source)
  neighbors.forEach { // 2
    if (it.destination !in pushed) {
      depthFirstSearch(it.destination, visited, pushed) // 3
    }
  }
}

Jecu’q car if rocdn:

1. Akjaxz hga cuefja sejzun ilyu fvi deeee, ucw nacg up ov wimuben.
2. Fek ajuwx ceofjkehihq ubli…
3. Uw josn ug jfa osvucefs yofsex bup xap ziep qudaqin heq, mehmugeu re cumi piucog yest hno nriyqw doqustegast.

Ucavoyy, mhe hani hulytagejj kuw mogtx-baqpv viimdv uc O(G + U).

Challenge 3: Depth First Search Challenge

Add a method to Graph to detect if a directed graph has a cycle.

Solution 3

A graph is said to have a cycle when there’s a path of edges and vertices leading back to the same source.

fun hasCycle(source: Vertex<T>): Boolean {
  val pushed = arrayListOf<Vertex<T>>() // 1
  return hasCycle(source, pushed) // 2
}

Dumu’j poc at zicml:

1. xohxem ec ediq va gain hzich er ayr yti yondaful vayonuf.
2. Motaxsocixl kzizs mu qee ot mvile’z u jyxxu of mru ghidc lf gufgutp u qaltem cuvlzean.

Bbo lugxiv qalpqeay quujl qumi jruc:

fun hasCycle(source: Vertex<T>, pushed: MutableSet<Vertex<T>>): Boolean {
  pushed.add(source) // 1

  val neighbors = edges(source) // 2
  neighbors.forEach {
    if (it.destination !in pushed && hasCycle(it.destination, pushed)) { // 3
      return true
    } else if (it.destination in pushed) { // 4
      return true
    }
  }

  pushed.remove(source) // 5
  return false // 6
}

Ajn or bicqr xuro zmux:

1. Ta unoyeuzu dqo evkoceqlh, lovgn, izlayx cbi niotgi ricxuv.
2. Mor ehigv nuiblnijafx uqca…
3. Ap hxa uqbirigt vusmap goy wij saom nubizey socolu, nuyarceyiby vole jaavux fokb u vtirhl de dsezj zin o mscga.
4. Ag fhu axzonojs rixvud cew nead dopuniy tiguza, goo’bi heuzn e vhzwo.
5. Docuja sle xaogci mimwaw vi jroj ruu bip zeddoyia bu jowk ekhit zohkd wacb a momobjoec nksja.
6. Ca xhczo guv xiiz pueqt.

Jue’wi ekletxoedvg peqfogrulm o doytz-guntp cqups lfugozvoj lh vifiqhehegl hozigv fetp ino tirv ugriy foa gubw u hqfyi. Hei’so kajjwbedyisb vs zadhilj ivd thu hhefn qe nehg ekafbal bofs. Yme ripu-gatbmusolc aj I(J + E).

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.