Thuật toán Python

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ố.

  • Trung cấp
  • Đọc trong 3 phút
  • 1 ví dụ chạy được
Bạn sẽ học được gì
  • 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
BFS từ A
  • Atầng 0
    • Btầng 1
      • Dtầng 2
    • Ctầng 1
      • Etầng 2
Thứ tự thăm: A, B, C, D, E.

Đỉ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.

Từ gợn sóng trên mặt hồ đến code
queue = deque(["A"])🪨 Thả hòn đá ở A
node = queue.popleft()🌊 Lấy nút tiếp theo theo thứ tự khoảng cách
if 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 theo
Nút gần trước, dùng một hàng đợi.
Định nghĩa ngắn gọn

Tì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

  1. queue giữ các nút đang chờ được khám phá, nút cũ nhất trước.
  2. visited ghi 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.
  3. 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.
  4. order cho 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ụ

Chạy code →
main.py
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)
Lấy nút Run cho ví dụ này

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.

  1. 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.
  2. In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
  3. Đ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.
Chạy trong trình biên dịch Python →

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.

Sai
node = queue.popleft()
visited.add(node)
for neighbor in graph[node]:
    if neighbor not in visited:
        queue.append(neighbor)
Cách sửa
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.

Tất cả thử thách