Chapters

Hide chapters

Data Structures & Algorithms in Swift

Third Edition · iOS 13 · Swift 5.1 · Xcode 11

Before You Begin

Section 0: 3 chapters
Show chapters Hide chapters

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.

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.
© 2024 Kodeco Inc.

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 Kodeco Personal Plan.

Unlock now