Breadth-First Search (BFS) is an algorithm used for traversing or searching tree or graph data structures. It starts at the tree root and explores all nodes at the present depth level before moving on to nodes at the next depth level.

BFS Algorithm Steps

  1. Create a queue and enqueue the root node.
  2. While the queue is not empty:
    • Dequeue a node from the front of the queue.
    • Visit the dequeued node.
    • Enqueue all the unvisited adjacent nodes of the dequeued node.

BFS Example

Consider the following graph:

    A
   / \
  B   C
 / \   \
D   E   F

To perform BFS on this graph, we start with node A and visit all its adjacent nodes (B and C) before moving on to the next level (D, E, and F).

BFS Applications

  • Shortest path in an unweighted graph
  • Finding connected components in a graph
  • Level order traversal of a tree

BFS in Python

Here's an example of implementing BFS in Python:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([(start, [start])])

    while queue:
        node, path = queue.popleft()
        if node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                queue.append((neighbor, path + [neighbor]))
    return visited

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

print(bfs(graph, 'A'))

For more information on graph traversal algorithms, you can read our guide on Depth-First Search (DFS).

Related Topics

Breadth-First Search