Về Chương 5
Định Vị Thành Phố BFS
ĐỊNH VỊ THÀNH PHỐ
BFS — BREADTH-FIRST SEARCH
Duyệt theo chiều rộng với hàng đợi Queue
Chưa thăm
Trong Queue
Đang thăm
Đã thăm
Đỉnh xuất phát:
1
2
3
4
5
6
Bắt đầu BFS
1
2
3
4
5
6
🔄 Hàng Đợi (Queue)
FIFO
OUT
Queue rỗng
IN
✅ Thứ Tự Thăm (Visited)
⚡ Đặc Tính BFS
Chiến lược
Mở rộng đồng tâm (từng layer một)
Ứng dụng
Tìm đường đi ngắn nhất (chưa có trọng số)
📋 Hành Vi Thuật Toán
BFS(G, start):
Q ← Queue(); Q.enqueue(start)
visited = {start}
while Q không rỗng:
v ← Q.dequeue()
thăm_đỉnh(v)
for w in lân_cận(v):
if w chưa thăm → Q.enqueue(w)
trả về visited