Searching is one of the fundamental problems in computer science. It involves finding a specific value or object in a given data structure. One of the most common searching algorithms is the Breadth-First Search (BFS).
In this article, we will discuss the details of Breadth-First Search in Python, including its definition, algorithm, and implementation.
What is Breadth-First Search?
Breadth-First Search is a method for traversing a graph or tree data structure. It starts at the root node and explores all the nodes at the current depth before moving on to the nodes at the next depth level. In other words, BFS explores the graph or tree in a breadth-wise manner.
The BFS algorithm uses a queue data structure to keep track of the nodes that need to be explored. It starts by adding the root or starting node into the queue. Then, it dequeues the first node from the queue and visits it. After that, it enqueues all the unvisited neighbors of the current node. This process continues until all nodes have been visited.
Algorithm and Implementation
The BFS algorithm can be implemented as follows:
Step 1: Create a Graph
A graph is a collection of nodes and edges. In Python, we can represent a graph using a dictionary data structure. Each key in the dictionary represents a node, and its value is a list of nodes that it is connected to, or its neighbors. Here is an example of a graph:
graph = {'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []}Step 2: Create a Queue and Enqueue the Starting Node
We can represent the queue using a list data structure. We start by enqueuing the starting node into the queue. Here is an example code:
queue = []
visited = set()
def bfs(graph, start_node):
queue.append(start_node)
visited.add(start_node)Step 3: Dequeue a Node and Visit it
We dequeue a node from the queue and visit it. Here is an example code:
while queue:
current_node = queue.pop(0)
print(current_node)We also mark the current node as visited to avoid visiting it again in the future.
Step 4: Enqueue Unvisited Neighbors
We loop through all the neighbors of the current node and enqueue them if they have not already been visited. Here is an example code:
for neighbor in graph[current_node]:
if neighbor not in visited:
queue.append(neighbor)
visited.add(neighbor)Step 5: Repeat Until Queue is Empty
The above steps are repeated until the queue becomes empty. Here is the complete BFS implementation:
graph = {'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []}
queue = []
visited = set()
def bfs(graph, start_node):
queue.append(start_node)
visited.add(start_node)
while queue:
current_node = queue.pop(0)
print(current_node)
for neighbor in graph[current_node]:
if neighbor not in visited:
queue.append(neighbor)
visited.add(neighbor)
bfs(graph, 'A')The output of the above code will be: A, B, C, D, E, F.
FAQs
– What is the time complexity of BFS algorithm?
The time complexity of BFS is O(V+E), where V is the number of vertices and E is the number of edges in the graph.
– What is the advantage of using BFS?
BFS is guaranteed to find the shortest path between the starting node and any reachable node in an unweighted graph.
– Does BFS work on weighted graphs?
Yes, BFS works on weighted graphs, but it might not find the shortest path in that case
– Can BFS be used for directed graphs?
Yes, BFS can be used for directed graphs. In that case, we need to use the directed graph’s adjacency list instead of the undirected graph’s adjacency list.
– Can BFS be used for trees?
Yes, BFS can be used to traverse trees. In that case, the starting node would be the root of the tree
