Breadth-First Search (BFS) Algorithm Explained with Examples and Applications

 What is Breadth-First Search (BFS)?

Breadth-First Search (BFS) is a fundamental graph traversal algorithm that explores all nodes at the present depth level before moving on to nodes at the next depth level. It is widely used for solving shortest path problems in unweighted graphs, searching in trees, and analyzing connected components in graphs.

BFS Algorithm Explanation

BFS uses a queue data structure to keep track of the nodes to be explored next. The key idea is:

• Visit the starting node and enqueue it.
• While the queue is not empty:
  • Dequeue a node from the front.
  • Process the node (e.g., print or record).
  • Enqueue all its adjacent unvisited neighbors.

Algorithm Steps (for Binary Tree)

1. Start with the root node and put it into the queue.
2. While the queue is not empty:
   • Remove the node from the queue.
   • Process the current node.
   • If the left child exists, enqueue it.
   • If the right child exists, enqueue it.

Algorithm Steps (for General Graph)

1. Start with the given node and enqueue it.
2. Use a visited set to keep track of visited nodes.
3. While the queue is not empty:
   • Remove a node from the queue.
   • Process the node.
   • For each adjacent node:
     • If it has not been visited, mark it as visited and enqueue it.

Python Example Code

1. BFS for Binary Tree

from collections import deque

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

def bfs_binary_tree(root):
    if not root:
        return

    queue = deque([root])

    while queue:
        node = queue.popleft()
        print(node.val)

        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

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

bfs_binary_tree(root)

Output:

1
2
3
4
5

2. BFS for General Graph

from collections import deque

def bfs_graph(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        print(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# Example Usage
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

bfs_graph(graph, 'A')

Output:

A
B
C
D
E
F

Time and Space Complexity Analysis

Binary Tree

• Time Complexity: $O(n)$ where $n$ is the number of nodes. Each node is visited exactly once.
• Space Complexity: $O(w)$ where $w$ is the maximum width of the tree (the most nodes at any level).

General Graph

• Time Complexity: $O(V + E)$ where $V$ is the number of vertices and $E$ is the number of edges.
• Space Complexity: $O(V)$ for storing the visited set and queue.

Conclusion

BFS is one of the most intuitive and effective ways to traverse graphs and trees. It ensures the shortest path (in terms of the number of edges) is found in unweighted graphs. Understanding BFS deeply is crucial for building robust algorithms in complex systems.

References

• Wikipedia - Breadth-First Search
• GeeksforGeeks - BFS for a Graph