Mức là số cạnh ít nhất từ s
BFS (Breadth First Search) dùng hàng đợi FIFO: xử lí các đỉnh gần s trước, rồi lan sang các mức xa hơn. Với đồ thị không trọng số, mức của v là số cạnh ít nhất trên đường từ s đến v.
Từ 0 trong mẫu: mức 0 có {0}, mức 1 có {1,2}, mức 2 có {3,4}, mức 3 có {5}; 6 không tới được. Thứ tự trong cùng mức có thể đổi theo thứ tự Adj nhưng các khoảng cách không đổi.
Giữ FIFO bằng chỉ số đọc đầu hàng
Q là list; head chỉ phần tử kế tiếp cần lấy. Các phần tử trước head đã được xử lí, không cần xóa khỏi list. append thêm cuối nên vẫn FIFO và không phải dồn dữ liệu như pop(0).
Đánh dấu khi đưa đỉnh vào Q như cách thực hành tìm đường trong SGK. Điều này giúp mỗi đỉnh vào hàng một lần. dist[s]=0; dist[v]=−1 nghĩa là chưa tới được. prev[v] ghi đỉnh đã phát hiện v.
```python
def bfs(Adj, s):
check_vertex(Adj, s)
n = len(Adj)
seen = [False]*n
dist = [-1]*n
prev = [None]*n
Q = [s]
head = 0
seen[s] = True
dist[s] = 0
order = []
while head < len(Q):
u = Q[head]
head += 1
order.append(u)
for v in Adj[u]:
if not seen[v]:
seen[v] = True
dist[v] = dist[u] + 1
prev[v] = u
Q.append(v)
return order, dist, prev
```
Theo dõi phần hàng đợi còn chờ
|Sau khi lấy và xử lí|Phần Q còn chờ từ head|
|---|---|
|0|[1,2]|
|1|[2,3,4]|
|2|[3,4]|
|3|[4,5]|
|4|[5]|
|5|[]|
Thứ tự order là [0,1,2,3,4,5]; dist là [0,1,1,2,2,3,−1]. Khi xử lí 2, đỉnh 4 đã được đánh dấu lúc đưa vào hàng từ 1, nên không thêm lại và không đổi prev[4].
Với danh sách kề và cách hàng đợi này, duyệt toàn vùng tới được có chi phí nằm trong O(V+E). Nếu dùng list.pop(0), phải tính thêm chi phí dồn phần tử. Kết luận đường ít cạnh nhất chưa đồng nghĩa đường ngắn nhất theo km hoặc nhanh nhất theo phút nếu các cạnh có độ dài, thời gian khác nhau.
Bài luyện
Khoảng cách ít cạnh nhất từ 0 đến 5 trong mẫu là bao nhiêu?
Không có cạnh trực tiếp 0–5.
Đúng. BFS đặt 5 ở mức 3.
Có đường dài hơn nhưng đó không phải khoảng cách nhỏ nhất.
Hai đỉnh khác nhau không có đường độ dài 0.
Lời giải
5 được phát hiện từ 3 ở mức 2 nên dist[5]=3. Đường 0→1→3→5 có ba cạnh; không có đường chỉ một hoặc hai cạnh trong đồ thị mẫu.
Bài luyện
Vì sao đánh dấu 4 ngay lúc đưa vào hàng từ 1?
Đúng. Đỉnh đã được phát hiện chỉ cần vào hàng một lần.
Cạnh vẫn giữ nguyên.
4 được thêm sau và phải chờ theo FIFO.
Hàng đợi vẫn FIFO.
Lời giải
Khi 1 phát hiện 4, nó đặt seen[4]=True, prev[4]=1 và thêm 4. Tới lượt 2 gặp 4, seen đã True nên bỏ qua, giữ đường phát hiện đầu và tránh trùng hàng.
Bài luyện
BFS trên dữ liệu này bảo đảm loại đường nào?
Không có trọng số thời gian để kết luận.
Không có trọng số độ dài để kết luận.
DFS có thể theo nhánh dài hơn.
Đúng. Các cạnh được tính như nhau.
Lời giải
BFS duyệt theo số cạnh từ nguồn nên lần phát hiện đầu tiên cho mức nhỏ nhất. Muốn tối ưu km hoặc phút với các cạnh có trọng số khác nhau cần mô hình và thuật toán phù hợp khác.
Đang học