Graphs

Graph BFS

TimeO(V + E) SpaceO(V)

Think of a rumor spreading. Day 1, you tell your direct friends. Day 2, they each tell their friends. Day 3, those friends tell theirs. The rumor reaches everyone in the fewest possible “hops.” BFS explores a graph exactly like this — layer by layer from the source.

When to use it: Shortest path in unweighted graphs, checking connectivity, finding all nodes within k edges, or any problem involving “minimum moves/steps.”

Key insight: BFS guarantees that the first time you reach a node, you’ve found the shortest path to it (in an unweighted graph). This is why BFS is the go-to for “minimum steps” problems.

Common trap: Forgetting the visited set. Without it, BFS revisits nodes and can loop forever in cyclic graphs, or at minimum waste massive time.

function graphBFS(graph, start):
    visited = {start}
    queue = [start]
    distance = {start: 0}

    while queue is not empty:
        node = queue.dequeue()

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                distance[neighbor] = distance[node] + 1
                queue.enqueue(neighbor)

    return distance

# Multi-source BFS (e.g., rotten oranges spreading)
function multiSourceBFS(grid, sources):
    visited = set(sources)
    queue = sources                 # start with ALL sources
    steps = 0

    while queue is not empty:
        nextQueue = []
        for node in queue:
            for neighbor in getNeighbors(node):
                if neighbor not in visited:
                    visited.add(neighbor)
                    nextQueue.append(neighbor)
        queue = nextQueue
        if queue is not empty:
            steps = steps + 1

    return steps

from collections import deque


def bfs_shortest_path(graph: dict[int, list[int]], start: int, end: int) -> int:
    """Shortest path in an unweighted graph. Returns -1 if unreachable."""
    if start == end:
        return 0

    visited = {start}
    queue = deque([(start, 0)])

    while queue:
        node, dist = queue.popleft()

        for neighbor in graph.get(node, []):
            if neighbor == end:
                return dist + 1
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))

    return -1


def num_islands(grid: list[list[str]]) -> int:
    """Count islands in a 2D grid using BFS."""
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                count += 1
                # BFS to mark entire island as visited
                queue = deque([(r, c)])
                grid[r][c] = "0"

                while queue:
                    row, col = queue.popleft()
                    for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                        nr, nc = row + dr, col + dc
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1":
                            grid[nr][nc] = "0"
                            queue.append((nr, nc))

    return count


def rotten_oranges(grid: list[list[int]]) -> int:
    """Multi-source BFS: minutes until all oranges rot. -1 if impossible."""
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1

    minutes = 0
    while queue and fresh:
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
        minutes += 1

    return minutes if fresh == 0 else -1

Problem: Given a grid where 0 is water and 1 is land, count the number of islands (groups of connected 1s, connected horizontally/vertically).

How would you approach this?

Answer: This is graph BFS (or DFS) on a grid. Each cell is a node, adjacent cells are edges. When you find an unvisited '1', start BFS to mark the entire connected component, then increment the island count.

Problem: In a grid, rotten oranges spread rot to adjacent fresh oranges every minute. What is the minimum number of minutes until all oranges are rotten?

How would you approach this?

Answer: This is multi-source BFS. Start BFS from all rotten oranges simultaneously (enqueue all of them at time 0). Each BFS layer represents one minute of spreading. The answer is the number of layers until no fresh oranges remain.

Time: O(V + E) where V is the number of vertices and E is the number of edges. Each vertex is enqueued and dequeued at most once, and each edge is examined at most once (twice for undirected graphs). For grids, V = rows * cols and E = 4V.

Space: O(V) for the visited set and the queue. In the worst case (e.g., a graph with all nodes at the same BFS level), the queue holds all V vertices.