Tìm kiếm theo chiều rộng (BFS) trong Python
Duyệt đồ thị theo từng tầng bằng hàng đợi, và tìm đường ngắn nhất trong đồ thị không có trọng số.
- Biểu diễn đồ thị bằng dict chứa list
- Dùng deque làm hàng đợi
- Theo dõi các đỉnh đã thăm
Atầng 0Btầng 1Dtầng 2
Ctầng 1Etầng 2
Đỉnh gần nhất được thăm trước
Vấn đề
Cần bao nhiêu bước để đi từ người này tới người kia trong một mạng xã hội, hay từ một ô của mê cung tới lối ra? Tìm kiếm theo chiều rộng (breadth-first search) lan ra theo từng vòng khoảng cách, nên lần đầu chạm tới một nút (node), nó đã đi theo một đường ngắn nhất tới nút đó.
Hình dung đời thường
Tìm kiếm theo chiều rộng giống những gợn sóng trên mặt hồ. Thả một hòn đá ở điểm xuất phát, gợn sóng chạm tới mọi thứ cách một bước trước, rồi tới mọi thứ cách hai bước, cứ thế. Sóng chỉ chạm tới chỗ xa hơn sau khi đã chạm hết mọi chỗ gần hơn.
queue = deque(["A"])🪨 Thả hòn đá ở Anode = queue.popleft()🌊 Lấy nút tiếp theo theo thứ tự khoảng cáchif neighbor not in visited:🔎 Nút này đã được chạm tới chưa?queue.append(neighbor)➕ Thêm nó vào vòng sóng tiếp theoTìm kiếm theo chiều rộng (BFS) duyệt đồ thị (graph) theo từng tầng tính từ nút xuất phát, dùng hàng đợi, nên tìm được đường đi ngắn nhất trên đồ thị không có trọng số.
Những điểm quan trọng
queuegiữ các nút đang chờ được khám phá, nút cũ nhất trước.visitedghi lại các nút đã tìm thấy, nên không nút nào bị thêm hai lần và chu trình không làm lặp vô hạn.node = queue.popleft()lấy nút tiếp theo; các hàng xóm chưa thăm của nó vào cuối hàng đợi.ordercho thấy A, rồi hai hàng xóm B và C, rồi D và E ở tầng xa hơn.
Khi nào nên sử dụng?
- Đường đi ngắn nhất trên đồ thị không trọng số, lưới và mê cung.
- Số bước quen biết giữa hai người trong mạng xã hội.
- Trình thu thập web (crawler) và tìm mọi thứ có thể tới được từ một điểm.
Khi nào chưa cần
- Các cạnh có chi phí khác nhau, như khoảng cách đường đi: dùng thuật toán Dijkstra.
- Cần đi hết một nhánh trước các nhánh khác, như khi quay lui: dùng tìm kiếm theo chiều sâu.
Mô phỏng Tìm kiếm theo chiều rộng (BFS) trong Python
O(V + E)Nhấn Phát hoặc Từng bước để theo dõi từng phép so sánh và thay đổi dữ liệu.
Code ví dụ
from collections import deque
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
queue = deque(["A"])
visited = {"A"}
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
print(order)
Kết quả khi chạy
['A', 'B', 'C', 'D', 'E']
Giải thích code
Hàng đợi queue chứa các đỉnh đang chờ được thăm, và các đỉnh được lấy ra theo đúng thứ tự đã thêm vào. Set visited ghi nhớ những đỉnh đã gặp để không thăm lại một đỉnh nhiều lần khi đồ thị có chu trình. Thứ tự duyệt là A, B, C, D, E, và độ phức tạp là O(V + E), với V là số đỉnh và E là số cạnh.
Thay đổi giá trị và chạy chương trình bằng trình chạy Python online của CodeUtility mà không cần cài Python.
Bài tập mở rộng
Hãy thử chỉnh sửa code theo các gợi ý dưới đây. Tự thay đổi và quan sát kết quả sẽ giúp bạn hiểu bài sâu hơn nhiều so với chỉ đọc code.
- Thử với danh sách rỗng, danh sách chỉ có một phần tử hoặc có giá trị trùng lặp.
- In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
- Đo thời gian chạy với 100, 1.000 và 10.000 phần tử, rồi so sánh với một cách giải khác.
Lỗi hay gặp
Đánh dấu đã thăm quá muộn
Nếu chỉ đánh dấu khi lấy nút ra khỏi hàng đợi, một nút có thể bị thêm vào nhiều lần.
node = queue.popleft()
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
Bạn học xong bài này chưa?
Đánh dấu đã học để theo dõi tiến độ của bạn.
Luyện tập với thử thách
Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.
- Can We Split Into Two Teams? Decide whether people can be assigned to two teams so that each listed pair is on opposite teams. Trung bình
- Đường kính của cây Một cây là một đồ thị vô hướng liên thông không có chu trình. Trung bình
- Count Islands Count groups of connected land cells in a grid. Trung bình