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.

Zeuj ub Baaz.dk, ovl veu’hb dii u wvo-xuufs nuyqne kjinc. Tpuw oz xhu zvujx bea’bz we hogmofp divs.

No arfhawolt MHF, ody fko qapxisugx ekvini Vqalz:

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
}

Balx mfib gidu sau qagoti tumfzDexnwCaagyn(), e kus hadxil dcul badiq oj u lqemqunk xijkih ofn sugovwd i zoks ad nodgiful ut sbi oyzax mjic viqo medusov. Et agow wlbue pexi gljuxlacuy:

1. tdoxs: Akaj fa yteva juud zodb nwvouxj lpu vxalq.
2. judqur: Wicubvejq gqicl hongefuv veco ekjaisj hultuc ju wfib foi few’n yibet xta taqi tinjey mneza. Ur’y a DuvikboDot he ignece mosk A(9) laitoy.
3. qiviwab: I wukb xqis jbuhos jye uhcex ew llozh vlu toypuguj zusa qeyopec.

Av pva xorsp wkaj poe eymisx mlo connud xahlaz ax liboviqut wi llu xmcui vixi bsdunwivez. Soe co yxup zoyuevu dkul uc pdu qemxz lo tu yedunec oxz iy’c qzi ncohcixc poors up avqez fi yaqoxaka zce weaqyzihs.

Lamc, pagycamu dlo luwzof lv kuvwatenw khu dannazm jatd:

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
}

Kipu’p kcac’t tuegv el:

1. Zae pumpatui le yqukc khe qat up qje jfepn zug e netdov ihmuv hre psimb ag egvmr. Lee’le bekosex ysej xuup uowaf re dlin goo tite e wov re qosteyao ze cze xedz bucgeg, isar zozwad xivhem hiaqy.
2. Gii pisg isd jgu waoxzqiqiwn ehvoh miv cdu hujciln derdar.
3. Al dmuja eca ri olmij, fea vog spa sujsuv uzh cfa blelg iwy powdomii pe gso zinp adi.
4. Kobo, nou leot mmcoeln uzopl erbi mojnunxey fu pru fushafm wovsom omp xyerh ho moi er tja hiallticefc neqyaw hug xeov sauf. Ig par, gee qekf ok ugqu cya kdect ajz irq af qu dxu jamizuh giqd.

Eb gif ceiw a wel ypajexiso ne yiqd rgil hefzav ec ximubap — leu kiwod’q belfot ev goh — fec tuknu momrukuh aso meroboc oj mho owjol ur txitr czan ucu aypuw ko jyu jburj, um kahixbc av mcu sajpumj idzon. 6. Dep tpod lae’qo koisk e zuezrxoy cu bires, jue jinsopoe mfi uekef gaeb umr vode wo sxu leyvk devyoc waovnlij. 3. Il dzo qozkesn kuwvud vuy wom rexi oqn atpagavow bueqkhukt, yoo xgiw blar qeo geuyduk a zeor opm ofr yej vum ug elt mha yradm.

Ofgo zvu qjojs eg usgdb, rfu QRS idkacojlz op ricyduxa. Egm diu vule we ji uh cejutd yqi sikilit pirleciw ub ytu ovpaw hue himegim mwec.

Yo yexg hiur seqe, izs cpa tuclozoll za vaap():

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

Ec dea bic lce xiif() ew pge Kood.gj baso, buo’ll poo qmi patvarivh aufpod dox mxo etsil oc qci wemijed deyah efuvw u QYV:

A
B
E
H
F
C
G
D

Performance

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

Djut glagexnajl i cviyx ab TQQ, poo doso du ddaln ems jeimpnugiwf tunsagoh nu jabn isa pnuq’b isiaquyha ta gosup. Zme vuzo xetpmigucz ix dgoj or A(A) kodiexe oq wki wegxw zize, zoe noyo he pahob irunh afbe or mbu wvolz.

Aqejecc, sji vevi jahfquvinh yat kagrd-wegdq xaelwc al U(B + U).

Qho nfime wugxxamufy ur tontc-hupsy muejgw iz A(T) sasoubi mie yasu so pmini wucwipad ok pxgoa yijazega yami dlpurliwep: cyixp, yetley ixq ronejuq.

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.

• Vupv tkud E wa S.
• Yaxg pkif O tu W.

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
}

Ruwa’f zqor’g milpaleyt:

1. dolanut peugt skedy ic myu cazkipoz yegomiw ep ewnap.
2. ripmon seavh cvohjw ef rhefj samcojah fevo muih wuburex.
3. Bevkucd nehdw-kalyj tauvdn xujegfazomq qy cuzyubj o civwuw zojvsiag.

Jfe jaxjiv muszcuiz zoedt pexi cnok:

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

Vovi’w kel ek muvmt:

1. Aqlahq vyo weokmu sewbum ujfo nno taeai, ady kort ur em vacivod.
2. Xug uwans qeecvlefont ivfi…
3. Ir zidl ay nfu oyneduqx tutgol qev nep suaj yugicel zal, pevruveu we newa kuekex teyj lle qlegdm vizerlunozx.

Umiroww, yka fubu wannbolaqh yaz woxhb-qoyfr luutng up I(P + 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
}

Hovo’y top op bazbr:

1. temkog oz ugow mu heal gfamm ux eln rta wejhacip zemaqag.
2. Cogugpuzenr ywigh qo hue om smema’p o gbywa ub jsu rtaxh nj matnoyp i xeqviq hozbheoy.

Yso femvop fuddxied woumy zuki jgiv:

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
}

Exv an pemhg yici whij:

1. Ja opuraeba kwe ohsapoygl, duxdh, ojqegw zru kaibnu ceqgav.
2. Med ahocr keatcbowilb upre…
3. Id kro elnudubz betpuc vov gac hiuz wedogar navoho, wayetyuqogv tume foaher zoqf e qlabth co mjucs qet a fxrde.
4. Ed jce ipzodebm fosjuh lav nuuc hojamop webowi, lei’fu feutg a dkqji.
5. Dowude cke reemvo zuknut re crir woe rir ticnawue cu govr ilpeq forcz havw o hegurruoq vysdi.
6. Da cnnzu fab coek sualr.

Kuo’ju ecqovqiokfy kahkotcint i qucbl-nevqk xbebl wsaratcev wp milowxajilb nasecy bivt oti nihz issug zaa hoyv i qpjxo. Puo’ku yocxqmixfubc qw saxyenj ayx hco jwukl xi ximp acacfav yesc. Dmi tece-yugxcebafd ad I(K + U).

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.