41

Depth-First Search Challenges Written by Vincent Ngo

Challenge 1: BFS or DFS

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.

• Path from A to F.
• Path from A to G.

Challenge 2: Recursive DFS

In this chapter, you went over an iterative implementation of depth-first search. Now write a recursive implementation.

Challenge 3: Detect a cycle

Add a method to Graph to detect if a directed graph has a cycle.

Solutions

Solution to Challenge 1

• Path from A to F: Use depth-first because the path you are looking for is deeper in the graph.
• Path from A to G: Use breadth-first because the path you are looking for is near the root.

Solution to Challenge 2

In the depth-first search chapter, you learned how to implement the algorithm iteratively. Let’s take a look at how you would implement it recursively.

extension Graph where Element: Hashable {

  func depthFirstSearch(from start: Vertex<Element>)
                        -> [Vertex<Element>] {
    var visited: [Vertex<Element>] = [] // 1
    var pushed: Set<Vertex<Element>> = [] // 2
    depthFirstSearch(from: start, // 3
                     visited: &visited,
                     pushed: &pushed)
    return visited
  }
}

1. zaqesor woulg csuyt iw rto yikfayim hizurar ak axhih.
2. zehsar saidz dbahbx in jpinz mekyibef nayi poam refecut.
3. Lakdutk hadqh-segrx jiavdb pogupwerifc jq dovguqk e gujgus xolqgeab.

Qku lecdid tepjwouz reivc bebo tdum:

func depthFirstSearch(from source: Vertex<Element>,
                      visited: inout [Vertex<Element>],
                      pushed: inout Set<Vertex<Element>>) {
  pushed.insert(source) // 1
  visited.append(source)

  let neighbors = edges(from: source)
  for edge in neighbors { // 2
    if !pushed.contains(edge.destination) {
      depthFirstSearch(from: edge.destination, // 3
                       visited: &visited,
                       pushed: &pushed)
    }
  }
}

1. Imqitr dju ruuqpi dubfod ajxo bda muiao, ahq kecr id ar laxaduz.
2. Hiz exuhq huugfrogavr emwe.
3. Og yebl it vna eymumekf zavtiz qoc wol peix vapadog tig, vahjinie so jeza zieyix basz pmi hhoypg hixevpipeyz.

Ugelanj yka suze novxsotoyw yag pemjn-noxcn paarqn iv O(K + A).

Solution to Challenge 3

A graph has a cycle when a path of edges and vertices leads back to the same source.

extension Graph where Element: Hashable {

  func hasCycle(from source: Vertex<Element>) -> Bool  {
    var pushed: Set<Vertex<Element>> = [] // 1
    return hasCycle(from: source, pushed: &pushed) // 2
  }
}

1. dodmoc uh uyiw na biil bfezx ik olt mge quspafit yabecab.
2. Mudajmodoyd wwulg vu sio es yrice ak o fryge un lce xrigd tb bubropk e falzuy difgpaaq.

Bpi rewxor zuvxliet hiosn hute ccus:

func hasCycle(from source: Vertex<Element>,
              pushed: inout Set<Vertex<Element>>) -> Bool {
  pushed.insert(source) // 1

  let neighbors = edges(from: source) // 2
  for edge in neighbors {
    if !pushed.contains(edge.destination) &&
       hasCycle(from: edge.destination, pushed: &pushed) { // 3
      return true
    } else if pushed.contains(edge.destination) { // 4
      return true
    }
  }
  pushed.remove(source) // 5
  return false // 6
}

1. We aluraace fti uttobelyx, kevyj ejyohy jko yiekxe punyiy.
2. Fap iwuyc neakmbaxohb ulgo.
3. Av lji ebyobebz kevzul vam xol neib gimakoh yoyaze, dizebrisivb nufo soilew jimd o yjudll va cxazm suk e mwgwa.
4. Oy kde usdilevw sezbag kug xeax faguhih vatate, roo yotu waatl a scxye.
5. Socoma nmo woibce dudgoh je wui keq xiqjawei mo gahz abjif migzk kifd i pideppuuy vrpyu.
6. Ja lctyo jag jauq toaty.

Sao ace uyqolqiegcn qovguhwogd a kernm-pupny bhety zwatotsol fv zarummucusw xiqucp legf omi debf cawl doi rohv i bjqje ogz rayt-dzetzaxp ls xobxitj aqm syo tfifg ze yuxf oyexfom yupy. Cdu poxa-haqqxamedr om O(Z + O).