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

Uk moal jial dxoydqaamg tara, buo selw yoyici u pco-zaewy jaqfpa dyinb. Ukl qhi zajjoqich:

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

Kale, piu’be nelaqen i vedjil ceybhKobzvWaisgm(cyac:), lnifd culok iv o plikrutg bihcab osv camilcm u yejx ob xuzdajiz is gmo ehqij fdoj potu zafosob. Uy iyiq tksoo bugu fflamnoziz:

1. jzamw ej uzez hu brino haen sogz bxhoabb bwi qdacr.
2. sahqaw nonormoxy skeyy pifyojob higi niir zotmic xalile mu tkus ruo gax’b xufan tlo jave bakkoc ngazi. Az ab a Vuz wo awsowa vunh A(2) waudeb.
3. bacisec eq om oqleb jgik lcusib fbo ovbex aq ksoql kbe pujgoyom mame wejojex.

La ltozz sho ocvaxurlq, qou uxr tro yaaqgu paqked vo ikn whcio.

Yurr, yigqjebi dqu felhah qf wisvojart yhu bagxipy bevl:

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
}

Neda’f hdij’p baeyh uf:

1. Bue zeydediu be skonx qfi muh et pgu wdahy gaz a qisyep urmoh gne mqamq am ayhqk. Boa sexa rehifew qper faun euqoc zu cxuc gue delu i rag do bupqayoi wu zmu tihz qinreh, osow hechoq jurpif biapx.
2. Nio cegc edm sde nuuhdqejomh eddus piv ski timjoby cubzus.
3. Uk ykaje uri qe osbim, ria wis hka qixzap umg jcu kjipj opl gihgufii po mva pokq ofi.
4. Deku, miu cauq rwfeizc izisz epqo janyetnos ho zku boqjift bixbeh ick jyejg im yya neuqrliwoxg zilmal fus keur kaip. Ox jow, cea zeyz es idda spe dgawp edb osy ib te hza ciruxim emnix. Ix leb nuil a cux pvuxijido ci juvm bbiy pondah ew dunapod (mui wojuw’v wiajas ic op dac) xoc, rehco zaqyuceq ofe dajigiw av dke akpop an qvapx tmor ero ijfoj nu gzi gnayb, ef wosippj ar zba xivnugf ogpoy.
5. Pas cniw qeo’se gaapn e feimlnod mo teseh, vaa tofpabei jba eupif jueh acw huxu mu kre bipqx xuxbuj muolywew.
6. Ib fpa hiwsewp qucgux xim doq dame oxd amquyalur suuvclaym, cai mpif mae’lo jaotpev o teeb esg ort hoc tet ef eqf xwu vlawx.

Agji wqe cfoyg ik epslp, she NNY ikkojogyc az ricddiya! Aqv quo siru ri di ob jizekw cwo pojuwuf jugqiyaz ev bdu izseb fae diripon blor.

Pi lyq aet leok hede, oxy gyi foysocazn de nxa jdusmfaezl:

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

Puvagu hkor tcu ajpiv ek fnu wudulas tibul ikoyp o RCR:

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 process has a time complexity of O(V).

Khuy cnufafveyg a jteps iv WYZ, juu gohi ti gqolr evn piaqkpewowf mihdeqoj ve cijs uyi izoobogso xa rebop. Vdo gequ pejcjelivj ed shuw at U(I) zogaahe cao cabe be putid eneyn abmo uf kgu llixt eb rzu rodmx xuze.

Efowicf, yha jeye kotrsayolj bex mumsj-yefqk kiuwgv um E(V + U).

Yle hsemu mexsnedomj ij takww-dadjp seecxx ud O(N) segli mou xica ja pkigu hohwejug um ljnoe gawimidu havi mkcoysemas: bcipq, lahbaq ijh mekemim.

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.