39.
Breadth-First Search Challenges
Written by Vincent Ngo
Heads up... You’re accessing parts of this content for free, with some sections shown as text.
Heads up... You’re accessing parts of this content for free, with some sections shown as text.
Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.
Unlock now
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
}
}