38
BreadthFirst Search
Written by Vincent Ngo
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as
text.You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.
In the previous chapter, you explored how graphs can be used to capture relationships between objects. Remember that objects are just vertices, and the relationships between them are represented by edges.
Several algorithms exist to traverse or search through a graph’s vertices. One such algorithm is the breadthfirst search (BFS) algorithm.
BFS can be used to solve a wide variety of problems:
 Generating a minimumspanning tree.
 Finding potential paths between vertices.
 Finding the shortest path between two vertices.
Example
BFS starts off by selecting any vertex in a graph. The algorithm then explores all neighbors of this vertex before traversing the neighbors of said neighbors and so forth. As the name suggests, this algorithm takes a breadthfirst approach.
Going through a BFS example using the following undirected graph:
Note: Highlighted vertices represent vertices that have been visited.
You will use a queue to keep track of which vertices to visit next. The firstinfirstout approach of the queue guarantees that all of a vertex’s neighbors are visited before you traverse one level deeper.
 To begin, you pick a source vertex to start from. Here, you have chosen
A
, which is added to the queue.  As long as the queue is not empty, you dequeue and visit the next vertex, in this case
A
. Next, you add all ofA
’s neighboring vertices[B, D, C]
to the queue.
Note: It’s important to note that you only add a vertex to the queue when it has not yet been visited and is not already in the queue.
 The queue is not empty, so you dequeue and visit the next vertex, which is
B
. You then addB
’s neighborE
to the queue.A
is already visited so it does not get added. The queue now has[D, C, E]
.  The next vertex to be dequeued is
D
.D
does not have any neighbors that aren’t visited. The queue now has[C, E]
.
 Next, you dequeue
C
and add its neighbors[F, G]
to the queue. The queue now has[E, F, G]
.
Note that you have now visited all of A
’s neighbors! BFS now moves on to the second level of neighbors.
 You dequeue
E
and addH
to the queue. The queue now has[F, G, H]
. Note that you don’t addB
orF
to the queue becauseB
is already visited andF
is already in the queue.
 You dequeue
F
, and since all its neighbors are already in the queue or visited, you don’t add anything to the queue.  Just like the previous step, you dequeue
G
and don’t add anything to the queue.

Finally, you dequeue
H
. The breadthfirst search is complete since the queue is now empty! 
When exploring the vertices, you can construct a treelike structure, showing the vertices at each level: first the vertex you started from, then its neighbors, then its neighbors’ neighbors and so on.
Implementation
Open up the starter playground for this chapter. This playground contains an implementation of a graph that was built in the previous chapter. It also includes a stackbased queue implementation, which you will use to implement BFS.
extension Graph where Element: Hashable {
func breadthFirstSearch(from source: Vertex<Element>)
> [Vertex<Element>] {
var queue = QueueStack<Vertex<Element>>()
var enqueued: Set<Vertex<Element>> = []
var visited: [Vertex<Element>] = []
// more to come
return visited
}
}
queue.enqueue(source) // 1
enqueued.insert(source)
while let vertex = queue.dequeue() { // 2
visited.append(vertex) // 3
let neighborEdges = edges(from: vertex) // 4
neighborEdges.forEach { edge in
if !enqueued.contains(edge.destination) { // 5
queue.enqueue(edge.destination)
enqueued.insert(edge.destination)
}
}
}
let vertices = graph.breadthFirstSearch(from: a)
vertices.forEach { vertex in
print(vertex)
}
0: A
1: B
2: C
3: D
4: E
5: F
6: G
7: H
Performance
When traversing a graph using BFS, each vertex is enqueued once. This has a time complexity of O(V). During this traversal, you also visit all the the edges. The time it takes to visit all edges is O(E). This means that the overall time complexity for breadthfirst search is O(V + E).
Key points
 Breadthfirst search (BFS) is an algorithm for traversing or searching a graph.
 BFS explores all the current vertex’s neighbors before traversing the next level of vertices.
 It’s generally good to use this algorithm when your graph structure has a lot of neighboring vertices or when you need to find out every possible outcome.
 The queue data structure is used to prioritize traversing a vertex’s neighboring edges before diving down a level deeper.