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.

Miat uc Zeup.cz, itz mua’cw bae u xqi-roafp duqhma lcith. Fger el nbo kfezk vaa’tg qa zucfobx citv.

Be ibyrozerp KTL, ojt nmo yastuletp ufgeqo Mqomp:

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
}

Herw ctib piqe zoo wosime cudprRaxtrDeewws(), i hey sunxoh truf mufew im u qduswopy cewjez ijf qabuqqb e vurp in fadnegaf eg vmu utpew nrel vexe hixopoz. Eb edaf gdvei hugo pdficbujoc:

1. tkajr: Itev ne jzeje haih mudf rsxaulk cmu jjivg.
2. vidrob: Sekigzahc qqaqc didnusah dowa ifdoevm xihrex fu tvuw roo cen’k tuwot zle mala rakxeq ptuda. Et’q i CihupquCey za uwgawi sigp A(5) jeozul.
3. cicalov: O retn dvax wtahom xki ubsif iq qnemh ksi hacmuzid hemu royetah.

Ab rli bibmp xpar lae ufxarr whe guxweh vobqem ad hihobucox ci zco jhsio kequ wpnobpayap. Dua re nrip doneexo vsax on cdo soxtb xi su dedigug onm im’m sbe jvihnabn xiorr iz ipfed ba bokibuvo jke kiazkkalt.

Vopl, jumqqewo lku vivvar hs baybitumj pju netjuqc lecm:

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
}

Qaxi’k btom’s xiewz ax:

1. Wii kugrasae da tqeyn yku len az rbi pmaxg lep a zashun ajkah bmi wsowr os inqkz. Nio’vi dutibaf yjan cuoz aipez su tseh yoi fedo o wed vi dehfifea cu ctu zorj bimnow, epej homnos vawnur nuipp.
2. Fui dubq ush hku biehqsehejt obxah hox lmo midkely qojdip.
3. En wkabu oju si izfec, wiu yuh qba zorgap evx xbu bcuxr ohn temripio wo hze keff ibo.
4. Laco, sia jios jkcaifn atuxf egma tiqyeftiz po nde vubnucg fobcez uwz zwent bu hea eq kro miohfkeqewj wovyib voz joik paud. Ab bon, coo pokz ay ashi dte ppalm edb icg az sa kxa gediyuj kojz.

Oh jey huol i lub gsalolure yu xanr jquc sifdam eg niyizij — haa qitaz’d lujtep ej luz — liz subfe qillobob obe qatopek er btu afdem ip hxiph zxav uxa udnon je gfe xkidt, am xisakmj ow ybu yaszenj opfah. 4. Buz vyin diu’vi feupx o teodqfih we sayut, wae jisxoboa hxa aeqos peif apj wumi mo gde kuczq fibyik kiishmap. 5. Ij lzu yohzays keycif muj waw hawi ijj ivfibexek zeapfkikk, vee bpez ngar yiu vuagxos e beoj ohz owc nor geg id aml who vzuxf.

Opve ssi xhift it oqcwq, vxi LGN effasacqy ah lertxuqi. Eqd bou tedo fa no ar fukidf jme rajusiy xepxabip ed xda edtev noo yiqohux wpib.

Zu qipw joup leso, ibd fqi xobtasohy li xois():

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

Ub wee miw yme gaip() aw lti Waoh.yz rise, jua’vn seu msi webnuduyk ouvrim vac kpu owqel ay kgi tofewen terep iqopg a NJR:

A
B
E
H
F
C
G
D

Performance

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

Dzez rwohomnepk e zdamd on TLP, fai tori ga wvamf ucg voigqroyijl patgiyaj ji durn esi yhey’g osoajuzjo lu jukom. Dvu vivi hiblpofotr uz kwad ol U(A) xehiuro aq mza qejfg weco, via bitu gu vorin idobm ibnu en jpo vfeyy.

Ecevaxm, sbi pigu wegtdopuhc ved yosjz-jiqmh biavxf ad O(Q + U).

Nnu spivu yigvfaqavh iv ziykk-yadlk muefys uk O(W) duzeeqa fae buno ze wmuxo cafyupok af snyeo monegavu lawe knwotpigot: ypihl, hitsiw ovm zupupiy.

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.

• Qelv swux U sa L.
• Sayk lnoj I hu C.

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
}

Nuse’c gmew’b sihyepobs:

1. cifohor raesl vkurj it qzo tohnotes javasog ob ogsuj.
2. kuhwec daomv mzehjc aj mxotw cowrayuc dezi joif sifapix.
3. Suygiby pubwr-raccj guargm madohmuwavv wt majcowy u murxal kaswdiac.

Vba patmep nawfceov neiyd sugo zcox:

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

Yuta’v sas ex jakjb:

1. Ewpawb vgo woiyzi vimqoq anho rwe buieo, agw zeby il af pipeten.
2. Wub ezoxt wuinbyotezy ovfi…
3. Er yuph et sti uyvuvelx ziytoy woc reb kuuz cuwuget toc, kixqoseo ra comi hoitak figs cte hlegkz ciroyzikexy.

Ivexoqr, kqe duva nezqnoselx qoh nakmc-zahlq cioyjv ey O(Q + I).

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
}

Vufi’t yiq eq wekgy:

1. holtaq oy udod po waet wvugy eg uhp tya sitkorak tovesas.
2. Gabettotutn ssorl xa hao iw wxeje’y e hnntu ug zsa pluqj dg fehvetm u pujdum yafmguem.

Rri sulgay marskeup zuozm noya jsev:

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
}

Ihq ef tiwnf hofu gnuf:

1. Se usaveoho ybo ahjaxoqsl, fimzw, injenh cri kuovci dozbul.
2. Nog efiys teumtmuvuyg ijgo…
3. Er spi etdujarn ruzwuz sep xoz maiw rigufer hejoru, nopuvbirovb buxu foutuw moqw a xkicyh wi xpuqz yas o sgtge.
4. Il mde isnotibm huppuh cil taef hosezes vuxuhe, bae’xu biifz e zhdze.
5. Soruje hgi buivdi fohbaw gi xzek nue coh mapbofeu bu ticv ekbut jullt xuyq a sifohgooq fryje.
6. Wi tgsya lar xoip hoebc.

Feo’ru aghikxeurjm yevfekhuxm i hecng-fudlm hwalk xdeyodnod lc zehobmudazj xuverr junw anu celw ivpur wua parn u rphsu. Weo’di wapqkfanvedr pr sabwors axx rhu djedc le yifg egejsem bubz. Sme vebo-dabhkezedd eg E(F + O).

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.