Duyệt rộng (BFS)

Khái niệm

Duyệt theo chiều rộng (Breadth-First Search — BFS) khám phá tất cả đỉnh ở khoảng cách d trước khi khám phá các đỉnh ở khoảng cách d+1. BFS dùng hàng đợi (queue) để quản lý thứ tự duyệt.

Tính chất nổi bật: BFS trên đồ thị không có trọng số (unweighted) luôn tìm được đường đi ngắn nhất từ nguồn đến mọi đỉnh.

Ứng dụng:

Tìm đường đi ngắn nhất (không có trọng số)
Kiểm tra khả năng đến được (reachability)
Bài toán lan rộng (spreading problems)
Tìm khoảng cách ngắn nhất trong lưới

So sánh BFS và DFS

graph TD; A["Đỉnh nguồn S"] --> B["BFS: Duyệt theo tầng\nLayer 1 → Layer 2 → ..."]; A --> C["DFS: Đi sâu vào 1 nhánh\nrồi quay lại"]; B --> D["Đường đi ngắn nhất\n(không có trọng số)"]; C --> E["Linh hoạt, ít bộ nhớ\nphù hợp backtracking"];

Cài đặt BFS cơ bản

from collections import deque

def bfs(do_thi, start):
    da_tham = set([start])
    queue = deque([start])
    thu_tu = []

    while queue:
        u = queue.popleft()   # Lấy từ đầu hàng đợi
        thu_tu.append(u)
        for v in do_thi.get(u, []):
            if v not in da_tham:
                da_tham.add(v)
                queue.append(v)   # Thêm vào cuối hàng đợi

    return thu_tu

do_thi = {0:[1,2], 1:[0,3,4], 2:[0], 3:[1], 4:[1,5], 5:[4]}
print(bfs(do_thi, 0))   # [0, 1, 2, 3, 4, 5]  (thứ tự theo tầng)

Tìm đường đi ngắn nhất

from collections import deque

def bfs_khoang_cach(do_thi, start, end):
    """
    Trả về độ dài đường đi ngắn nhất từ start đến end,
    hoặc -1 nếu không có đường đi.
    """
    if start == end:
        return 0

    da_tham = {start}
    queue = deque([(start, 0)])   # (đỉnh, khoảng cách)

    while queue:
        u, dist = queue.popleft()
        for v in do_thi.get(u, []):
            if v == end:
                return dist + 1
            if v not in da_tham:
                da_tham.add(v)
                queue.append((v, dist + 1))

    return -1   # Không tìm thấy

do_thi = {0:[1,2], 1:[0,3,4], 2:[0], 3:[1], 4:[1,5], 5:[4]}
print(bfs_khoang_cach(do_thi, 0, 5))   # 3 (0→1→4→5)
print(bfs_khoang_cach(do_thi, 2, 3))   # 3 (2→0→1→3)
print(bfs_khoang_cach(do_thi, 0, 0))   # 0

Bài tập luyện tập

Dễ — BFS trên lưới: số bước ngắn nhất

Tìm đường đi ngắn nhất từ ô S đến ô E trong lưới. Ô . đi được, ô # là tường.

from collections import deque

def bfs_luoi(luoi, start, end):
    """
    luoi: list of string — '.' đi được, '#' tường
    start, end: (row, col)
    Trả về số bước ngắn nhất, hoặc -1 nếu không có đường.
    """
    rows, cols = len(luoi), len(luoi[0])
    queue = deque([(start, 0)])
    da_tham = {start}

    while queue:
        (r, c), dist = queue.popleft()
        if (r, c) == end:
            return dist
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols
                    and luoi[nr][nc] != '#'
                    and (nr, nc) not in da_tham):
                da_tham.add((nr, nc))
                queue.append(((nr, nc), dist + 1))

    return -1

luoi = [
    ".....",
    ".###.",
    ".....",
    ".###.",
    ".....",
]
print(bfs_luoi(luoi, (0,0), (4,4)))   # 8
print(bfs_luoi(luoi, (0,0), (2,2)))   # 8 (phải đi vòng)

Trung bình — BFS nhiều nguồn (multi-source BFS)

Cho lưới có nhiều điểm xuất phát, tìm khoảng cách ngắn nhất từ mỗi ô đến điểm xuất phát gần nhất.

from collections import deque

def khoang_cach_gan_nhat(luoi):
    """
    luoi[r][c] = 1: điểm xuất phát, 0: ô cần tính khoảng cách.
    Trả về ma trận khoảng cách ngắn nhất từ mỗi ô tới điểm 1 gần nhất.
    """
    rows, cols = len(luoi), len(luoi[0])
    dist = [[float('inf')] * cols for _ in range(rows)]
    queue = deque()

    # Khởi tạo: tất cả điểm xuất phát có khoảng cách = 0
    for r in range(rows):
        for c in range(cols):
            if luoi[r][c] == 1:
                dist[r][c] = 0
                queue.append((r, c))

    while queue:
        r, c = queue.popleft()
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] == float('inf'):
                dist[nr][nc] = dist[r][c] + 1
                queue.append((nr, nc))

    return dist

luoi = [[0,0,0],[0,1,0],[1,0,0]]
for row in khoang_cach_gan_nhat(luoi):
    print(row)
# [2, 1, 2]
# [1, 0, 1]
# [0, 1, 2]

Khó — Biến đổi từ (Word Ladder)

Cho hai từ begin và end và một danh sách từ. Tìm chuỗi biến đổi ngắn nhất: mỗi bước đổi đúng một chữ cái, và mỗi từ trung gian phải có trong danh sách.

from collections import deque

def word_ladder(begin, end, word_list):
    """
    Tìm chuỗi biến đổi ngắn nhất. Trả về độ dài, hoặc 0 nếu không có.
    """
    word_set = set(word_list)
    if end not in word_set:
        return 0

    queue = deque([(begin, 1)])
    da_tham = {begin}

    while queue:
        word, length = queue.popleft()
        for i in range(len(word)):
            for ch in 'abcdefghijklmnopqrstuvwxyz':
                next_word = word[:i] + ch + word[i+1:]
                if next_word == end:
                    return length + 1
                if next_word in word_set and next_word not in da_tham:
                    da_tham.add(next_word)
                    queue.append((next_word, length + 1))

    return 0

words = ["hot", "dot", "dog", "lot", "log", "cog"]
print(word_ladder("hit", "cog", words))   # 5 (hit→hot→dot→dog→cog)
print(word_ladder("hit", "xyz", words))   # 0 (không có đường)

Kết luận

BFS là công cụ không thể thiếu khi bài toán yêu cầu số bước ít nhất trong đồ thị không có trọng số. Với đồ thị có trọng số, cần dùng Dijkstra trong mục Lý thuyết đồ thị. Tiếp theo hãy học Quy hoạch động — kỹ thuật nâng cao xử lý bài toán tối ưu với cấu trúc con chồng chéo.

Trong series này: