BFS: tìm đường ít bước và mô phỏng lan truyền

Minh cần đưa sách từ phòng 1 đến phòng 7. Mỗi hành lang nối hai phòng và mất một phút đi qua. Có nhiều đường khác nhau, nên Minh muốn biết cần ít nhất bao nhiêu phút. Nếu duyệt sâu theo một nhánh trước, bạn có thể gặp đường dài trước đường ngắn. Ta sẽ tìm theo từng lớp để biết chắc thời điểm đến mỗi phòng là sớm nhất.

Hàng đợi đưa các đỉnh ra theo thứ tự được phát hiện

Duyệt theo chiều rộng (breadth-first search, viết tắt BFS) xử lý các đỉnh theo từng lớp khoảng cách. Lớp 0 có đỉnh xuất phát. Lớp 1 gồm các đỉnh tới được bằng một cạnh, lớp 2 gồm những đỉnh cần ít nhất hai cạnh, và cứ tiếp tục như vậy.

Xét đồ thị vô hướng có các cạnh 1-2, 1-3, 2-4, 2-5, 3-5, 3-6, 5-7 và 6-7. Đỉnh 8 đứng riêng. Hình có đủ các cạnh để bạn kiểm chứng đường đi đến đỉnh 7.

Đỉnh 7 có đường 1-2-5-7 gồm ba cạnh. Không có cạnh nối 1 với 5 hoặc 6, nên không thể tới 7 bằng hai cạnh. Đỉnh 8 không có hành lang nên không tới được từ 1.

BFS cần hàng đợi (queue): phần tử vào trước được lấy ra trước. Python có collections.deque, hỗ trợ append() ở cuối và popleft() ở đầu. Hai thao tác này có chi phí trung bình O(1).

from collections import deque
q = deque([1])
q.append(2)
q.append(3)
print(q.popleft())
q.append(4)
print(list(q))
print(q.popleft())

1
[2, 3, 4]
2

Sau khi lấy 1, hàng đợi chứa 2 và 3. Thêm 4 không đẩy 4 lên trước 2. Trái lại, list.pop(0) phải dịch các phần tử còn lại. Với hàng đợi lớn, lặp thao tác đó có thể tốn tổng O(n²).

Gán khoảng cách ngay khi phát hiện đỉnh

Ta tạo dist với giá trị -1 để biểu thị chưa tới được. Đặt dist[start] = 0, rồi đưa nguồn vào hàng đợi. Khi lấy u, ta xét từng hàng xóm v. Nếu dist[v] == -1, ta gán dist[v] = dist[u] + 1 trước khi thêm v vào hàng đợi.

from collections import deque
n = 8
edges = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 5), (3, 6), (5, 7), (6, 7)]
g = [[] for _ in range(n + 1)]
for u, v in edges:
    g[u].append(v)
    g[v].append(u)
dist = [-1] * (n + 1)
dist[1] = 0
q = deque([1])
while q:
    u = q.popleft()
    for v in g[u]:
        if dist[v] == -1:
            dist[v] = dist[u] + 1
            q.append(v)
print(*dist[1:])

0 1 1 2 2 2 3 -1

Kết quả cho lớp 0 là 1; lớp 1 là 2 và 3; lớp 2 là 4, 5 và 6; lớp 3 là 7. Giá trị -1 cuối cùng thuộc về đỉnh 8. Danh sách kề của đồ thị vô hướng chứa cả hai chiều. Với cạnh có hướng u -> v, chỉ thêm v vào g[u].

Hình dưới cho thấy trạng thái hàng đợi trong thứ tự xét cạnh như chương trình trên. Sau khi xử lý 2, đỉnh 5 đã được đánh dấu. Khi xử lý 3, ta gặp lại 5 nhưng không thêm lần nữa.

Ta đánh dấu khi thêm vào hàng đợi, không chờ đến khi lấy ra. Nếu đánh dấu muộn, 5 có thể được thêm bởi cả 2 lẫn 3. Trong đồ thị nhiều cạnh, số bản sao có thể làm chương trình tốn bộ nhớ và thời gian không cần thiết.

from collections import deque
g = [[], [2, 3], [1, 4], [1, 4], [2, 3]]
dist = [-1] * 5
dist[1] = 0
q = deque([1])
added = []
while q:
    u = q.popleft()
    for v in g[u]:
        if dist[v] == -1:
            dist[v] = dist[u] + 1
            q.append(v)
            added.append(v)
print(added)
print(dist[4])

[2, 3, 4]
2

Đỉnh 4 chỉ xuất hiện một lần trong added. Thứ tự hàng xóm có thể thay đổi thứ tự duyệt, nhưng không thay đổi khoảng cách ngắn nhất.

Lần phát hiện đầu tiên cho số cạnh ít nhất

Khi đang lấy các đỉnh lớp d, các đỉnh lớp d + 1 mới được thêm vào cuối hàng đợi. Vì vậy, mọi đỉnh lớp d được xử lý trước mọi đỉnh lớp d + 1. Hàng đợi không bỏ sót một lớp ngắn hơn để chuyển sang lớp dài hơn.

Giả sử BFS phát hiện v từ u và gán dist[v] = d + 1. Đường đang biết tới u có d cạnh, nên có một đường tới v với d + 1 cạnh. Nếu có đường ngắn hơn, đỉnh ngay trước v trên đường ấy đã thuộc lớp nhỏ hơn d. Đỉnh đó đã được xử lý trước u và phát hiện v trước rồi. Mâu thuẫn này chứng minh lần phát hiện đầu tiên là ngắn nhất.

Mỗi đỉnh được thêm tối đa một lần. Với n đỉnh và m cạnh vô hướng, tổng độ dài các danh sách kề là 2m. Thời gian là O(n + m) và bộ nhớ là O(n + m), tính cả đồ thị. Ví dụ n = 100000, m = 200000 cần xét tối đa 400000 mục kề, không phải 10 tỷ cặp đỉnh.

Muốn biết khoảng cách tới một đích duy nhất, có thể dừng ngay sau khi phát hiện đích. Nếu cần khoảng cách của mọi đỉnh, phải tiếp tục đến khi hàng đợi rỗng. Đừng dừng trước khi xử lý trường hợp nguồn trùng đích: khoảng cách khi đó bằng 0.

start = 4
target = 4
dist = [-1] * 6
dist[start] = 0
print(dist[target])

0

Mỗi đỉnh lưu cha để dựng lại một đường ngắn nhất

Khi phát hiện v từ u, ghi parent[v] = u. Sau BFS, đi ngược từ đích qua các cha cho đến nguồn. Đảo danh sách thu được để in theo chiều từ nguồn tới đích. Nếu dist[target] == -1, không có đường để dựng.

7 8 1 7
1 2
1 3
2 4
2 5
3 5
3 6
5 7
6 7

from collections import deque
import sys
data = list(map(int, sys.stdin.read().split()))
n, m, start, target = data[:4]
g = [[] for _ in range(n + 1)]
for i in range(m):
    u, v = data[4 + 2 * i: 6 + 2 * i]
    g[u].append(v)
    g[v].append(u)
dist = [-1] * (n + 1)
parent = [-1] * (n + 1)
dist[start] = 0
q = deque([start])
while q:
    u = q.popleft()
    for v in g[u]:
        if dist[v] == -1:
            dist[v] = dist[u] + 1
            parent[v] = u
            q.append(v)
if dist[target] == -1:
    print(-1)
else:
    path = []
    cur = target
    while cur != -1:
        path.append(cur)
        cur = parent[cur]
    path.reverse()
    print(dist[target])
    print(*path)

3
1 2 5 7

Ở dữ liệu này, chương trình chọn đường qua 2 và 5. Nếu đổi thứ tự cạnh, một đường ngắn khác có thể được chọn. Số cạnh của mọi đường được chọn vẫn là 3. Không gán lại parent[v] khi gặp lại v, vì cha ban đầu đã thuộc một đường ngắn nhất.

Mảng parent này chỉ giữ một cha cho mỗi đỉnh, nên không liệt kê tất cả đường ngắn nhất. Nếu đề yêu cầu đếm hoặc liệt kê các đường, bạn cần lưu thêm thông tin cho những cạnh cùng dẫn tới khoảng cách tối ưu. Việc đó có yêu cầu bộ nhớ và xử lý riêng; một đường được dựng ở đây không đại diện cho mọi phương án.

Ô trống trong mê cung cũng là đỉnh của đồ thị

Với bảng gồm R hàng và C cột, coi mỗi ô đi được là một đỉnh. Hai ô có cạnh nếu chúng kề trên, dưới, trái hoặc phải. Ta không cần dựng danh sách kề cho toàn bộ bảng: tính bốn ô lân cận ngay khi xử lý một ô.

Trong ví dụ, S là điểm đầu, T là đích, dấu # là tường và dấu . là ô trống. Mỗi bước chỉ di chuyển sang một ô kề cạnh. Đường chéo không được tính.

from collections import deque
grid = ["S..#.", ".#...", "...#T", "....."]
rows, cols = len(grid), len(grid[0])
start = (0, 0)
target = (2, 4)
dist = [[-1] * cols for _ in range(rows)]
dist[start[0]][start[1]] = 0
q = deque([start])
while q:
    r, c = q.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 grid[nr][nc] != '#' and dist[nr][nc] == -1:
            dist[nr][nc] = dist[r][c] + 1
            q.append((nr, nc))
print(dist[target[0]][target[1]])
for row in dist:
    print(*row)

6
0 1 2 -1 6
1 -1 3 4 5
2 3 4 -1 6
3 4 5 6 7

Điều kiện kiểm tra biên phải đứng trước grid[nr][nc]. Python chấp nhận chỉ số âm và có thể âm thầm lấy ô ở cuối bảng. Khi đích bị ngăn bởi tường, khoảng cách giữ nguyên -1. Nếu S và T là cùng một ô theo đề, kết quả là 0.

Mỗi ô được thêm tối đa một lần và xét bốn hướng. Vì thế thời gian là O(RC), bộ nhớ cũng là O(RC). Với bảng 500 × 500, ta xét nhiều nhất một triệu hướng. Không duyệt lại cả bảng cho từng bước lan truyền.

Nhiều nguồn có thể bắt đầu cùng lúc

Giả sử hai trạm cứu hộ ở hai ô khác nhau bắt đầu đi cùng lúc. Ta muốn biết mỗi ô cách trạm gần nhất bao nhiêu bước. Thay vì chạy BFS riêng từ từng trạm, ta đặt tất cả nguồn có khoảng cách 0 và thêm chúng vào cùng hàng đợi trước vòng lặp.

from collections import deque
grid = ["A...#", ".#...", "...#.", "#...B"]
rows, cols = len(grid), len(grid[0])
dist = [[-1] * cols for _ in range(rows)]
q = deque()
for r in range(rows):
    for c in range(cols):
        if grid[r][c] in 'AB':
            dist[r][c] = 0
            q.append((r, c))
while q:
    r, c = q.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 grid[nr][nc] != '#' and dist[nr][nc] == -1:
            dist[nr][nc] = dist[r][c] + 1
            q.append((nr, nc))
for row in dist:
    print(*row)

0 1 2 3 -1
1 -1 3 3 2
2 3 3 -1 1
-1 3 2 1 0

Hãy tưởng tượng thêm một nguồn ảo nối tới mọi nguồn thật. Mọi đường từ nguồn ảo đều có thêm một cạnh giống nhau. Vì vậy, thứ tự ngắn nhất tương đương với việc đặt các nguồn thật ở lớp 0. Khi hai nguồn tới cùng một ô ở cùng thời điểm, khoảng cách vẫn đúng. Thứ tự thêm nguồn chỉ ảnh hưởng nguồn nào được ghi làm cha.

Nếu có k nguồn, chạy riêng k lần có thể tốn O(kRC). Khởi tạo chung và chạy một lần vẫn chỉ tốn O(RC), kể cả bước tìm nguồn trong bảng. Các nguồn trùng nhau trong danh sách đầu vào cần được thêm một lần để giữ mỗi đỉnh trong hàng đợi tối đa một lần.

Trạng thái có thể gồm cả vị trí và điều kiện cần nhớ

Có khi chỉ lưu phòng hiện tại chưa đủ. Giả sử robot phải đến kho sau một số bước chẵn, và được phép đi lại qua phòng hoặc hành lang. Hai lần đến cùng phòng có thể khác nhau: một lần sau số bước chẵn, lần kia sau số bước lẻ. Khả năng đáp ứng điều kiện ở đích vì thế cũng khác nhau.

Ta mở rộng trạng thái (state) thành (u, p). Ở đây u là phòng, còn p bằng 0 nếu số bước đã đi chẵn, bằng 1 nếu lẻ. Đi qua một cạnh đổi p thành 1 - p. Bắt đầu ở (s, 0) vì chưa đi bước nào. Đáp án cần tìm là khoảng cách tới (t, 0).

Xét tam giác có các cạnh 1-2, 2-3, 3-1. Đường một bước từ 1 tới 2 không đạt yêu cầu, nhưng đường 1-3-2 có hai bước. Nếu đánh dấu phòng 2 đã thăm chỉ vì gặp nó sau một bước, ta bỏ lỡ trạng thái đến phòng 2 sau số bước chẵn.

Đoạn sau duyệt đồ thị trạng thái. Mỗi cặp được đánh dấu riêng. Đầu ra gồm khoảng cách chẵn và lẻ của từng phòng, với -1 nếu trạng thái đó không tới được.

from collections import deque
g = [[], [2, 3], [1, 3], [1, 2]]
dist = [[-1, -1] for _ in range(4)]
dist[1][0] = 0
q = deque([(1, 0)])
while q:
    u, parity = q.popleft()
    for v in g[u]:
        next_parity = 1 - parity
        if dist[v][next_parity] == -1:
            dist[v][next_parity] = dist[u][parity] + 1
            q.append((v, next_parity))
for u in range(1, 4):
    print(u, *dist[u])

1 0 3
2 2 1
3 2 1

Mỗi bước của hành trình ban đầu tương ứng đúng một cạnh trong đồ thị trạng thái. Ngược lại, mọi bước trong đồ thị trạng thái đều là một hành lang hợp lệ. BFS trên đồ thị mới tìm ít bước nhất đến trạng thái cần tìm. Nó có tối đa 2n trạng thái và xét tối đa 4m lượt kề với đồ thị vô hướng. Do đó thời gian vẫn là O(n + m) và bộ nhớ là O(n + m).

Điều quan trọng là đề cho phép đi lại. Nếu đề yêu cầu đường đơn không lặp đỉnh, không thể mặc nhiên áp dụng mô hình này để giải cùng bài toán.

Khi có chìa khóa, dùng mặt nạ bit (bitmask, xem Bài 34) để nhớ các chìa đã nhặt. Chìa a tương ứng bit 0, chìa b tương ứng bit 1. Chẳng hạn, trên hàng SaA.T, đi vào a thì bật bit 0. Cửa A chỉ cho qua khi bit 0 đã bật. Hai trạng thái ở cùng ô nhưng khác mặt nạ cần được xét riêng.

hall = 'SaA.T'
mask = 0
for col, cell in enumerate(hall):
    if 'A' <= cell <= 'F' and not (mask & (1 << (ord(cell) - ord('A')))):
        print('Cửa đóng tại cột', col)
        break
    if 'a' <= cell <= 'f':
        mask |= 1 << (ord(cell) - ord('a'))
    print('cột', col, 'mặt nạ', format(mask, '06b'))

cột 0 mặt nạ 000000
cột 1 mặt nạ 000001
cột 2 mặt nạ 000001
cột 3 mặt nạ 000001
cột 4 mặt nạ 000001

Với sáu chìa khác nhau, mỗi ô có tối đa 2^6 = 64 mặt nạ. Bảng 50 × 50 có tối đa 160.000 trạng thái. Mỗi trạng thái xét bốn hướng, nên BFS tốn O(RC · 64) thời gian và bộ nhớ. Số trạng thái cần lưu có thể tăng theo số chìa, vì vậy hãy tính giới hạn trước khi cài đặt.

Trọng số quyết định BFS thường có phù hợp hay không

BFS thường tối thiểu hóa số cạnh. Nếu mỗi cạnh có cùng chi phí dương, đường ít cạnh nhất cũng có tổng chi phí nhỏ nhất. Nếu chi phí khác nhau, số cạnh ít hơn không đủ để kết luận.

direct_cost = 10
two_edge_cost = 2 + 3
print('trực tiếp:', 1, 'cạnh, chi phí', direct_cost)
print('qua một đỉnh:', 2, 'cạnh, chi phí', two_edge_cost)

trực tiếp: 1 cạnh, chi phí 10
qua một đỉnh: 2 cạnh, chi phí 5

Ở đây BFS theo số cạnh chọn đường trực tiếp, dù tổng chi phí của nó là 10. Đường hai cạnh có chi phí 5. Với trọng số không âm khác nhau, xem thuật toán Dijkstra ở Bài 40. Với bài chỉ hỏi có tới được không, DFS ở Bài 37 cũng phù hợp, nhưng thứ tự DFS không bảo đảm đường ít cạnh nhất.

Lỗi thường gặp

Tóm tắt

BFS dùng deque để xử lý theo lớp khoảng cách. Đánh dấu khi thêm vào hàng đợi để mỗi đỉnh được xử lý tối đa một lần. Mảng parent giữ một đường ngắn nhất. Trên bảng, sinh hàng xóm theo hướng hợp lệ. Với nhiều nguồn, đưa tất cả vào hàng đợi ở khoảng cách 0.

Kiểm tra nhanh

Đọc thêm

• Breadth First Search — CP-Algorithms
• collections.deque — Python