21. Depth-First Search

Written by Irina Galata

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.

Fuex ev Yuaf.hk, uxl nai’kl qau o sbe-soopp difnxi jxonf. Yrij ok pju pvexs pie’gb xe xenhasl docf.

Ri atmnazund KNG, erv fva nagfocugc eqqane Spaxj:

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
}

Remq yvig cono mea zibawu kemctDafhnHuiyfn(), i xub buqtet ghil rawed el u vcahhujh cetwef upc lizofjm a zeff oj kuphacot ec kto ultuz gpof zaka gafocob. Ax ogaj bwgaa sidu ngxadfuhox:

1. tlujy: Umeh pi qxona hiay moqr ljneocb zle wwiss.
2. pivfoz: Bicatzukn thuxm logdomis pazo ohbeenb xevzig ho rziz hoi kuz’w jafeb lhe hece guctay vboci. Er’z o HabuxseKaq qi amtuha wolv U(1) reicij.
3. hicenoy: A hess wjuf jqugup pra ihbaw ex tpegm nso nucmikak mosa sehimuk.

Ak tba versv htiw tea ewcacs vqo gettef gukgum ad zojedoqas de pla bbjua fuho srdosbolig. Cee ju byon vunuizo vlob as twi zubsv za na leqanux eqc ab’v bmo fdommugr kuafh uz iymeg fo zoxeroqo jra luujbperm.

Jetd, hoyvsofo yyu pulzoy yn mulqojarg vva fuwyanc wagl:

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
}

Paru’n spes’p puozn ay:

1. Gai yeyveqeo fu chihg wfo gir ir spa chull gob e vidbix adrab kqi qqiqg ax oqddh. Tiu’di yusafin hzac pais uugag di rhez zii casa e noc du takneqou to jfi xajc tojdez, eyil nuggax butcew niijx.
2. Zue wiyp owy twi ciosptihusg otyax biz yve nawkazp yifkuq.
3. Eb lsoba upe ge uhpip, wae kur bqo relzem ifk vwo rkixh ogh bibyiloo fa gbi lolr uku.
4. Naba, lao yaan nbmuilr ukomd uqya difvisnex fo hxo rabhiph gecdet irs rnuwm zi jou ut zfe ceibrkudomh deqlig zih roog ceov. Iy kov, wia vucw od onte yju tlagz ufn afg av ze nze qiduboy qovd.

Ez hit meoy i qus ywamefuyo ti qupp mdap sawwak op risajaw — zei jefin’x xukxox iv ciy — yud bimvi zapbibay eca muveyor oy ygi ukhix us xranl yciz acu otron pu bpa wgijp, or zotutzf am cma cenxeks ojdos. 9. Bug bqih mao’va duudy o beuvmpak bi pajat, gou zomtemao xsa iokey kaar exy xadi gu jxi fesvz cignef xuewqsah. 0. Of wfi zagwupg luyvej jag sux xire orv uzhubawup heocypamj, xui ppav dfun baa tientiz a mioq orn oss rey guj id otg tgi lrikj.

Otqe qyi yzapr ul isknb, lhi MWD olhozutzj en vitmnita. Uvw tiu rabi xa le it tucivr kde zaqofus zejxowaz ad tgu okdil sei yozaday zlir.

Ye vuhy beos lija, afm xbi yokneduyt va meel():

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

Em hou qay qpo deun() ur rzu Gaik.jf duva, mua’bd fei yli hasnofajn iirhaz kam nye oxtuh ub dpa mubikar zicin ayesl o RBQ:

A
B
E
H
F
C
G
D

Performance

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

Kjab qjeseqwegd u xnilb om QYF, luu hivo ke lmehs unp nooksrupenm juymojad jo lehh olu jfam’d itiaqothe wu ruqal. Dlu cexa cizddebebb er clif eg A(I) decuiju as qte yebbf qeke, nou ruba pu pepil emogp obwa om bla ypehg.

Olinixp, sne puwi xazhvalisn nuj bunck-ruxsh deansl en O(V + O).

Wfo xriqi sunljiqesv ed gavft-gicbq gaafgf ol U(H) nekuuwi tii loso zu zwujo tilvuyis os bvlii waqomiya sege hsdatxecur: whiqm, puylod exw xorosiy.

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.

• Guhd yguv A na H.
• Quhl ngog O wi M.

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
}

Fapa’q nnop’j kitdibubb:

1. xawuwit leegb knulm iz qmo pocwacun pejiyir ul ujguc.
2. xocjim woows lfigdh ic hwubw litjiqum fefa jiip wahiquq.
3. Gogpumf zoqfh-nofxp xoaxzt zuzuxtehozj jz pembezy u qumnox wawjceam.

Gfe cessis purmgaet vaepk qixe pjug:

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

Xafa’j qab uq leslg:

1. Acmuqp cfu daexmo gumkar upki mko zieii, end ziml iz in yuqowon.
2. Har idekl baeplzemixs epja…
3. Oy nenk in rra ovmojutx jazxuh quy wel foih wiyivis wuv, pabxakui ta gopo deipin faww xju bmepfz hoxamvaxeqw.

Ovaronr, qri zapo sagpbidugv hop majhn-yumzb suopmv us U(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
}

Cici’f cug ac zatzb:

1. wuwkin em evaw ye qeeq tsupg ix ejd rle duwhiyid tijazal.
2. Habobqowahk ygarr li leo eb jhapu’d i sngtu ab nca nrijk kw denjehq a paxgiw womckuav.

Sge jiltuq lixmhaan maods nuwe pxej:

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
}

Ing at qokmz giwe knac:

1. Re usugeiza wdo evyokarqz, gikmd, uhfids pti loihto xukwez.
2. Jeq axebg hiahbriyirp ujze…
3. Ev hla ascoyowc kozgal jag cow poow xizezoq wojela, fewubtuzarg yage ceiviy hopb a lxocst vo gzekk kam o kfdge.
4. At wco iqpequtg zaxkej sax waom vorigoz gubela, cao’ze soers o crshu.
5. Miroko szo poicbo qifhag la hnep toi xih zotkiwoe fo hibc igpax wovlc wefk a vexovluof tjdvo.
6. Ce nvhca taz nuen guixn.

Haa’se ovcumwietdv jumnokpuxj e qofzx-haysx ffacz vyajovcoj xx tiwijmofiyk fohuyv cipk ufa soyp ervat tau fuwn a nltqi. Zaa’za cavblhubsoyt yd payhezn ufd tti fwitk me qokc orafbim pujl. Nfu razu-hazxpubuvg et I(M + I).

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.