Home iOS & Swift Books Data Structures & Algorithms in Swift

41
Depth-First Search Challenges Written by Vincent Ngo

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

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

Solution to Challenge 3

A graph is said to have a cycle when there is a path of edges and vertices leading 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
  }
}
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
}

Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.

Have feedback to share about the online reading experience? If you have feedback about the UI, UX, highlighting, or other features of our online readers, you can send them to the design team with the form below:

© 2021 Razeware LLC

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

Unlock Now

To highlight or take notes, you’ll need to own this book in a subscription or purchased by itself.