About the Algorythm Recipe 🍰
The Breadth First Search (BFS) Algorithm is akin to a careful custodian with a bunch of keys. Picture yourself in a structure with numerous rooms, each room having doors leading to other rooms. Rather than haphazardly opening doors, the BFS algorithm, much like a systematic custodian, makes sure you thoroughly unlock and inspect one room before advancing to the next.
Beginning from a selected room (or 'root'), it unlocks all the adjacent rooms at the current level prior to moving to rooms at the subsequent level. It employs a keyring (queue) to keep a record of rooms to be explored next.
The BFS algorithm is especially handy for traversing structures (or graphs) and is skilled at finding the shortest path in an unweighted structure (graph). Just like a custodian, it ensures no door (or node) remains locked! 🔑
Cookin' time! 🍳
from collections import deque
def bfs(graph, start):
"""
Perform Breadth First Search (BFS) traversal on a graph.
Args:
- graph: Adjacency list representation of the graph.
- start: Starting node for the BFS traversal.
Returns:
- List containing the order of visited nodes.
"""
visited = set()
queue = deque([start])
visited.add(start)
traversal_order = []
while queue:
current_node = queue.popleft()
traversal_order.append(current_node)
for neighbor in graph[current_node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return traversal_order
# Example usage:
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
start_node = 'A'
bfs_order = bfs(graph, start_node)
print("BFS Traversal Order:", bfs_order)
In this implementation, the graph is represented using an adjacency list where each node maps to a list of its neighboring nodes. The bfs function takes the graph and a starting node as input, then performs BFS traversal, storing the order of visited nodes in a list (traversal_order). It utilizes a queue data structure to keep track of nodes to visit next. Finally, it returns the traversal order.