Keyur Ramoliya

Posted on

Python - Implement Breadth-First Search (BFS) for Graph and Tree Traversal

Breadth-First Search (BFS) is a versatile algorithm for traversing graphs and trees in a level-by-level fashion. It starts at the root (or any chosen node) and explores all neighbor nodes before moving to their children. BFS is useful for tasks like shortest path finding, connected component analysis, and more. Here's an example:

Example - BFS for Traversing a Binary Tree in Python:

``````class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None

def bfs_tree(root):
if not root:
return

queue = [root]  # Initialize a queue with the root node

while queue:
current = queue.pop(0)  # Dequeue the current node
print(current.val)  # Process the current node

if current.left:
queue.append(current.left)  # Enqueue the left child
if current.right:
queue.append(current.right)  # Enqueue the right child

# Example usage:
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

bfs_tree(root)  # Traverses and prints the tree nodes in BFS order
``````

In this example, we implement BFS to traverse a binary tree level by level. We use a queue data structure to keep track of nodes to visit, ensuring that nodes at each level are processed before moving to the next level.

BFS is a powerful algorithm for exploring graphs and trees, and it guarantees the shortest path in unweighted graphs. You can adapt it to traverse various types of graphs and solve a wide range of problems efficiently.