Key takeaways:
Breadth-first search (BFS) is a graph traversal algorithm that explores all nodes at the current level before moving to the next.
BFS can be implemented using a queue to manage the exploration order.
It starts by inserting the starting node into the queue and marking it as visited.
The algorithm continues by dequeuing nodes, visiting their unvisited neighbors, and adding them to the queue.
The time complexity of BFS is
, where is the number of vertices and is the number of edges. The space complexity of BFS is
, where is the number of vertices.
Breadth-first search (BFS) is an algorithm used for traversing graphs or tree data structures. It explores all the vertices at the current level before moving to the next. BFS is commonly implemented using queues or linked lists to maintain the order of exploration.
The breadth-first search has a wide range of applications. For example, web crawlers can use BFS to build an index. It starts from a source page and follows links, ensuring comprehensive coverage. It can also help find people within a given distance from a person up to a specified level on social networking websites.
Let’s discuss the algorithm for the BFS:
Start: Insert the starting node into a queue. Mark the starting node as visited.
Explore: While the queue is not empty:
Remove a node from the queue and print its value
Insert all unvisited adjacent nodes of the removed node into the queue. Mark each adjacent node as visited to avoid revisiting.
End: Repeat the process until the queue is empty.
The following slides depict the flow of BFS in detail:
The following code example implements the BFS in Python:
graph = {'A' : ['B','C'],'B' : ['D', 'E'],'C' : ['F'],'D' : [],'E' : ['F'],'F' : []}visited = [] # List to keep track of visited nodesqueue = [] #Initialize a queuedef bfs(visited, graph, node):visited.append(node)queue.append(node)while queue:s = queue.pop(0)print (s, end = " ")for neighbour in graph[s]:if neighbour not in visited:visited.append(neighbour)queue.append(neighbour)# Driver Codebfs(visited, graph, 'A')
Lines 3–10: The illustrated graph is represented using an adjacency list. An easy way to do this in Python is to use a dictionary data structure, where each vertex has a stored list of its adjacent vertices or nodes.
Line 12: The visited is a list that is used to keep track of visited nodes.
Line 13: The queue is a list that is used to keep track of nodes currently in the queue.
Line 29: The arguments of the bfs function are the visited list, the graph in the form of a dictionary, and the starting node A.
Lines 15–26: The bfs follows the algorithm described above:
It checks and appends the starting node to the visited list and the queue.
Then, while the queue contains elements, it keeps taking nodes out of the queue, appends the neighbors of that node to the queue if they are unvisited, and marks them as visited.
This continues until the queue is empty.
Kickstart your coding journey with Learn Python 3 from Scratch—a comprehensive course designed to take you from a beginner to a confident Python programmer!
Since all of the nodes are visited, the time complexity for BFS on a graph is
The space complexity of BFS is
Haven’t found what you were looking for? Contact Us
Free Resources
