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.
- DFS bằng đệ quy
- Tập visited
- Thứ tự DFS khác BFS thế nào
Athứ 1Bthứ 2Dthứ 3
Cthứ 4Ethứ 5
Đ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.
visited.add(node)🧵 Đánh dấu đường hầm này là đã đifor neighbor in graph[node]:🔀 Xem từng đường hầm dẫn ra từ đâydepth_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ạiTì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
visited.add(node)đánh dấu nút, nên chu trình không gây đệ quy vô hạn.for neighbor in graph[node]:lần lượt xem từng hàng xóm.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.- 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ụ
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"))
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.
- 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
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.
def depth_first(node, visited=set()):
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.
- Count Islands Count groups of connected land cells in a grid. Trung bình
- Strongly Connected Components Count groups of nodes that can all reach each other. Khó
- Longest Path in a DAG Find the heaviest path in a task dependency graph. Khó