Napman's Notes

BFS

2 min read

BFS (Breadth-First Search)

Use when: Shortest path in unweighted graph, level-order traversal, “minimum steps” problems.

Complexity: O(V + E)

Standard BFS

from collections import deque
 
def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
 
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

BFS - Shortest Path (unweighted)

from collections import deque
 
def bfs_shortest(graph, start, target):
    visited = set([start])
    queue = deque([(start, 0)])  # (node, distance)
 
    while queue:
        node, dist = queue.popleft()
        if node == target:
            return dist
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
 
    return -1  # unreachable

BFS - Level Order (trees)

from collections import deque
 
def level_order(root):
    if not root:
        return []
    queue = deque([root])
    result = []
 
    while queue:
        level = []
        for _ in range(len(queue)):  # process one level at a time
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
 
    return result

BFS - Grid

from collections import deque
 
def bfs_grid(grid, start):
    rows, cols = len(grid), len(grid[0])
    visited = set([start])
    queue = deque([start])
    dirs = [(0,1),(0,-1),(1,0),(-1,0)]
 
    while queue:
        r, c = queue.popleft()
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited:
                visited.add((nr, nc))
                queue.append((nr, nc))

Signals in a Problem

  • “Minimum number of steps/moves”
  • “Shortest path” in unweighted graph or grid
  • Level-by-level processing

Graph View