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.