DFS, ngăn xếp và so sánh với BFS
Hiểu DFS đào sâu bằng ngăn xếp và đệ quy, truy vết quay lui, và bảng so sánh toàn diện với BFS.
Trung bìnhThuật toán ~60 phút
Ôn lại trước khi học
Giới thiệu
Bài này học DFS đào sâu rồi quay lui. Thuật toán này giúp giải mê cung và sắp lịch.
Kiến thức cần nhớ
DFS đào sâu
- Dùng ngăn xếp LIFO: vào sau ra trước.
- Đâm sâu một nhánh tới lá rồi mới quay lui.
- Thời gian tuyến tính, nhớ theo đường sâu nhất.
- Ví dụ đời thường: đi mê cung tới ngõ cụt rồi quay lại.
Đệ quy và cờ đã thăm
- Đệ quy: đánh dấu rồi gọi sang lân cận chưa thăm.
- Quên cờ đã thăm thì hai nút trỏ nhau gây treo vô hạn.
- Stack tường minh tương đương đệ quy nhưng không sợ tràn.
- Ví dụ đời thường: đánh dấu phòng đã vào để khỏi lặp.
# DFS đệ quy gọn nhất
def dfs(graph, u, tham):
tham.add(u) # đánh dấu đã thăm
for v in graph[u]: # xét từng lân cận
if v not in tham: # chưa thăm mới đi
dfs(graph, v, tham) # đào sâu tiếp
BFS so với DFS
- BFS dùng hàng đợi, lan lớp; DFS dùng stack, đâm nhánh.
- BFS cho đường ngắn nhất, DFS thì không đảm bảo.
- BFS nhớ lớp rộng nhất, DFS nhớ nhánh sâu nhất.
- Ví dụ đời thường: BFS như sóng lan, DFS như khoan sâu.
| Tiêu chí | BFS | DFS |
|---|---|---|
| Cấu trúc | Hàng đợi FIFO | Ngăn xếp LIFO |
| Thứ tự | Lớp gần trước | Nhánh sâu trước |
| Thắng ở | Đường ngắn nhất | Topo, mê cung |
| Thời gian |
Ví dụ
- Input: mạng 6 người, DFS từ Amin -> Output: Amin, Wasim, Imran, Faras rồi quay lui.
- Câu này cho thấy đào sâu khác hẳn lan lớp.
- Input: tam giác 3 nút mà quên tập đã thăm -> Output: gọi qua lại vô hạn.
- Câu này cho thấy cờ đã thăm là sống còn.
💻 Bài tập
Ngôn ngữ: C++. Dùng lại Graph ngày 40. Nộp vào day-041/.
Bài 1: DFS hai cách
| Hàm | Yêu cầu |
|---|---|
std::vector<int> dfsRecursive(const Graph&, int s) | Thứ tự thăm, lân cận xét theo thứ tự tăng dần |
std::vector<int> dfsIterative(const Graph&, int s) | Stack tường minh, cùng thứ tự với bản đệ quy |
std::vector<int> discovery, finish | Ghi thời điểm vào và ra mỗi đỉnh (bản đệ quy) |
Cạnh vô hướng: 0-1, 0-2, 1-3, 2-3, 3-4
dfsRecursive(0) -> [0,1,3,2,4]
dfsIterative(0) -> [0,1,3,2,4]
Đường thẳng 10^6 đỉnh: dfsRecursive có thể tràn stack, dfsIterative chạy bình thường
Để bản stack cùng thứ tự với đệ quy, đẩy lân cận vào stack theo thứ tự ngược và đánh dấu thăm lúc lấy ra, không phải lúc đẩy vào.
Bài 2: Ứng dụng DFS
| Hàm | Yêu cầu |
|---|---|
bool hasCycleUndirected(const Graph&) | Gặp đỉnh đã thăm mà không phải cha thì có chu trình |
bool hasCycleDirected(const Graph&) | 3 màu: trắng, xám (đang trên stack), đen |
std::vector<int> topoSort(const Graph&) | Đồ thị có hướng không chu trình, sắp theo thời điểm ra giảm dần. Có chu trình thì ném lỗi |
Môn học: 0->1, 0->2, 1->3, 2->3 -> topoSort hợp lệ, 0 đứng đầu, 3 đứng cuối
Thêm 3->0 -> hasCycleDirected = true, topoSort ném lỗi
Bài 3: So sánh BFS và DFS (nâng cao)
- Giải mê cung ngày 40 bằng DFS. So độ dài đường DFS tìm được với BFS.
- Sinh cây nhị phân đầy đủ độ sâu 20 và đồ thị đường thẳng đỉnh. Đo bộ nhớ lớn nhất của hàng đợi BFS và stack DFS (số phần tử tối đa).
- Liệt kê mọi đường đi từ
StớiEtrong lưới không có tường bằng DFS quay lui. In số đường.
Lưới 4x4, chỉ đi phải hoặc xuống -> 20 đường
✅ Tiêu chí hoàn thành
- 2 bản DFS cho cùng thứ tự thăm trên 100 đồ thị ngẫu nhiên.
-
topoSortpass kiểm tra: mọi cạnhu->vcóuđứng trướcv. - Bảng bộ nhớ BFS và DFS có số thật.
- Nêu được khi nào chọn BFS, khi nào chọn DFS.
❓ Câu hỏi ôn tập
- DFS dùng cấu trúc gì để đào sâu?
- Vì sao quên cờ đã thăm gây treo?
- BFS và DFS khác nhau ở thứ tự nào?
- Bài nào nên dùng DFS thay vì BFS?
🌕 Bạn đã hoàn thành ngày 41. Làm hết bài tập phía trên rồi sang ngày tiếp theo.