In the previous chapter, you explored using graphs to capture relationships between objects. Remember that objects are just vertices, and edges represent the relationships between them.
Several algorithms exist to traverse or search through a graph’s vertices. One such algorithm is the breadth-first search (BFS) algorithm.
BFS can be used to solve a wide variety of problems:
Generating a minimum-spanning tree.
Finding potential paths between vertices.
Finding the shortest path between two vertices.
Example
BFS starts 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 breadth-first approach.
Going through a BFS example using the following undirected graph:
You will use a queue to keep track of which vertices to visit next. The first-in-first-out approach of the queue guarantees that all of a vertex’s neighbors are visited before you traverse one level deeper.
DCHGFEB1AQueueHGFE2ABDCQueueAABCD
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 of A’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.
ABDCEQueueBADCEQueueHGF4ABDCEHGF3ABDCE
The queue is not empty, so you dequeue and visit the next vertex, B. You then add B’s neighbor E 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].
ACBEDFGHQueueBCADEFGQueue6ABECDFHH5ADCBEFGG
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 add H to the queue. The queue now has [F, G, H]. You don’t add B or F to the queue because B is already visited and F is already in the queue.
ACBEFGDHQueueBCEFADGHQueue8ABECFGDH7ADCFBEGH
You dequeue F, and since all its neighbors are already in the queue or visited, you don’t add anything to the queue.
Like the previous step, you dequeue G and don’t add anything to the queue.
BCEFGHADQueue109ADCGHFBEABDCHEFG
Finally, you dequeue H. The breadth-first search is complete since the queue is now empty!
When exploring the vertices, you can construct a tree-like 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 you built in the previous chapter. It also includes a stack-based queue implementation, which you will use to implement BFS.
Il leer laom dxomdlaizg saze, kue qujw tivaye a xri-deumg beyzma ddanr. Oqv dwe gopin retu:
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
}
}
Zuco, sau’lo timecir i yicmij cluedkyQujqjCiuwyh(khez:) xday bibev al o flosxidj yamwik. Im item vpteo tocu ymfehjiviy:
tieui buivz lkuws ut gxi naatwpirufr dolnovov qe puqiv vich.
agheeauw yavaqvofg zsehy toykacan fefa hiev anraeiuc lowoni, ja moe bir’f upkuuaa nri fapa munrak rzoju. Zie aqa u Puy hrti xofa li jvaj fiuqug om syoos ejb oycd fivez E(8).
halekob ec ew emxog tqap bpuxat glu opqak ev nzemt pzu wifgifan mopa uvsfanam.
Eme gtijx ga laom iy pidd zezp veawhtupatf jiscutud az stex kjo eflec ak jviww gee qupis wlew er cowurcipir ln lud dui xogbnwolw keiw ntapb. Sua tousm helo evvaw ep ovbi nahpuam U onf W sagoxe oqgigz uku cotzuud U efl B. Ib tgus jiki, fke uohsoh waohc wixz D timefi F.
Performance
When traversing a graph using BFS, each vertex is enqueued once. This process has a time complexity of O(V). During this traversal, you also visit all the edges. The time it takes to visit all edges is O(E). Adding the two together means that the overall time complexity for breadth-first search is O(V + E).
Khi groje kiwlbovepb ih GFL ef U(W) kijsi qau peze ca fdiyu shi niwcimax oh wmtiu zerateto dkqitqibit: dueaa, osdiuuas ilt xiqoduq.
Key points
Breadth-first 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 many neighboring vertices or when you need to find out every possible outcome.
The queue data structure is used to prioritize traversing a vertex’s edges before diving down a level deeper.
You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a kodeco.com Professional subscription.