LeetCode Patterns ·

🎯 BFS Basics

1️⃣ Core Framework

When discussing BFS Basics, I frame it as:

What problem pattern BFS solves
Queue and level-order traversal
BFS on trees
BFS on graphs
Visited set
Shortest path in unweighted graphs
Multi-source BFS
Grid BFS
Common edge cases
Senior-level explanation

2️⃣ What Problem Are We Solving?

BFS, or Breadth-First Search, is used when we need to explore a structure level by level.

It is commonly used for:

Level-order traversal
Shortest path in unweighted graphs
Minimum number of steps
Grid traversal
Connected components
Multi-source expansion
Word ladder style problems
Rotting oranges
Walls and gates
Nearest distance problems

The core idea is:

Explore all nodes at distance 1,
then all nodes at distance 2,
then all nodes at distance 3,
and so on.

👉 Interview Answer

BFS is a graph traversal algorithm that explores nodes level by level.

It uses a queue to process nodes in first-in, first-out order.

BFS is especially useful when we need the shortest path in an unweighted graph, because the first time we reach a node is through the minimum number of edges.

3️⃣ Why BFS Works

BFS Uses a Queue

Queue behavior:

First In, First Out

Example:

push A
push B
push C

pop → A
pop → B
pop → C

This ensures older nodes are processed before newer nodes.

Level-by-Level Expansion

Suppose we start at node S.

Level 0: S
Level 1: neighbors of S
Level 2: neighbors of Level 1
Level 3: neighbors of Level 2

Because BFS processes earlier levels first, it naturally finds minimum distance in unweighted graphs.

Key Requirement

BFS is most useful when each edge has equal cost.

unweighted graph
or
same cost per move

If edges have different weights, BFS may not give the shortest path.

👉 Interview Answer

BFS works because it explores all nodes at the current distance before moving to the next distance.

In an unweighted graph, every edge has the same cost.

Therefore, the first time BFS reaches a node, it has found the shortest path to that node.

4️⃣ BFS vs DFS

BFS

Uses:

queue

Order:

level by level

Best for:

shortest path in unweighted graph
minimum number of steps
level-order traversal
nearest target

DFS

Uses:

stack or recursion

Order:

go deep first

Best for:

backtracking
connected components
cycle detection
topological exploration
path existence

Comparison

Pattern	Data Structure	Traversal Order	Best For
BFS	Queue	Level by level	Shortest path, minimum steps
DFS	Stack / Recursion	Depth first	Backtracking, exhaustive search

👉 Interview Answer

BFS explores level by level using a queue.

DFS explores deeply first using recursion or a stack.

If the problem asks for minimum steps or shortest path in an unweighted graph, BFS is usually the better choice.

If the problem asks to explore all possibilities or backtrack, DFS is usually more natural.

5️⃣ Basic BFS Template

Graph BFS Template

from collections import deque

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

    while queue:
        node = queue.popleft()

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

Key Components

Every BFS usually needs:

Queue
Visited set
Start node
Neighbor generation
Processing logic

👉 Interview Answer

A standard BFS uses a queue and a visited set.

The queue stores nodes waiting to be processed.

The visited set prevents revisiting the same node and avoids infinite loops.

For each node, we inspect its neighbors and enqueue the unvisited ones.

6️⃣ Level-Order BFS Template

Why Level Tracking Matters

Sometimes we need to know:

which level we are on
how many steps we have taken
minimum distance

Template

from collections import deque

def bfs_level_order(start, graph):
    queue = deque([start])
    visited = set([start])
    level = 0

    while queue:
        size = len(queue)

        for _ in range(size):
            node = queue.popleft()

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

        level += 1

Key Idea

At the start of each while loop:

queue contains all nodes from the current level

Processing size nodes ensures one level is completed before moving to the next.

👉 Interview Answer

If I need level information, I process BFS level by level.

At the beginning of each round, I record the current queue size.

That size represents the number of nodes in the current level.

After processing those nodes, I increment the level or distance.

7️⃣ BFS on Binary Tree

Problem

Return level-order traversal of a binary tree.

    3
   / \
  9  20
     / \
    15  7

answer = [[3], [9, 20], [15, 7]]

Code

from collections import deque

def level_order(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        size = len(queue)
        level = []

        for _ in range(size):
            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

Why It Works

The queue always processes nodes in level order.

root
then root's children
then grandchildren

👉 Interview Answer

For binary tree level-order traversal, I use BFS with a queue.

I process the queue level by level.

For each node, I add its children to the queue.

Each round of the outer loop corresponds to one tree level.

8️⃣ Minimum Depth of Binary Tree

Problem

Find the minimum depth from root to a leaf node.

Why BFS Is Good

The first leaf node found by BFS is the closest leaf.

Because BFS explores:

depth 1
then depth 2
then depth 3

Code

from collections import deque

def min_depth(root):
    if not root:
        return 0

    queue = deque([(root, 1)])

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

        if not node.left and not node.right:
            return depth

        if node.left:
            queue.append((node.left, depth + 1))

        if node.right:
            queue.append((node.right, depth + 1))

    return 0

👉 Interview Answer

Minimum depth is a good BFS problem.

Since BFS explores the tree level by level, the first leaf node we encounter is the shallowest leaf.

So we can return immediately when we find the first leaf.

9️⃣ BFS on Graph

Problem

Traverse all reachable nodes from a start node.

Graph Representation

Adjacency list:

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

Code

from collections import deque

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

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

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

    return order

Why Visited Is Required

Graphs can contain cycles.

Example:

A ↔ B

Without visited:

A visits B
B visits A
A visits B again
...

This causes infinite traversal.

👉 Interview Answer

For graph BFS, I use a queue and a visited set.

The visited set is necessary because graphs may contain cycles.

I mark a node visited when I enqueue it, not when I dequeue it, to avoid adding the same node multiple times.

🔟 When to Mark Visited

Why?

This prevents the same node from being added multiple times by different parents.

Example:

A → C
B → C

If C is not marked until dequeue time, both A and B may enqueue C.

Pattern

if neighbor not in visited:
    visited.add(neighbor)
    queue.append(neighbor)

👉 Interview Answer

In BFS, I usually mark a node as visited when I enqueue it.

This prevents duplicate entries in the queue.

If I wait until dequeue time, the same node may be enqueued multiple times through different paths.

1️⃣1️⃣ Shortest Path in Unweighted Graph

Problem

Find the shortest number of edges from start to target.

Code

from collections import deque

def shortest_path(graph, start, target):
    queue = deque([(start, 0)])
    visited = set([start])

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

        if node == target:
            return distance

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

    return -1

Why First Target Is Shortest

Because BFS processes nodes in increasing distance order:

distance 0
distance 1
distance 2
distance 3

The first time target is reached, no shorter path can exist.

👉 Interview Answer

BFS finds the shortest path in an unweighted graph.

I store the distance along with each node in the queue.

Because BFS explores nodes in increasing distance order, the first time I reach the target is the shortest path.

1️⃣2️⃣ Grid BFS

Problem Pattern

Many LeetCode BFS problems are on a 2D grid.

Common examples:

Number of islands
Shortest path in binary matrix
Rotting oranges
Walls and gates
Nearest exit from entrance
Pacific Atlantic water flow variants

Direction Array

directions = [
    (1, 0),
    (-1, 0),
    (0, 1),
    (0, -1)
]

For 8-direction movement:

directions = [
    (1, 0), (-1, 0),
    (0, 1), (0, -1),
    (1, 1), (1, -1),
    (-1, 1), (-1, -1)
]

Boundary Check

0 <= new_row < rows
0 <= new_col < cols

👉 Interview Answer

For grid BFS, I treat each cell as a graph node.

Neighbor generation comes from moving up, down, left, and right, or sometimes all eight directions.

I always check boundaries, obstacles, and visited state before adding a neighbor to the queue.

1️⃣3️⃣ Grid BFS Template

from collections import deque

def grid_bfs(grid, start_row, start_col):
    rows = len(grid)
    cols = len(grid[0])

    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    queue = deque([(start_row, start_col)])
    visited = set([(start_row, start_col)])

    while queue:
        row, col = queue.popleft()

        for dr, dc in directions:
            nr = row + dr
            nc = col + dc

            if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                continue

            if (nr, nc) in visited:
                continue

            if grid[nr][nc] == "#":
                continue

            visited.add((nr, nc))
            queue.append((nr, nc))

Key Components

For grid BFS, define:

rows and cols
directions
queue
visited
boundary check
obstacle check
neighbor expansion

👉 Interview Answer

In grid BFS, I model each cell as a node.

From each cell, I generate neighboring cells using direction arrays.

Before enqueueing a neighbor, I check whether it is inside bounds, not blocked, and not visited.

1️⃣4️⃣ Number of Islands

Problem

Given a grid of "1" and "0", count the number of islands.

An island is a group of connected "1" cells.

Code

from collections import deque

def num_islands(grid):
    if not grid or not grid[0]:
        return 0

    rows = len(grid)
    cols = len(grid[0])
    islands = 0

    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    def bfs(start_row, start_col):
        queue = deque([(start_row, start_col)])
        grid[start_row][start_col] = "0"

        while queue:
            row, col = queue.popleft()

            for dr, dc in directions:
                nr = row + dr
                nc = col + dc

                if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                    continue

                if grid[nr][nc] != "1":
                    continue

                grid[nr][nc] = "0"
                queue.append((nr, nc))

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                islands += 1
                bfs(r, c)

    return islands

Key Insight

Each BFS consumes one full island.

When we find an unvisited land cell,
we start BFS and mark the entire connected island.

👉 Interview Answer

Number of Islands can be solved by BFS or DFS.

I scan the grid.

When I find a land cell, I count one island and run BFS to visit all connected land cells.

During BFS, I mark visited land as water to avoid revisiting it.

1️⃣5️⃣ Rotting Oranges

Problem

Each minute, rotten oranges make adjacent fresh oranges rotten.

Return the minimum minutes needed for all oranges to become rotten.

Why Multi-Source BFS?

All initially rotten oranges start spreading at the same time.

So the BFS starts from multiple sources.

initial rotten oranges = all starting points

Code

from collections import deque

def oranges_rotting(grid):
    rows = len(grid)
    cols = 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, 0))
            elif grid[r][c] == 1:
                fresh += 1

    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    minutes = 0

    while queue:
        row, col, time = queue.popleft()
        minutes = max(minutes, time)

        for dr, dc in directions:
            nr = row + dr
            nc = col + dc

            if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                continue

            if grid[nr][nc] != 1:
                continue

            grid[nr][nc] = 2
            fresh -= 1
            queue.append((nr, nc, time + 1))

    return minutes if fresh == 0 else -1

👉 Interview Answer

Rotting Oranges is a multi-source BFS problem.

All initially rotten oranges are added to the queue first.

BFS expands from all of them simultaneously.

Each BFS level represents one minute.

At the end, if any fresh orange remains, return -1.

1️⃣6️⃣ Multi-Source BFS

What Is Multi-Source BFS?

Instead of starting BFS from one node, we start from many nodes at the same time.

Initial queue contains all sources:

queue = deque(all_sources)

When to Use

Use multi-source BFS when the problem asks for:

nearest distance to any source
spread from multiple starting points
minimum time for all cells to change
simultaneous expansion

Examples

Rotting Oranges
Walls and Gates
Map of Highest Peak
01 Matrix
Nearest exit from many sources
Fire spread problems

👉 Interview Answer

Multi-source BFS starts from multiple nodes at once.

It is useful when many sources expand simultaneously, or when we need the distance to the nearest source.

By enqueueing all sources initially, BFS guarantees that each cell is reached from the nearest source first.

1️⃣7️⃣ 01 Matrix

Problem

Given a matrix of 0s and 1s, return the distance of each cell to the nearest 0.

Key Idea

Start BFS from all 0 cells.

Why?

Because each 1 wants to know:

distance to nearest 0

So all 0s are sources.

Code

from collections import deque

def update_matrix(mat):
    rows = len(mat)
    cols = len(mat[0])

    queue = deque()
    dist = [[-1] * cols for _ in range(rows)]

    for r in range(rows):
        for c in range(cols):
            if mat[r][c] == 0:
                dist[r][c] = 0
                queue.append((r, c))

    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    while queue:
        row, col = queue.popleft()

        for dr, dc in directions:
            nr = row + dr
            nc = col + dc

            if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                continue

            if dist[nr][nc] != -1:
                continue

            dist[nr][nc] = dist[row][col] + 1
            queue.append((nr, nc))

    return dist

👉 Interview Answer

01 Matrix is a multi-source BFS problem.

Instead of starting from every 1 and searching for the nearest 0, I start from all 0 cells at once.

BFS expands outward, so the first time a 1 cell is reached, that distance is the shortest distance to a 0.

1️⃣8️⃣ Word Ladder

Problem

Transform one word into another by changing one letter at a time.

Each intermediate word must exist in the word list.

Find the shortest transformation length.

Why BFS?

Each transformation has equal cost:

one word change = one step

So shortest transformation length is shortest path in an unweighted graph.

Basic Code

from collections import deque

def ladder_length(begin_word, end_word, word_list):
    word_set = set(word_list)

    if end_word not in word_set:
        return 0

    queue = deque([(begin_word, 1)])
    visited = set([begin_word])

    while queue:
        word, steps = queue.popleft()

        if word == end_word:
            return steps

        for i in range(len(word)):
            for ch in "abcdefghijklmnopqrstuvwxyz":
                next_word = word[:i] + ch + word[i + 1:]

                if next_word in word_set and next_word not in visited:
                    visited.add(next_word)
                    queue.append((next_word, steps + 1))

    return 0

Optimization Note

For large inputs, we can precompute wildcard patterns:

hot → *ot, h*t, ho*

Then map each pattern to matching words.

👉 Interview Answer

Word Ladder can be modeled as shortest path in an unweighted graph.

Each word is a node.

An edge exists between two words if they differ by one character.

Since each transformation has equal cost, BFS finds the shortest transformation length.

1️⃣9️⃣ BFS With State

When Node Is Not Enough

Sometimes BFS state is more than just position.

Examples:

(row, col, remaining_obstacle_eliminations)
(node, keys_collected)
(position, used_special_move)
(word, steps)

Example State

(row, col, remaining_k)

In shortest path with obstacle elimination, reaching the same cell with more remaining eliminations is better than reaching it with fewer.

Visited Must Include Full State

Wrong:

visited.add((row, col))

Correct:

visited.add((row, col, remaining_k))

👉 Interview Answer

In BFS, the visited key must represent the full state.

Sometimes position alone is not enough.

If two paths reach the same cell with different remaining resources, they are not equivalent states.

So the visited set should include all variables that affect future decisions.

2️⃣0️⃣ BFS Complexity Analysis

Graph BFS

For graph with V vertices and E edges:

Time: O(V + E)
Space: O(V)

Because:

each vertex is enqueued once
each edge is checked once or twice

Grid BFS

For an m x n grid:

Time: O(mn)
Space: O(mn)

Because each cell is processed at most once.

Word Ladder Basic Version

Let:

N = number of words
L = word length

Basic neighbor generation can be:

O(N * L * 26)

depending on implementation.

👉 Interview Answer

BFS on a graph is O(V + E), because each node is visited once and each edge is examined once or twice.

BFS on a grid is O(mn), because each cell is processed at most once.

Space complexity is usually proportional to the queue and visited set.

2️⃣1️⃣ Common Edge Cases

Empty Input

root = None
grid = []
graph = {}

Start Equals Target

start == target

Usually distance is:

or answer is immediately found.

No Path Exists

Return:

-1
0
[]

depending on the problem.

Obstacles

Grid cells may be blocked:

"#"
0
-1

Always check before enqueueing.

Multiple Sources

All sources must be enqueued before BFS starts.

Revisit Problems

If visited is missing or incomplete, BFS may loop forever or create duplicate work.

👉 Interview Answer

Common BFS edge cases include empty input, start already equals target, no valid path, blocked cells, multiple starting sources, and incorrect visited-state handling.

I usually handle these before or during queue initialization.

2️⃣2️⃣ Common Mistakes

Mistake 1: Forgetting Visited

Without visited, graph BFS can loop forever.

Mistake 2: Marking Visited Too Late

Marking visited only when popping may enqueue duplicates.

Preferred:

visited.add(neighbor)
queue.append(neighbor)

Mistake 3: Mixing BFS and DFS Logic

Using stack accidentally turns BFS into DFS.

BFS requires:

queue.popleft()

Mistake 4: Wrong Level Counting

Incrementing distance after every node instead of after every level.

Mistake 5: Not Including Full State in Visited

For stateful BFS, visited must include all relevant state variables.

Mistake 6: Using BFS for Weighted Shortest Path

If edge weights differ, use:

Dijkstra

not plain BFS.

👉 Interview Answer

Common BFS mistakes include forgetting visited, marking visited too late, using a stack instead of a queue, counting levels incorrectly, missing part of the state in visited, and using BFS for weighted shortest path problems.

Plain BFS only guarantees shortest path when all edges have equal cost.

2️⃣3️⃣ When BFS Applies

Good Fit

Use BFS when the problem asks for:

minimum steps
shortest path in unweighted graph
level-order traversal
nearest target
spread over time
distance from source
simultaneous expansion

Problem Signals

Look for words like:

minimum number of moves
shortest path
nearest
level order
each minute
spread
fewest steps
unweighted graph
grid shortest path

👉 Interview Answer

I consider BFS when the problem asks for shortest path, minimum steps, nearest target, level-order traversal, or simultaneous spread.

The key condition is that each move or edge has the same cost.

2️⃣4️⃣ When BFS Does Not Apply

Not Good Fit

Plain BFS is not ideal when:

edges have different weights
need all combinations
need recursive backtracking
need topological order with dependencies
need optimal substructure over choices

Better Alternatives

Problem Type	Better Pattern
Weighted shortest path	Dijkstra
Negative weights	Bellman-Ford
All combinations	Backtracking
Deep path exploration	DFS
Dependency ordering	Topological Sort
Optimization with overlapping subproblems	Dynamic Programming

👉 Interview Answer

BFS is not always the right choice.

If edge weights differ, plain BFS no longer guarantees shortest path.

For weighted shortest path, Dijkstra is more appropriate.

For exhaustive combinations, backtracking or DFS is usually better.

2️⃣5️⃣ Standard Templates

Basic Graph BFS Template

from collections import deque

def bfs(graph, start):
    queue = deque([start])
    visited = set([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 Template

from collections import deque

def shortest_path(graph, start, target):
    queue = deque([(start, 0)])
    visited = set([start])

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

        if node == target:
            return distance

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

    return -1

Level-Order Template

from collections import deque

def bfs_by_level(start, graph):
    queue = deque([start])
    visited = set([start])
    level = 0

    while queue:
        size = len(queue)

        for _ in range(size):
            node = queue.popleft()

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

        level += 1

Grid BFS Template

from collections import deque

def grid_bfs(grid, start_row, start_col):
    rows = len(grid)
    cols = len(grid[0])
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    queue = deque([(start_row, start_col)])
    visited = set([(start_row, start_col)])

    while queue:
        row, col = queue.popleft()

        for dr, dc in directions:
            nr = row + dr
            nc = col + dc

            if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                continue

            if (nr, nc) in visited:
                continue

            if grid[nr][nc] == "#":
                continue

            visited.add((nr, nc))
            queue.append((nr, nc))

Multi-Source BFS Template

from collections import deque

def multi_source_bfs(grid, sources):
    rows = len(grid)
    cols = len(grid[0])
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    queue = deque()
    dist = [[-1] * cols for _ in range(rows)]

    for r, c in sources:
        queue.append((r, c))
        dist[r][c] = 0

    while queue:
        row, col = queue.popleft()

        for dr, dc in directions:
            nr = row + dr
            nc = col + dc

            if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                continue

            if dist[nr][nc] != -1:
                continue

            dist[nr][nc] = dist[row][col] + 1
            queue.append((nr, nc))

    return dist

BFS With State Template

from collections import deque

def bfs_with_state(start_state):
    queue = deque([(start_state, 0)])
    visited = set([start_state])

    while queue:
        state, steps = queue.popleft()

        if is_target(state):
            return steps

        for next_state in get_neighbors(state):
            if next_state not in visited:
                visited.add(next_state)
                queue.append((next_state, steps + 1))

    return -1

🧠 Staff-Level Answer Final

👉 Interview Answer Full Version

BFS, or Breadth-First Search, is a traversal algorithm that explores nodes level by level.

It uses a queue, which follows first-in, first-out behavior.

This ensures that nodes discovered earlier are processed before nodes discovered later.

BFS is especially useful for shortest path problems in unweighted graphs, because it explores all nodes at distance d before exploring nodes at distance d + 1.

Therefore, the first time BFS reaches a target node, it has found the minimum number of edges or steps.

A standard BFS usually has a queue, a visited set, a start node, and a way to generate neighbors.

The visited set is important because graphs can contain cycles. I usually mark a node visited when I enqueue it, not when I dequeue it, to avoid adding the same node multiple times.

For tree problems, BFS is commonly used for level-order traversal. I process the queue by level using the current queue size.

For grid problems, I treat each cell as a graph node. Neighbor generation is usually based on four directions or eight directions. Before enqueueing a cell, I check boundaries, obstacles, and visited state.

Multi-source BFS is used when many sources expand at the same time. Examples include Rotting Oranges, 01 Matrix, and Walls and Gates. By putting all sources into the queue initially, BFS guarantees that each cell is reached from the nearest source first.

Some BFS problems require state beyond just the current node. For example, state may include position, remaining obstacle eliminations, collected keys, or whether a special move has been used. In those cases, the visited set must include the full state, not just the position.

The complexity of BFS on a graph is O(V + E), because each vertex is visited once and each edge is checked. For a grid, the complexity is O(mn), because each cell is processed at most once.

BFS is not appropriate for weighted shortest path problems unless all edge weights are equal. If weights differ, Dijkstra is usually the correct algorithm.

At a senior level, I would explain: what the nodes are, how neighbors are generated, what the queue represents, what the visited state contains, and why level-order traversal guarantees the shortest path.

⭐ Final Insight

BFS 的核心不是“用 queue 遍历”。

它的核心是 level-by-level expansion。

Senior-level 的重点是：

node 是什么， neighbor 怎么生成， visited state 包含什么， queue 里每一层代表什么，为什么第一次到达 target 就是 shortest path，以及为什么 plain BFS 只适用于 unweighted graph。

能讲清楚这些， BFS 就不是简单遍历，而是一种解决 shortest path、minimum steps 和 simultaneous expansion 的基础算法模型。

中文部分

🎯 BFS Basics

1️⃣ 核心框架

讨论 BFS Basics 时，我通常从：

BFS 解决什么问题
Queue 和 level-order traversal
Tree 上的 BFS
Graph 上的 BFS
Visited set
Unweighted graph 中的 shortest path
Multi-source BFS
Grid BFS
常见 edge cases
高级工程师解释方式

2️⃣ 要解决什么问题？

BFS，也就是 Breadth-First Search，用于按层探索结构。

它常用于：

Level-order traversal
Shortest path in unweighted graphs
Minimum number of steps
Grid traversal
Connected components
Multi-source expansion
Word ladder style problems
Rotting oranges
Walls and gates
Nearest distance problems

核心思想是：

先探索距离为 1 的节点，
再探索距离为 2 的节点，
再探索距离为 3 的节点。

👉 面试回答

BFS 是一种 graph traversal algorithm。

它按层探索节点，并使用 queue 以 first-in, first-out 的顺序处理节点。

BFS 特别适合 unweighted graph 中的 shortest path，因为第一次到达某个节点时，一定是通过最少边数到达的。

3️⃣ 为什么 BFS 有效？

BFS 使用 Queue

Queue 行为：

First In, First Out

Example:

push A
push B
push C

pop → A
pop → B
pop → C

这保证了先进入 queue 的节点先被处理。

Level-by-Level Expansion

假设从 node S 开始：

Level 0: S
Level 1: S 的 neighbors
Level 2: Level 1 的 neighbors
Level 3: Level 2 的 neighbors

因为 BFS 先处理较浅层，所以它天然能在 unweighted graph 中找到 minimum distance。

关键条件

BFS 最适合每条边成本相同的情况：

unweighted graph
or
same cost per move

如果 edge weights 不同，BFS 不一定能找到 shortest path。

👉 面试回答

BFS 有效，是因为它会先探索当前距离的所有节点，再进入下一层距离。

在 unweighted graph 中，每条边成本相同。

所以 BFS 第一次到达某个节点时，就已经找到了 shortest path。

4️⃣ BFS vs DFS

BFS

使用：

queue

顺序：

level by level

适合：

shortest path in unweighted graph
minimum number of steps
level-order traversal
nearest target

DFS

使用：

stack or recursion

顺序：

go deep first

适合：

backtracking
connected components
cycle detection
topological exploration
path existence

Comparison

Pattern	Data Structure	Traversal Order	Best For
BFS	Queue	Level by level	Shortest path, minimum steps
DFS	Stack / Recursion	Depth first	Backtracking, exhaustive search

👉 面试回答

BFS 使用 queue，按层探索。

DFS 使用 recursion 或 stack，先往深处探索。

如果题目问 minimum steps 或 unweighted graph 中的 shortest path， BFS 通常更合适。

如果题目问探索所有可能性或 backtracking， DFS 通常更自然。

5️⃣ Basic BFS Template

Graph BFS Template

from collections import deque

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

    while queue:
        node = queue.popleft()

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

Key Components

每个 BFS 通常需要：

Queue
Visited set
Start node
Neighbor generation
Processing logic

👉 面试回答

标准 BFS 使用 queue 和 visited set。

Queue 存等待处理的 nodes。

Visited set 用来避免重复访问同一个 node，也可以防止 graph cycle 造成 infinite loop。

对每个 node，我检查它的 neighbors，并把还没访问过的 neighbor 加入 queue。

6️⃣ Level-Order BFS Template

为什么 Level Tracking 重要？

有些题需要知道：

当前是第几层
已经走了多少步
minimum distance 是多少

Template

from collections import deque

def bfs_level_order(start, graph):
    queue = deque([start])
    visited = set([start])
    level = 0

    while queue:
        size = len(queue)

        for _ in range(size):
            node = queue.popleft()

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

        level += 1

Key Idea

每次 while loop 开始时：

queue 中正好是当前 level 的所有 nodes

处理 size 个 node，就能保证一层处理完再进入下一层。

👉 面试回答

如果需要 level 信息，我会按层处理 BFS。

每一轮开始时，先记录 queue 当前大小。

这个 size 就是当前 level 的节点数。

处理完这些节点后，再增加 level 或 distance。

7️⃣ Binary Tree BFS

Problem

返回 binary tree 的 level-order traversal。

    3
   / \
  9  20
     / \
    15  7

answer = [[3], [9, 20], [15, 7]]

Code

from collections import deque

def level_order(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        size = len(queue)
        level = []

        for _ in range(size):
            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

为什么有效？

Queue 会按层处理 nodes：

root
then root's children
then grandchildren

👉 面试回答

对 binary tree level-order traversal，我使用 BFS 和 queue。

我按 level 处理 queue。

对每个 node，把它的 children 加入 queue。

外层 while loop 每一轮对应 tree 的一层。

8️⃣ Minimum Depth of Binary Tree

Problem

找到 root 到 leaf node 的最短深度。

为什么 BFS 合适？

BFS 找到的第一个 leaf node 就是最近的 leaf。

因为 BFS 按顺序探索：

depth 1
depth 2
depth 3

Code

from collections import deque

def min_depth(root):
    if not root:
        return 0

    queue = deque([(root, 1)])

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

        if not node.left and not node.right:
            return depth

        if node.left:
            queue.append((node.left, depth + 1))

        if node.right:
            queue.append((node.right, depth + 1))

    return 0

👉 面试回答

Minimum depth 是很适合 BFS 的问题。

因为 BFS 按层探索 tree，第一次遇到 leaf node 时，这个 leaf 一定是最浅的。

所以可以直接返回当前 depth。

9️⃣ Graph BFS

Problem

从 start node 出发，遍历所有 reachable nodes。

Graph Representation

Adjacency list:

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

Code

from collections import deque

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

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

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

    return order

为什么需要 Visited？

Graph 可能有 cycle。

Example:

A ↔ B

如果没有 visited：

A visits B
B visits A
A visits B again
...

会无限循环。

👉 面试回答

对 graph BFS，我使用 queue 和 visited set。

Visited set 很重要，因为 graph 可能有 cycle。

我通常在 enqueue 的时候就 mark visited，而不是等 dequeue 时再 mark。

这样可以避免同一个 node 被加入 queue 多次。

🔟 什么时候 Mark Visited？

为什么？

这样可以防止同一个 node 被不同 parent 重复加入 queue。

Example:

A → C
B → C

如果 C 等 dequeue 时才 mark visited， A 和 B 可能都会把 C 加入 queue。

Pattern

if neighbor not in visited:
    visited.add(neighbor)
    queue.append(neighbor)

👉 面试回答

在 BFS 中，我通常在 enqueue 的时候就 mark visited。

这样可以避免 duplicate queue entries。

如果等到 dequeue 时再 mark，同一个 node 可能会通过不同路径被加入 queue 多次。

1️⃣1️⃣ Unweighted Graph Shortest Path

Problem

找从 start 到 target 的最短边数。

Code

from collections import deque

def shortest_path(graph, start, target):
    queue = deque([(start, 0)])
    visited = set([start])

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

        if node == target:
            return distance

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

    return -1

为什么第一次到达 Target 就是 Shortest？

因为 BFS 按 distance 增加顺序处理 nodes：

distance 0
distance 1
distance 2
distance 3

第一次到达 target 时，不可能存在更短路径。

👉 面试回答

BFS 可以找到 unweighted graph 中的 shortest path。

我在 queue 中同时存 node 和 distance。

因为 BFS 按距离从小到大探索，第一次到达 target 时，就是 shortest path。

1️⃣2️⃣ Grid BFS

Problem Pattern

很多 LeetCode BFS 问题发生在 2D grid 上。

常见例子：

Number of islands
Shortest path in binary matrix
Rotting oranges
Walls and gates
Nearest exit from entrance
Pacific Atlantic water flow variants

Direction Array

directions = [
    (1, 0),
    (-1, 0),
    (0, 1),
    (0, -1)
]

8 个方向：

directions = [
    (1, 0), (-1, 0),
    (0, 1), (0, -1),
    (1, 1), (1, -1),
    (-1, 1), (-1, -1)
]

Boundary Check

0 <= new_row < rows
0 <= new_col < cols

👉 面试回答

对 grid BFS，我把每个 cell 当成 graph node。

Neighbor generation 来自上下左右移动，有些题也可能是 8 个方向移动。

在 enqueue neighbor 之前，我一定会检查 boundary、obstacle 和 visited state。

1️⃣3️⃣ Grid BFS Template

from collections import deque

def grid_bfs(grid, start_row, start_col):
    rows = len(grid)
    cols = len(grid[0])

    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    queue = deque([(start_row, start_col)])
    visited = set([(start_row, start_col)])

    while queue:
        row, col = queue.popleft()

        for dr, dc in directions:
            nr = row + dr
            nc = col + dc

            if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                continue

            if (nr, nc) in visited:
                continue

            if grid[nr][nc] == "#":
                continue

            visited.add((nr, nc))
            queue.append((nr, nc))

Key Components

Grid BFS 要定义：

rows and cols
directions
queue
visited
boundary check
obstacle check
neighbor expansion

👉 面试回答

Grid BFS 中，我把每个 cell 建模成一个 node。

从当前 cell 出发，用 directions array 生成 neighbors。

对每个 neighbor，先检查是否越界，是否 blocked，是否已经 visited。

然后再加入 queue。

1️⃣4️⃣ Number of Islands

Problem

给定 "1" 和 "0" 组成的 grid，统计 island 数量。

Island 是相邻的 "1" 组成的 connected component。

Code

from collections import deque

def num_islands(grid):
    if not grid or not grid[0]:
        return 0

    rows = len(grid)
    cols = len(grid[0])
    islands = 0

    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    def bfs(start_row, start_col):
        queue = deque([(start_row, start_col)])
        grid[start_row][start_col] = "0"

        while queue:
            row, col = queue.popleft()

            for dr, dc in directions:
                nr = row + dr
                nc = col + dc

                if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                    continue

                if grid[nr][nc] != "1":
                    continue

                grid[nr][nc] = "0"
                queue.append((nr, nc))

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                islands += 1
                bfs(r, c)

    return islands

Key Insight

每次 BFS 会消耗掉一个完整 island。

发现一个未访问 land cell，
就从这里开始 BFS，
并 mark 整个 connected island。

👉 面试回答

Number of Islands 可以用 BFS 或 DFS。

我扫描整个 grid。

当发现一个 land cell，就把 island count 加一，然后用 BFS visit 所有 connected land cells。

BFS 过程中，我把访问过的 land 标记成 water，防止重复访问。

1️⃣5️⃣ Rotting Oranges

Problem

每一分钟，rotten orange 会让相邻 fresh orange 变 rotten。

返回所有 orange 变 rotten 所需的最短时间。

为什么是 Multi-Source BFS？

所有初始 rotten oranges 同时开始传播。

所以 BFS 起点有多个：

initial rotten oranges = all starting points

Code

from collections import deque

def oranges_rotting(grid):
    rows = len(grid)
    cols = 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, 0))
            elif grid[r][c] == 1:
                fresh += 1

    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    minutes = 0

    while queue:
        row, col, time = queue.popleft()
        minutes = max(minutes, time)

        for dr, dc in directions:
            nr = row + dr
            nc = col + dc

            if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                continue

            if grid[nr][nc] != 1:
                continue

            grid[nr][nc] = 2
            fresh -= 1
            queue.append((nr, nc, time + 1))

    return minutes if fresh == 0 else -1

👉 面试回答

Rotting Oranges 是 multi-source BFS。

我先把所有初始 rotten oranges 加入 queue。

BFS 从所有 rotten oranges 同时向外扩展。

每一层 BFS 代表一分钟。

最后如果还有 fresh orange，返回 -1。

1️⃣6️⃣ Multi-Source BFS

什么是 Multi-Source BFS？

普通 BFS 从一个 source 开始。

Multi-source BFS 从多个 source 同时开始。

初始 queue 包含所有 sources：

queue = deque(all_sources)

什么时候用？

当题目问：

nearest distance to any source
spread from multiple starting points
minimum time for all cells to change
simultaneous expansion

Examples

Rotting Oranges
Walls and Gates
Map of Highest Peak
01 Matrix
Nearest exit from many sources
Fire spread problems

👉 面试回答

Multi-source BFS 是从多个起点同时开始 BFS。

它适用于多个 source 同时扩散的问题，或者需要计算到最近 source 的距离。

通过一开始把所有 sources 放入 queue， BFS 可以保证每个 cell 第一次被访问时，就是离最近 source 的最短距离。

1️⃣7️⃣ 01 Matrix

Problem

给定 0 和 1 组成的 matrix，返回每个 cell 到最近 0 的距离。

Key Idea

从所有 0 cell 开始 BFS。

为什么？

因为每个 1 想知道：

distance to nearest 0

所以所有 0 都是 source。

Code

from collections import deque

def update_matrix(mat):
    rows = len(mat)
    cols = len(mat[0])

    queue = deque()
    dist = [[-1] * cols for _ in range(rows)]

    for r in range(rows):
        for c in range(cols):
            if mat[r][c] == 0:
                dist[r][c] = 0
                queue.append((r, c))

    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    while queue:
        row, col = queue.popleft()

        for dr, dc in directions:
            nr = row + dr
            nc = col + dc

            if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                continue

            if dist[nr][nc] != -1:
                continue

            dist[nr][nc] = dist[row][col] + 1
            queue.append((nr, nc))

    return dist

👉 面试回答

01 Matrix 是 multi-source BFS。

不要从每个 1 出发去找最近的 0。

更高效的方法是从所有 0 同时出发。

BFS 向外扩展，每个 1 第一次被访问时，就得到了到最近 0 的 shortest distance。

1️⃣8️⃣ Word Ladder

Problem

每次改变一个字母，把 begin word 转换成 end word。

每个 intermediate word 必须在 word list 中。

要求最短转换长度。

为什么 BFS？

每次转换成本相同：

one word change = one step

所以 shortest transformation length 就是 unweighted graph 中的 shortest path。

Basic Code

from collections import deque

def ladder_length(begin_word, end_word, word_list):
    word_set = set(word_list)

    if end_word not in word_set:
        return 0

    queue = deque([(begin_word, 1)])
    visited = set([begin_word])

    while queue:
        word, steps = queue.popleft()

        if word == end_word:
            return steps

        for i in range(len(word)):
            for ch in "abcdefghijklmnopqrstuvwxyz":
                next_word = word[:i] + ch + word[i + 1:]

                if next_word in word_set and next_word not in visited:
                    visited.add(next_word)
                    queue.append((next_word, steps + 1))

    return 0

Optimization Note

大输入下，可以预处理 wildcard patterns：

hot → *ot, h*t, ho*

然后把每个 pattern 映射到匹配 words。

👉 面试回答

Word Ladder 可以建模成 unweighted graph 中的 shortest path。

每个 word 是一个 node。

如果两个 word 只差一个字符，它们之间有一条 edge。

因为每次 transformation 成本相同， BFS 可以找到最短 transformation length。

1️⃣9️⃣ BFS With State

Node 不一定只是位置

有些 BFS 的 state 不只是当前位置。

Examples:

(row, col, remaining_obstacle_eliminations)
(node, keys_collected)
(position, used_special_move)
(word, steps)

Example State

(row, col, remaining_k)

在 obstacle elimination shortest path 中，同一个 cell 如果剩余 k 不同，它们不是同一个状态。

Visited 必须包含完整 State

错误：

visited.add((row, col))

正确：

visited.add((row, col, remaining_k))

👉 面试回答

在 BFS 中， visited key 必须表示完整 state。

有时候 position alone 不够。

如果两条路径到达同一个 cell，但剩余资源不同，它们未来可走的路径也不同。

所以 visited set 应该包含所有会影响后续决策的变量。

2️⃣0️⃣ BFS Complexity Analysis

Graph BFS

对于 V 个 vertices 和 E 条 edges：

Time: O(V + E)
Space: O(V)

原因：

each vertex is enqueued once
each edge is checked once or twice

Grid BFS

对于 m x n grid：

Time: O(mn)
Space: O(mn)

因为每个 cell 最多处理一次。

Word Ladder Basic Version

设：

N = number of words
L = word length

基础 neighbor generation 可能是：

O(N * L * 26)

取决于实现方式。

👉 面试回答

Graph BFS 的复杂度是 O(V + E)，因为每个 node 最多访问一次，每条 edge 最多检查一次或两次。

Grid BFS 是 O(mn)，因为每个 cell 最多处理一次。

Space complexity 通常由 queue 和 visited set 决定。

2️⃣1️⃣ 常见 Edge Cases

Empty Input

root = None
grid = []
graph = {}

Start Equals Target

start == target

通常 distance 是：

或者直接返回答案。

No Path Exists

根据题目返回：

-1
0
[]

Obstacles

Grid cells 可能 blocked：

"#"
0
-1

enqueue 前要检查。

Multiple Sources

所有 sources 必须在 BFS 开始前都加入 queue。

Revisit Problems

如果 visited 缺失或不完整， BFS 可能 infinite loop 或 duplicate work。

👉 面试回答

BFS 常见 edge cases 包括 empty input、 start already equals target、 no valid path、 blocked cells、 multiple sources、以及 visited state 不完整。

我通常在 queue 初始化前后处理这些情况。

2️⃣2️⃣ 常见错误

Mistake 1: 忘记 Visited

Graph BFS 没有 visited，可能无限循环。

Mistake 2: Mark Visited 太晚

如果等到 pop 时才 mark visited，可能会重复 enqueue。

Mistake 3: 混淆 BFS 和 DFS

不小心用 stack，就变成 DFS。

BFS 需要：

queue.popleft()

Mistake 4: Level Counting 错误

每处理一个 node 就增加 distance 是错误的。

应该每一层结束后再增加。

Mistake 5: Visited 没包含完整 State

Stateful BFS 中，visited 必须包含所有相关变量。

Mistake 6: 用 BFS 解 Weighted Shortest Path

如果 edge weights 不同，应该用：

Dijkstra

而不是 plain BFS。

👉 面试回答

BFS 常见错误包括：忘记 visited、 visited mark 太晚、用 stack 误写成 DFS、 level counting 错误、 visited 没包含完整 state、以及用 BFS 解 weighted shortest path。

Plain BFS 只有在所有 edge cost 相同时，才能保证 shortest path。

2️⃣3️⃣ 什么时候 BFS 适用？

Good Fit

当题目问：

minimum steps
shortest path in unweighted graph
level-order traversal
nearest target
spread over time
distance from source
simultaneous expansion

Problem Signals

看到这些关键词时想到 BFS：

minimum number of moves
shortest path
nearest
level order
each minute
spread
fewest steps
unweighted graph
grid shortest path

👉 面试回答

当题目问 shortest path、minimum steps、nearest target、 level-order traversal，或者 simultaneous spread 时，我会优先考虑 BFS。

关键条件是每一步或每条 edge 的 cost 相同。

2️⃣4️⃣ 什么时候 BFS 不适用？

Not Good Fit

Plain BFS 不适合：

edges have different weights
need all combinations
need recursive backtracking
need topological order with dependencies
need optimal substructure over choices

Better Alternatives

Problem Type	Better Pattern
Weighted shortest path	Dijkstra
Negative weights	Bellman-Ford
All combinations	Backtracking
Deep path exploration	DFS
Dependency ordering	Topological Sort
Optimization with overlapping subproblems	Dynamic Programming

👉 面试回答

BFS 不是所有题都适合。

如果 edge weights 不同， plain BFS 不再保证 shortest path。

Weighted shortest path 应该考虑 Dijkstra。

如果是 exhaustive combinations， backtracking 或 DFS 通常更适合。

2️⃣5️⃣ 标准模板

Basic Graph BFS Template

from collections import deque

def bfs(graph, start):
    queue = deque([start])
    visited = set([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 Template

from collections import deque

def shortest_path(graph, start, target):
    queue = deque([(start, 0)])
    visited = set([start])

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

        if node == target:
            return distance

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

    return -1

Level-Order Template

from collections import deque

def bfs_by_level(start, graph):
    queue = deque([start])
    visited = set([start])
    level = 0

    while queue:
        size = len(queue)

        for _ in range(size):
            node = queue.popleft()

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

        level += 1

Grid BFS Template

from collections import deque

def grid_bfs(grid, start_row, start_col):
    rows = len(grid)
    cols = len(grid[0])
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    queue = deque([(start_row, start_col)])
    visited = set([(start_row, start_col)])

    while queue:
        row, col = queue.popleft()

        for dr, dc in directions:
            nr = row + dr
            nc = col + dc

            if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                continue

            if (nr, nc) in visited:
                continue

            if grid[nr][nc] == "#":
                continue

            visited.add((nr, nc))
            queue.append((nr, nc))

Multi-Source BFS Template

from collections import deque

def multi_source_bfs(grid, sources):
    rows = len(grid)
    cols = len(grid[0])
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    queue = deque()
    dist = [[-1] * cols for _ in range(rows)]

    for r, c in sources:
        queue.append((r, c))
        dist[r][c] = 0

    while queue:
        row, col = queue.popleft()

        for dr, dc in directions:
            nr = row + dr
            nc = col + dc

            if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                continue

            if dist[nr][nc] != -1:
                continue

            dist[nr][nc] = dist[row][col] + 1
            queue.append((nr, nc))

    return dist

BFS With State Template

from collections import deque

def bfs_with_state(start_state):
    queue = deque([(start_state, 0)])
    visited = set([start_state])

    while queue:
        state, steps = queue.popleft()

        if is_target(state):
            return steps

        for next_state in get_neighbors(state):
            if next_state not in visited:
                visited.add(next_state)
                queue.append((next_state, steps + 1))

    return -1

🧠 Staff-Level Answer Final

👉 面试回答完整版本

BFS，也就是 Breadth-First Search，是一种按层遍历 nodes 的算法。

它使用 queue，也就是 first-in, first-out 的数据结构。

这保证了先被发现的 nodes 会先被处理。

BFS 特别适合 unweighted graph 中的 shortest path，因为它会先探索所有距离为 d 的 nodes，再探索距离为 d + 1 的 nodes。

所以当 BFS 第一次到达 target node 时，它已经找到了最少 edge 数或最少 steps。

一个标准 BFS 通常包含： queue、visited set、start node，以及 neighbor generation。

Visited set 非常重要，因为 graph 可能有 cycles。我通常在 enqueue 的时候 mark visited，而不是等 dequeue 时再 mark，这样可以避免同一个 node 被不同 path 重复加入 queue。

对 tree 问题， BFS 常用于 level-order traversal。我会通过当前 queue size 来一层一层处理。

对 grid 问题，我会把每个 cell 当作 graph node。 Neighbor generation 通常来自四个方向或八个方向。 Enqueue 之前，我会检查 boundary、obstacle 和 visited state。

Multi-source BFS 用于多个 source 同时扩散的问题。例如 Rotting Oranges、01 Matrix、Walls and Gates。通过一开始把所有 sources 加入 queue， BFS 可以保证每个 cell 第一次被访问时，就是从最近 source 到达的。

有些 BFS 问题的 state 不只是当前 node。比如 state 可能包括 position、remaining obstacle eliminations、 collected keys，或者 special move 是否已经使用。这种情况下， visited set 必须包含完整 state，不能只包含 position。

Graph BFS 的复杂度是 O(V + E)，因为每个 vertex 最多访问一次，每条 edge 最多检查一次或两次。 Grid BFS 的复杂度是 O(mn)，因为每个 cell 最多处理一次。

BFS 不适合 weighted shortest path，除非所有 edge weights 相同。如果权重不同，通常应该使用 Dijkstra。

高级工程师解释 BFS 时，我会讲清楚： node 是什么， neighbor 如何生成， queue 代表什么， visited state 包含什么，为什么 level-order traversal 能保证 shortest path。

⭐ Final Insight

BFS 的核心不是“用 queue”。

它的核心是 level-by-level expansion。

Senior-level 的重点是：

node 是什么， neighbor 怎么生成， visited state 包含什么， queue 中每一层代表什么，为什么第一次到达 target 就是 shortest path，以及为什么 plain BFS 只适用于 unweighted graph。

能讲清楚这些， BFS 就是一种解决 shortest path、minimum steps 和 simultaneous expansion 的基础算法模型。

🎯 BFS Basics

1️⃣ Core Framework

2️⃣ What Problem Are We Solving?

3️⃣ Why BFS Works

BFS Uses a Queue

Level-by-Level Expansion

Key Requirement

4️⃣ BFS vs DFS

BFS

DFS

Comparison

5️⃣ Basic BFS Template

Graph BFS Template

Key Components

6️⃣ Level-Order BFS Template

Why Level Tracking Matters

Template

Key Idea

7️⃣ BFS on Binary Tree

Problem

Code

Why It Works

8️⃣ Minimum Depth of Binary Tree

Problem

Why BFS Is Good

Code

9️⃣ BFS on Graph

Problem

Graph Representation

Code

Why Visited Is Required

🔟 When to Mark Visited

Recommended

Why?

Pattern

1️⃣1️⃣ Shortest Path in Unweighted Graph

Problem

Code

Why First Target Is Shortest

1️⃣2️⃣ Grid BFS

Problem Pattern

Direction Array

Boundary Check

1️⃣3️⃣ Grid BFS Template

Key Components

1️⃣4️⃣ Number of Islands

Problem

Code

Key Insight

1️⃣5️⃣ Rotting Oranges

Problem

Why Multi-Source BFS?

Code

1️⃣6️⃣ Multi-Source BFS

What Is Multi-Source BFS?

When to Use

Examples

1️⃣7️⃣ 01 Matrix

Problem

Key Idea

Code

1️⃣8️⃣ Word Ladder

Problem

Why BFS?

Basic Code

Optimization Note

1️⃣9️⃣ BFS With State

When Node Is Not Enough

Example State

Visited Must Include Full State

2️⃣0️⃣ BFS Complexity Analysis

Graph BFS

Grid BFS

Word Ladder Basic Version

2️⃣1️⃣ Common Edge Cases

Empty Input

Start Equals Target

No Path Exists

Obstacles

Multiple Sources