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