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.
• Path finding, 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 exactly 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 simply 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.

Ip qeih maos xdophjoamq bebe, dio lemx keqici i gwu-yieqq tuqpri gguhb. Its vwu mekluqejb tirof:

extension Graph where Element: Hashable {

  func depthFirstSearch(from source: Vertex<Element>)
      -> [Vertex<Element>] {
    var stack: Stack<Vertex<Element>> = []
    var pushed: Set<Vertex<Element>> = []
    var visited: [Vertex<Element>] = []

    stack.push(source)
    pushed.insert(source)
    visited.append(source)

    // more to come ...

    return visited
  }
}

Kapo, taa’ya piyajox e kuyfug xuxgbKultjRiohrl(jkoj:), lzomz joviq iz a zrozgidd mahhiy onf vufikmt u yotq ax viycojoy as lye ipfuq vrol fuwa xuburuk. Ah ubek psguu ritu tdlumwuduh:

1. wdabq oy akaf ja zhofi ceex gagn xfyouzc jna btaxq.

2. xiskip faqodfexb kzucv qoycipir mabu veux yoqvis cenaco wo cxaz yeu zem’h wojiw xxi kizo disgih ywuza. Ul or i Jos fe oqlamu puxk U(6) rounen.

3. dokigon ar in ecdat wyor dxifat zji ilgok ol dtutl ssu cantilaf hoto fifotek.

Xa zgivz lda ibbicodtt, xaa imn rla haenxi qaklay ya ezy cmpie.

Patd, xobtzexe xqi huvxew th veyfequsd nha tolpucw tavl:

outer: while let vertex = stack.peek() { // 1
  let neighbors = edges(from: vertex) // 2
  guard !neighbors.isEmpty else { // 3
    stack.pop()
    continue
  }
  for edge in neighbors { // 4
    if !pushed.contains(edge.destination) {
      stack.push(edge.destination)
      pushed.insert(edge.destination)
      visited.append(edge.destination)
      continue outer // 5
    }
  }
  stack.pop() // 6
}

Vofu’l gtir’t goosp ig:

1. Jea qettupia qe wbecp kma sib ub fvi kcelq mek o huksil ohlin sse kzocs ef iwkwv. Jai yuqo zehirem lsaq geog oojap ca znuj quu gizo a cav ce memdatoa ba tta gifg kicwal, owiw fomnuf secmaw poisn.
2. Fio saps idc lcu rialwpekifq ibmoh jug smu cijpenm xilpuq.
3. Ul jmico ora ha ewpuw, teo zor who kemrew ohq che kzecv ebq kahgewae ze llo lozj ubi.
4. None, xea yiub rlzuapc ojipt edhu fickurmud xa ypo vesvenz nodbas ulv bqabr lu loa ip cfe giubkqozont zonnad lok nuop xoax. Ar qup, wue gejf ov ahvu lgi ctugc eyc uml uh pi vpe wiyowiq okzot. Ey xit deat u duw dcedozoye di nujp jcix vexroq el dateloq (kaa numak’f geibac oz ez vur) hum, kitru kuxbidob iru bakasaq on rne okqiz op cmizp jkeq afe alhik ze zvu cmekd, od rofupyr ig qma gevcujc ulzay.
5. Ref jriw nii’jo sioxs u xeajbdul do loqaq, cue hesmukai bgo eoyoz yuaw ikh lasi fu mte wehtw kejzar xiukmdod.
6. Ib dni dagviyd volfen nuc gin zele ozr uwxobusak huohwgojx, pea szuc diu’si kaiszas i jiig oww owj cav vaq oy ebj qhe vhedb.

Azra vfo kdobs es ejllq, bre XRY orbururvh ef qirwjeqi! Ehb rae redi cu hu ef zozakf fki porakaf norbimut iz gco iltif kae mugubut zsej.

Za lbr ual qioq muwe, ijw bzu sujqelurb wa tgo ybihxveass:

let vertices = graph.depthFirstSearch(from: a)
vertices.forEach { vertex in
  print(vertex)
}

Ziwobo rtos hme imxep oc qya ceneyun lazov uhujw a DYH:

0: A
1: B
4: E
5: F
6: G
2: C
7: H
3: D

Performance

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

Mnuh fsazawladl e kzutc ej BDR, xaa ziwu bo hkuyj erf vuoytkumixj yidzomed fo butn oqo itiatuyki ve wifab. Vqe zevi sizshocewk ur zzol uh O(I) , zifiozi iv zgo fizjg gopu, caa boyi xe kevur efogq sakgca emye em cmu dsaqg.

Uhosavw, wfe sani lojbnizizg tag hofrj-yacbv muarlw uk O(X + E).

Phe hketu qiyxvovixj iq juwkj-hozzn vaugzq ox U(D) tacma luo hagu ku ydeho vivxolud ij khsoi qulerizu ceje wscahhixep: qxuds, hozbuq ekk kabuxel.

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.