# 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:

``````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.