Thuật toán Python

Tìm kiếm theo chiều sâu (DFS) trong Python

Đi theo một nhánh sâu nhất có thể rồi mới quay lại. Viết DFS bằng đệ quy chỉ trong vài dòng.

  • Trung cấp
  • Đọc trong 2 phút
  • 1 ví dụ chạy được
Bạn sẽ học được gì
  • DFS bằng đệ quy
  • Tập visited
  • Thứ tự DFS khác BFS thế nào
DFS từ A
  • Athứ 1
    • Bthứ 2
      • Dthứ 3
    • Cthứ 4
      • Ethứ 5
Thứ tự thăm: A, B, D, C, E.

Đi sâu, rồi quay lại

Vấn đề

Tìm lối ra khỏi mê cung, kiểm tra đồ thị có chu trình không hay sắp xếp các công việc phụ thuộc lẫn nhau đều cần đi theo một đường càng xa càng tốt trước khi thử đường khác. Đó là tìm kiếm theo chiều sâu (depth-first search).

Hình dung đời thường

Tìm kiếm theo chiều sâu giống khám phá hang động với một cuộn dây. Bạn đi theo một đường hầm sâu hết mức. Gặp ngõ cụt thì lần theo sợi dây quay về ngã rẽ gần nhất và thử đường hầm tiếp theo. Bạn đánh dấu những đường đã đi để không bao giờ đi lại.

Từ việc khám phá hang động đến code
visited.add(node)🧵 Đánh dấu đường hầm này là đã đi
for neighbor in graph[node]:🔀 Xem từng đường hầm dẫn ra từ đây
depth_first(neighbor, visited)⬇️ Đi sâu vào đường đầu tiên chưa khám phá
return order↩️ Ngõ cụt: lần theo sợi dây quay lại
Đi sâu trước, rồi quay lui và thử nhánh tiếp theo.
Định nghĩa ngắn gọn

Tìm kiếm theo chiều sâu (DFS) duyệt đồ thị bằng cách đi theo một nhánh sâu nhất có thể rồi mới quay lui, thường dùng đệ quy hoặc stack.

Những điểm quan trọng

  1. visited.add(node) đánh dấu nút, nên chu trình không gây đệ quy vô hạn.
  2. for neighbor in graph[node]: lần lượt xem từng hàng xóm.
  3. order.extend(depth_first(neighbor, visited)) khám phá hết nhánh bên dưới một hàng xóm trước khi sang hàng xóm tiếp theo.
  4. Kết quả thăm D trước C, vì nhánh của B được đi hết trước.

Khi nào nên sử dụng?

  • Tìm một đường đi bất kỳ, giải mê cung và câu đố bằng quay lui.
  • Phát hiện chu trình và sắp xếp công việc có phụ thuộc (sắp xếp tô pô).
  • Khám phá mọi phần liên thông của đồ thị.

Khi nào chưa cần

  • Cần đường đi ngắn nhất: DFS có thể tìm ra đường dài trước; hãy dùng BFS.
  • Đồ thị rất sâu: đệ quy có thể chạm giới hạn của Python; dùng stack tự quản lý.

Mô phỏng Tìm kiếm theo chiều sâu (DFS) 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
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}

def depth_first(node, visited=None):
    visited = visited or set()
    visited.add(node)
    order = [node]
    for neighbor in graph[node]:
        if neighbor not in visited:
            order.extend(depth_first(neighbor, visited))
    return order

print(depth_first("A"))
Lấy nút Run cho ví dụ này

Kết quả khi chạy

['A', 'B', 'D', 'C', 'E']

Giải thích code

Set visited ghi nhớ các đỉnh đã thăm để tránh xử lý lặp lại và tránh vòng lặp vô hạn khi đồ thị có chu trình. Mỗi lời gọi đệ quy đi sâu vào một đỉnh kề chưa được thăm, nên chương trình thăm A, B, D rồi mới quay lại thăm C, E. Ngăn xếp lời gọi hàm đóng vai trò như stack của thuật toán, và độ phức tạp là O(V + E).

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

Dùng đối số mặc định thay đổi được

visited=set() sẽ bị dùng chung giữa các lần gọi riêng biệt.

Sai
def depth_first(node, visited=set()):
Cách sửa
def depth_first(node, visited=None):
    visited = visited or set()

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