How to implement a breadth-first search in Python
Breadth-first search (BFS) is an algorithm used for graph traversal on graphs or tree data structures. BFS explores all the vertices at the current level before moving to the next level. It can be easily implemented using data structures such as queues or linked lists to maintain the exploration order.
The breadth-first search has a wide range of applications, e.g., 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.
Algorithm
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:
Code example
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 nodes.queue = [] #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')
Explanation
-
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
visitedis a list that is used to keep track of visited nodes. -
Line 13: The
queueis a list that is used to keep track of nodes currently in the queue. -
Line 29: The arguments of the
bfsfunction are thevisitedlist, thegraphin the form of a dictionary, and the starting nodeA. -
Lines 15–26: The
bfsfollows the algorithm described above:- It checks and appends the starting node to the
visitedlist and thequeue. - Then, while the queue contains elements, it keeps taking out nodes from 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.
- It checks and appends the starting node to the
Time complexity
Since all of the nodes are visited, the time complexity for BFS on a graph is ; where is the number of vertices or nodes and is the number of edges.
Space complexity
The space complexity of BFS is , where represents the number of vertices or nodes in the graph.
