Breadth-First Search

Breadth-First Search (BFS) is a graph traversal algorithm that explores all vertices at the same depth before moving to the next depth. It uses a Queue.

Concept

Graph:     A --- B
           |     |
           C --- D

BFS from A: A -> B -> C -> D (level by level)

Implementation

from collections import deque

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

    while queue:
        vertex = queue.popleft()
        order.append(vertex)

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

    return order

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

print(bfs(graph, 'A'))  # ['A', 'B', 'C', 'D']

BFS Level Order

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

    while queue:
        level_size = len(queue)
        current_level = []
        for _ in range(level_size):
            vertex = queue.popleft()
            current_level.append(vertex)
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        levels.append(current_level)

    return levels

print(bfs_levels(graph, 'A'))  # [['A'], ['B', 'C'], ['D']]

Shortest Path (Unweighted Graph)

BFS finds the shortest path from the start to every reachable vertex.

def bfs_shortest_path(graph, start):
    visited = {start}
    queue = deque([(start, [start])])
    paths = {start: [start]}

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

    return paths

print(bfs_shortest_path(graph, 'A'))
# {'A': ['A'], 'B': ['A', 'B'], 'C': ['A', 'C'], 'D': ['A', 'B', 'D']}

Time Complexity

V = number of vertices, E = number of edges

BFS Applications

1. Shortest path in an unweighted graph.
2. Level order traversal of a binary tree.
3. Search in mazes/puzzles.
4. Connected components in an undirected graph.
5. Social network: Computing degrees of separation.
6. Web crawling: Traversing web pages.

# Finding connected components
def count_components(graph):
    visited = set()
    count = 0
    for vertex in graph:
        if vertex not in visited:
            bfs(graph, vertex)  # visited is updated inside
            count += 1
    return count

BFS uses a Queue. DFS uses a Stack/Recursion. Let's study DFS.