Chương 10 - Breadth-First Search (BFS)

BFS duyệt graph theo lớp (level by level). Đặc tính then chốt: nếu mọi cạnh có trọng số bằng nhau (= 1), BFS từ source cho ra đường đi ngắn nhất đến mọi đỉnh khác. Đây là lý do BFS xuất hiện rất nhiều ở các bài “shortest path in unweighted graph”, “minimum steps”, “minimum transformations”, …

Mục tiêu chương

Sau chương này, bạn sẽ:

  • Nhận diện BFS = shortest path trên graph không trọng số.
  • Thuộc multi-source BFS (rotting oranges, walls and gates).
  • Biết state design: node, cell, string, board index, (r, c, k).
  • Avoid off-by-one distance bằng BFS level-order.

Khi nào dùng pattern này?

  • Tìm shortest path trong graph không trọng số (hoặc trọng số đồng nhất).
  • Đề yêu cầu số bước tối thiểu để biến đổi state này sang state khác.
  • Duyệt level by level (level order traversal, layer of grid).
  • Multi-source BFS khi nhiều nguồn cùng lan toả (rotting oranges, walls and gates).
  • Khi đề bài “graph ngầm” (state space) - Word Ladder, Open Lock, Snakes & Ladders.

Phân biệt với DFS: - BFS: tìm path ngắn nhất, duyệt theo lớp. - DFS: thám hiểm sâu (path đầu tiên đến đích), check connectivity, đếm components.

Template code 

from collections import deque

# 1) BFS chuẩn - đường đi ngắn nhất từ start tới target
def bfs_shortest(start, target, neighbors_fn) -> int:
    if start == target:
        return 0
    visited = {start}
    queue = deque([(start, 0)])         # (node, distance)
    while queue:
        node, dist = queue.popleft()
        for nb in neighbors_fn(node):
            if nb == target:
                return dist + 1
            if nb not in visited:
                visited.add(nb)
                queue.append((nb, dist + 1))
    return -1


# 2) BFS theo lớp - không cần lưu distance trong queue
def bfs_by_level(start, neighbors_fn):
    visited = {start}
    queue = deque([start])
    level = 0
    while queue:
        size = len(queue)
        for _ in range(size):
            node = queue.popleft()
            # ... xử lý node ở level này ...
            for nb in neighbors_fn(node):
                if nb not in visited:
                    visited.add(nb)
                    queue.append(nb)
        level += 1


# 3) Multi-source BFS - đẩy nhiều nguồn vào queue cùng lúc
def multi_source(sources: list, neighbors_fn):
    queue = deque(sources)
    visited = set(sources)
    while queue:
        ...

Bài tự luyện cuối chương

  • LC 199 - Binary Tree Right Side View
  • LC 207 - Course Schedule (Chương 9)
  • LC 286 - Walls and Gates (multi-source)
  • LC 542 - 01 Matrix (multi-source)
  • LC 815 - Bus Routes
  • LC 847 - Shortest Path Visiting All Nodes (Bitmask DP, Chương 40)
  • LC 994 - Rotting Oranges (bài 10.2)

10.1 Binary Tree Level Order Traversal (LC 102)

Đề bài

Cho root của một binary tree. Trả về level order traversal dưới dạng danh sách các list (mỗi list chứa các node ở 1 level từ trên xuống, trái sang phải).

Ví dụ 

Input:  root = [3, 9, 20, null, null, 15, 7]   (LC level-order serialize)

        Cây thực tế:
              3
             / \
            9   20
               /  \
              15   7

Output: [[3], [9, 20], [15, 7]]

Ràng buộc

  • 0 <= số node <= 2000
  • -1000 <= node.val <= 1000

Clarifying questions

  • Root có thể null không? → Có (return empty list).
  • Output có cần ngược lại không? → Không (LC 102 yêu cầu top-down).

Hướng tiếp cận

BFS theo lớp. Mỗi vòng outer = 1 level. Đầu mỗi vòng, ghi size = len(queue), sau đó pop đúng size node - đó là toàn bộ level hiện tại.

Hình minh hoạ:

Init:  queue = [3]
Level 0: size=1
  Pop 3. result.append([3]). Push 9, 20.
  queue = [9, 20]

Level 1: size=2
  Pop 9 → null children.
  Pop 20 → push 15, 7.
  result.append([9, 20]).
  queue = [15, 7]

Level 2: size=2
  Pop 15, 7 → null children.
  result.append([15, 7]).
  queue = []

→ [[3], [9, 20], [15, 7]]

Code Python 3 

from collections import deque
from typing import List, Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right


class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        result: List[List[int]] = []
        queue = deque([root])
        while queue:
            size = len(queue)
            level_vals: list[int] = []
            for _ in range(size):
                node = queue.popleft()
                level_vals.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level_vals)
        return result

Phân tích độ phức tạp

  • Thời gian: O(n). Bộ nhớ: O(n) cho queue (worst-case level cuối có ~n/2 node).

Bình luận

  • Mẫu BFS theo lớp này dùng cho rất nhiều bài tree khác:
    • LC 107 - Bottom-up Level Order: như trên rồi result.reverse().
    • LC 199 - Right Side View: lấy level_vals[-1] mỗi level.
    • LC 515 - Largest Value in Each Tree Row: max(level_vals).
    • LC 103 - Zigzag Level Order: alternate level_vals reverse.
  • Bẫy: không lưu size = len(queue) trước vòng inner → queue bị mở rộng trong khi for loop → level bị “trộn”.

Bài tự luyện liên quan

  • LC 107 - Binary Tree Level Order Traversal II.
  • LC 199 - Binary Tree Right Side View.
  • LC 103 - Binary Tree Zigzag Level Order Traversal.

10.2 Rotting Oranges (LC 994) - Multi-source BFS

Đề bài

Cho lưới grid với các giá trị: - 0 = ô trống - 1 = quả tươi - 2 = quả thối

Mỗi phút, mỗi quả thối làm 4 ô kề bên (lên/xuống/trái/phải) có quả tươi trở thành thối. Trả về số phút tối thiểu để không còn quả tươi, hoặc -1 nếu không khả thi.

Ví dụ 

Input:  grid = [[2,1,1],
                [1,1,0],
                [0,1,1]]
        (0 = empty, 1 = fresh orange, 2 = rotten)
Output: 4   (số phút để mọi orange thối)

Input:  grid = [[2,1,1],
                [0,1,1],
                [1,0,1]]
Output: -1   (quả tươi ở (2,0) bị cô lập, không bao giờ thối)

Ràng buộc

  • 1 <= rows, cols <= 10
  • grid[i][j] ∈ {0, 1, 2}

Clarifying questions

  • Không có quả thối ban đầu? → Vẫn duyệt; nếu không có quả tươi → 0.

Hướng tiếp cận

Insight: Mỗi quả thối là một nguồn lan toả. Tất cả nguồn lan đồng thời mỗi phút → multi-source BFS.

Quy trình: 1. Đẩy tất cả quả thối ban đầu vào queue cùng lúc (level 0). 2. BFS theo lớp - mỗi level tăng minutes thêm 1. 3. Đếm số quả tươi ban đầu. Mỗi lần thối thêm một quả → giảm count. 4. Cuối: nếu còn quả tươi → -1, ngược lại → minutes.

Hình minh hoạ với grid 3x3:

Init:                t=0:              t=1:              t=4:
[2, 1, 1]            [2, 1, 1]         [2, 2, 1]         [2, 2, 2]
[1, 1, 0]            [1, 1, 0]         [2, 1, 0]         [2, 2, 0]
[0, 1, 1]            [0, 1, 1]         [0, 1, 1]         [0, 2, 2]
                                       (4 quả tươi)      (xong)

Hàng động BFS:
Queue chứa các ô (i, j) cùng level → mỗi vòng outer pop hết queue rồi push
hàng xóm. Số vòng outer = số phút.

Code Python 3 

from collections import deque
from typing import List

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        queue: deque[tuple[int, int]] = 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

        if fresh == 0:
            return 0

        minutes = 0
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        while queue and fresh > 0:
            minutes += 1
            for _ in range(len(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 grid[nr][nc] == 1:
                        grid[nr][nc] = 2
                        fresh -= 1
                        queue.append((nr, nc))

        return minutes if fresh == 0 else -1

Phân tích độ phức tạp

  • Thời gian: O(R · C). Bộ nhớ: O(R · C).

Bình luận

  • Multi-source BFS là pattern cực mạnh: thay vì BFS từng nguồn rồi lấy min, ta gộp tất cả nguồn vào level 0 → BFS một lần ra distance tới nguồn gần nhất cho mọi ô.
  • Bẫy: trả 0 ngay nếu không có quả tươi ban đầu - nếu không, vòng outer không chạy và return minutes = 0 đúng nhưng vô tình “may rủi”.

Bài tự luyện liên quan

  • LC 286 - Walls and Gates.
  • LC 542 - 01 Matrix.
  • LC 1162 - As Far From Land As Possible.

10.3 Word Ladder (LC 127)

Đề bài

Cho beginWord, endWord, và wordList (các từ cùng độ dài). Mỗi bước biến đổi: thay đúng 1 ký tự trong word hiện tại sao cho từ mới vẫn nằm trong wordList. Trả về số bước tối thiểu để biến beginWord → endWord (bao gồm cả 2 đầu). Trả 0 nếu không khả thi.

Ví dụ 

Input:  beginWord = "hit", endWord = "cog"
        wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Giải thích: hit → hot → dot → dog → cog  (độ dài 5)

Input:  beginWord = "hit", endWord = "cog"
        wordList = ["hot","dot","dog","lot","log"]
Output: 0    (cog không trong wordList)

Ràng buộc

  • 1 <= len(beginWord) <= 10
  • 1 <= len(wordList) <= 5000
  • Tất cả từ cùng độ dài.

Clarifying questions

  • endWord không trong wordList? → Trả 0.
  • beginWord có cần trong wordList không? → Không bắt buộc (LC 127).

Hướng tiếp cận

Mô hình hoá: Mỗi từ là 1 đỉnh; có cạnh giữa 2 từ nếu chúng khác nhau đúng 1 ký tự. Bài thành shortest path trong undirected graph → BFS.

Tối ưu sinh hàng xóm: Thay vì so sánh từ cur với mọi từ trong wordList (O(N·L) mỗi node) - quá chậm - ta sinh hàng xóm bằng cách thay từng vị trí ký tự bằng a..z (O(26·L) mỗi node).

Hình minh hoạ với "hit" → "cog":

Level 1: hit
Level 2: hot                (đổi i→o)
Level 3: dot, lot           (đổi h→d/l)
Level 4: dog, log           (đổi t→g)
Level 5: cog                ★ đáp án (5 bước)

Code Python 3 

from collections import deque
from typing import List

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        word_set = set(wordList)
        if endWord not in word_set:
            return 0

        queue = deque([(beginWord, 1)])
        visited = {beginWord}
        while queue:
            word, steps = queue.popleft()
            if word == endWord:
                return steps
            for i in range(len(word)):
                for ch in 'abcdefghijklmnopqrstuvwxyz':
                    if ch == word[i]:
                        continue
                    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

Phân tích độ phức tạp

  • Thời gian: O(N · L² · 26) với N = số từ, L = độ dài từ.
    • Mỗi node: sinh 26·L neighbors, mỗi cái xây string O(L).
  • Bộ nhớ: O(N · L).

Bình luận

  • Tối ưu hơn - Bidirectional BFS: BFS đồng thời từ beginWord và endWord, dừng khi 2 BFS gặp nhau. Giảm O(b^d) xuống O(b^(d/2)) - cải thiện đáng kể khi đường đi dài.
  • Tối ưu sinh hàng xóm với pattern dict: Pre-build {"h*t": ["hot", "hit", ...]}. Sau đó hàng xóm của "hot" là union các pattern "_ot", "h_t", "ho_". Cách này nhanh hơn cho L lớn.
  • Bẫy: đếm steps bắt đầu từ 1 (bao gồm beginWord).
  • Follow-up:
    • LC 126 - Word Ladder II: trả về tất cả đường đi ngắn nhất.

Bài tự luyện liên quan

  • LC 126 - Word Ladder II.
  • LC 433 - Minimum Genetic Mutation (cùng pattern).
  • LC 752 - Open the Lock (bài 10.4).

10.4 Open the Lock (LC 752)

Đề bài

Cho khoá 4 ô số 0000. Mỗi bước: xoay 1 ô số lên hoặc xuống 1 đơn vị (vòng 0..9). Cho deadends (các tổ hợp không được đến) và target. Trả về số bước tối thiểu để đến target, hoặc -1 nếu không khả thi.

Ví dụ 

Input:  deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Giải thích: 0000 → 1000 → 1100 → 1200 → 1201 → 1202 → 0202
            (không trùng deadend nào)

Ràng buộc

  • 1 <= len(deadends) <= 500
  • target không trong deadends.

Clarifying questions

  • Start 0000 có trong deadends không? → Trả -1.
  • target == start? → Trả 0.

Hướng tiếp cận

State space implicit graph. Mỗi state là chuỗi 4 chữ số → 10^4 = 10000 state. Từ mỗi state có 8 transition (4 ô × 2 chiều).

BFS: bắt đầu từ "0000", BFS đến target. Skip các state trong deadends.

Hình minh hoạ một phần BFS:

Level 0: 0000
Level 1: 1000, 9000, 0100, 0900, 0010, 0090, 0001, 0009  (8 hàng xóm)
Level 2: ... (mỗi node 8 hàng xóm, trừ những cái đã visited / deadend)
...
Level 6: 0202  ★

Code Python 3 

from collections import deque
from typing import List

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        dead = set(deadends)
        if "0000" in dead:
            return -1
        if target == "0000":
            return 0

        def neighbors(state: str):
            for i in range(4):
                d = int(state[i])
                for delta in (-1, 1):
                    new_d = (d + delta) % 10
                    yield state[:i] + str(new_d) + state[i + 1:]

        visited = {"0000"}
        queue = deque([("0000", 0)])
        while queue:
            state, steps = queue.popleft()
            for nb in neighbors(state):
                if nb in dead or nb in visited:
                    continue
                if nb == target:
                    return steps + 1
                visited.add(nb)
                queue.append((nb, steps + 1))
        return -1

Phân tích độ phức tạp

  • Thời gian: O(10^4) state × 8 neighbors = O(80000).
  • Bộ nhớ: O(10^4).

Bình luận

  • Bidirectional BFS cũng áp được, giảm cỡ một nửa số state phải duyệt.
  • Bẫy: kiểm tra "0000" in dead trước - nếu start đã chết thì return ngay.
  • Liên hệ: Pattern “BFS trên state space rời rạc” còn xuất hiện ở Sliding Puzzle (LC 773), Snakes and Ladders (10.6), …

Bài tự luyện liên quan

  • LC 773 - Sliding Puzzle.
  • LC 127 - Word Ladder.
  • LC 815 - Bus Routes.

10.5 Shortest Path in Binary Matrix (LC 1091)

Đề bài

Cho ma trận vuông n × n chứa 0 (đi được) và 1 (vật cản). Tìm đường đi ngắn nhất từ (0,0) đến (n-1,n-1), đi được 8 hướng (4 trục + 4 chéo). Độ dài đường đi = số ô đi qua (kể cả start và end). Trả -1 nếu không đi được.

Ví dụ 

Input:  grid = [[0,0,0],
                [1,1,0],
                [1,1,0]]
Output: 4
Giải thích: (0,0) → (0,1) → (1,2) → (2,2)

Ràng buộc

  • 1 <= n <= 100
  • grid[i][j] ∈ {0, 1}
  • grid[0][0] và grid[n-1][n-1] có thể là 1 (kết quả -1).

Clarifying questions

  • (0,0) hoặc (n-1,n-1) là 1 (vật cản)? → Trả -1.
  • n=1 với grid[0][0]=0? → Trả 1.

Hướng tiếp cận

BFS từ (0,0) với 8 hướng. Mỗi cạnh trọng số 1 (mỗi bước = 1 ô).

Code Python 3 

from collections import deque
from typing import List

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if grid[0][0] != 0 or grid[n - 1][n - 1] != 0:
            return -1
        if n == 1:
            return 1

        dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
        queue = deque([(0, 0, 1)])     # (r, c, steps)
        grid[0][0] = 1                  # mark visited
        while queue:
            r, c, steps = queue.popleft()
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                    if (nr, nc) == (n - 1, n - 1):
                        return steps + 1
                    grid[nr][nc] = 1
                    queue.append((nr, nc, steps + 1))
        return -1

Phân tích độ phức tạp

  • Thời gian: O(n²). Bộ nhớ: O(n²).

Bình luận

  • Tối ưu space: dùng grid[r][c] = 1 để mark visited thay cho set riêng. Mutating input - nên hỏi interviewer trước có cho phép.
  • Tối ưu hơn - A*: với heuristic = max(|nr - end_r|, |nc - end_c|) (Chebyshev distance vì 8 hướng), A* nhanh hơn BFS thuần đáng kể (Chương 30).
  • Bẫy: quên check n == 1 → trả về 1 thay vì đi vào BFS (sẽ không pop được).

Bài tự luyện liên quan

  • LC 542 - 01 Matrix.
  • LC 994 - Rotting Oranges.
  • LC 1293 - Shortest Path with Obstacles Elimination.

10.6 Snakes and Ladders (LC 909)

Đề bài

Cho bàn cờ n × n đánh số ô theo zigzag (như cờ rắn rồng). board[i][j] = -1 nghĩa là ô bình thường; nếu >= 1, đó là rắn/thang đưa bạn đến ô số đó.

Mỗi bước, từ ô hiện tại bạn được tung xúc xắc (6 mặt) đi 1..6 bước; nếu ô đến có rắn/thang, tự động đi tiếp đến ô đích. Tìm số lần tung tối thiểu để đến ô n*n cuối cùng. Trả -1 nếu không thể.

Ví dụ 

Input:  board =
        [[-1,-1,-1,-1,-1,-1],
         [-1,-1,-1,-1,-1,-1],
         [-1,-1,-1,-1,-1,-1],
         [-1,35,-1,-1,13,-1],
         [-1,-1,-1,-1,-1,-1],
         [-1,15,-1,-1,-1,-1]]
Output: 4

Ràng buộc

  • 2 <= n <= 20

Clarifying questions

  • Có thể đứng yên? → Không (mỗi turn phải tung).
  • Có thể nhảy quá target? → Phải dừng nếu đi đến đúng target.

Hướng tiếp cận

State space: mỗi ô đánh số 1..n². Từ ô s, có thể đi đến ô s+1, s+2, ..., s+6 (rồi nhảy nếu có rắn/thang). Mỗi cạnh = 1 lần tung → BFS ra số tung tối thiểu.

Trick zigzag → tọa độ: - Hàng (từ dưới): (label - 1) // n. - Cột tuỳ hướng hàng: chẵn từ dưới thì trái → phải, lẻ thì phải → trái.

Code Python 3 

from collections import deque
from typing import List

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n = len(board)
        def label_to_pos(label: int) -> tuple[int, int]:
            quot, rem = divmod(label - 1, n)
            row = n - 1 - quot
            col = rem if quot % 2 == 0 else n - 1 - rem
            return row, col

        target = n * n
        visited = {1}
        queue = deque([(1, 0)])     # (square, throws)
        while queue:
            square, throws = queue.popleft()
            for d in range(1, 7):
                nxt = square + d
                if nxt > target:
                    break
                r, c = label_to_pos(nxt)
                if board[r][c] != -1:
                    nxt = board[r][c]
                if nxt == target:
                    return throws + 1
                if nxt not in visited:
                    visited.add(nxt)
                    queue.append((nxt, throws + 1))
        return -1

Phân tích độ phức tạp

  • Thời gian: O(n²) state × 6 transitions.
  • Bộ nhớ: O(n²).

Bình luận

  • Bẫy zigzag: dễ tính sai (row, col) từ label. Vẽ ví dụ nhỏ n = 4 trên giấy để kiểm chứng công thức.
  • Tại sao BFS thay vì DP? Vì có thể có rắn (kéo lùi), không phải DAG - DP cần xử lý chu trình. BFS xử lý tự nhiên với visited.
  • Liên hệ: Cùng tinh thần “graph ngầm” của Word Ladder, Open Lock.

Bài tự luyện liên quan

  • LC 1293 - Shortest Path with Obstacles Elimination.
  • LC 815 - Bus Routes.
  • LC 1654 - Minimum Jumps to Reach Home.

Tóm tắt chương & Quyết định

BFS state design (đa dạng hơn bạn nghĩ)

State Bài tiêu biểu
node Shortest path unweighted graph
(r, c) Grid (Number of Islands, 01 Matrix)
word Word Ladder
(r, c, k_remaining) Shortest Path with K Obstacles
board_serialized Sliding Puzzle, Open Lock
bitmask_visited Shortest Path Visiting All Nodes
(node, parity) Bipartite, chẵn/lẻ bước

Word Ladder - neighbor generation

  • Wildcard map h*t → hot, hat, hit, ...: precompute O(N · L), lookup O(L).
  • Brute thử 26 chữ mỗi vị trí: O(L · 26) mỗi node, đơn giản hơn nhưng chậm khi N lớn.

Snakes & Ladders - 1D ↔︎ 2D

Board n×n serpentine: index i (1..n²) → tọa độ:

row_from_bottom = (i - 1) // n     # 0 = bottom row
col_in_row      = (i - 1) % n
r = n - 1 - row_from_bottom
c = col_in_row if row_from_bottom % 2 == 0 else n - 1 - col_in_row

Bug điển hình: quên đảo chiều hàng lẻ, hoặc index 0/1.

Distance: level BFS vs lưu trong queue

  • Level BFS (for _ in range(len(q)): ...): dist = số lần đã pop level. Dùng khi không cần trả dist từng node.
  • Lưu (node, d): linh hoạt hơn khi mỗi node có d riêng, nhưng tốn bộ nhớ.