Home iOS & Swift Books Data Structures & Algorithms in Swift

39
Breadth-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: Maximum queue size

For the following undirected graph, list the maximum number of items ever in the queue. Assume that the starting vertex is A.

Challenge 2: Iterative BFS

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

Challenge 3: Disconnected Graph

Add a method to Graph to detect if a graph is disconnected. An example of a disconnected graph is shown below:

var allVertices: [Vertex<Element>] { get }

Solutions

Solution to Challenge 1

The maximum number of items ever in the queue is 3.

Solution to Challenge 2

In the breadth 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 bfs(from source: Vertex<Element>) -> [Vertex<Element>] {
    var queue = QueueStack<Vertex<Element>>() // 1
    var enqueued: Set<Vertex<Element>> = [] // 2
    var visited: [Vertex<Element>] = [] // 3

    // 4
    queue.enqueue(source)
    enqueued.insert(source)
    // 5
    bfs(queue: &queue, enqueued: &enqueued, visited: &visited)
    // 6
    return visited
  }
}
private func bfs(queue: inout QueueStack<Vertex<Element>>,
                 enqueued: inout Set<Vertex<Element>>,
                 visited: inout [Vertex<Element>]) {
  guard let vertex = queue.dequeue() else { // 1
    return
  }
  visited.append(vertex) // 2
  let neighborEdges = edges(from: vertex) // 3
  neighborEdges.forEach { edge in
    if !enqueued.contains(edge.destination) { // 4
      queue.enqueue(edge.destination)
      enqueued.insert(edge.destination)
    }
  }
  // 5
  bfs(queue: &queue, enqueued: &enqueued, visited: &visited)
}

Solution to Challenge 3

A graph is said to be disconnected if no path exists between two nodes.

extension Graph where Element: Hashable {

  func isDisconnected() -> Bool {
    guard let firstVertex = allVertices.first else { // 1
      return false
    }
    let visited = breadthFirstSearch(from: firstVertex) // 2
    for vertex in allVertices { // 3
      if !visited.contains(vertex) {
        return true
      }
    }
    return false
  }
}

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.