39. Breadth-First Search Challenges

Written by Vincent Ngo

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:

To help you solve this challenge, a property allVertices was added to the Graph protocol:

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

This property is already implemented by AdjacencyMatrix and AdjacencyList.

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

bfs takes in the source vertex to start traversing from:

1. queue keeps track of the neighboring vertices to visit next.
2. enqueued remembers which vertices have been added to the queue. You can use a Set for O(1) lookup. An array is O(n).
3. visited is an array that stores the order in which the vertices were explored.
4. Initiate the algorithm by inserting the source vertex.
5. Perform bfs recursively on the graph by calling a helper function.
6. Return the vertices visited in order.

The helper function looks like this:

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

1. Base case, recursively continue to dequeue a vertex from the queue till it is empty.
2. Mark the vertex as visited.
3. For every neighboring edge from the current vertex.
4. Check to see if the adjacent vertices have been visited before inserting into the queue.
5. Recursively perform bfs till the queue is empty.

Overall time complexity for breadth-first search is O(V + E).

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

1. If there are no vertices, treat the graph as connected.
2. Perform a breadth-first search starting from the first vertex. This will return all the visited nodes.
3. Go through every vertex in the graph and check to see if it has been visited before.

The graph is considered disconnected if a vertex is missing in the visited set.