Tìm kiếm theo chiều sâu — Depth-First Search
Tìm kiếm theo chiều sâu (DFS) đi sâu hết một nhánh rồi mới quay lại nhánh khác, thường cài bằng đệ quy hoặc một ngăn xếp tường minh.
DFS hợp với các bài cần khám phá trọn vẹn cấu trúc: đếm thành phần liên thông, phát hiện chu trình, sắp xếp tô-pô. Bộ nhớ chỉ tỉ lệ với độ sâu, nhưng phải đánh dấu "đã thăm" để không đi lại vô tận.
Như đi mê cung — chui sâu vào một ngõ đến cùng, đụng tường mới lùi lại.
- So với BFS: BFS rải tin nhắn toàn dân theo từng vòng, DFS đi sâu một ngõ đến cùng rồi mới quay lại.
- Phù hợp khi cần đi hết toàn bộ nhánh: liệt kê đường đi, kiểm tra chu trình, tìm thành phần liên thông.
Dấu hiệu nhận biết
Gặp những từ khoá này trong đề → nghĩ ngay đến Tìm kiếm theo chiều sâu
| Từ khoá trong đề | Tại sao gợi đến chủ đề này |
|---|---|
| liệt kê mọi đường | DFS đi hết từng nhánh |
| phát hiện chu trình | DFS + visited + ngăn xếp đệ quy |
| thành phần liên thông | Đếm số component bằng DFS |
| topological sort | DFS post-order trên DAG |
Khi nào dùng
3 tình huống điển hình cần nghĩ đến chủ đề này
Cần duyệt toàn bộ đồ thị / cây: liệt kê mọi đỉnh, mọi cạnh
Bài toán có đệ quy tự nhiên: chia để trị, quay lui, topological sort
Kiểm tra chu trình, tìm thành phần liên thông, bài toán "flood fill"
Khi nào KHÔNG dùng
3 tình huống chủ đề này không phù hợp — biết để tránh overuse
Cần shortest path trong unweighted graph: BFS đảm bảo shortest, DFS không
Đồ thị rất sâu (depth > 10^4): recursion gây stack overflow → dùng iterative DFS với stack tường minh
Cần xử lý theo từng tầng (level-order): BFS đúng bản chất hơn
Hình minh hoạ
Chỉnh dữ liệu rồi bấm Phát để xem từng bước.
// DFS đệ quy — đi sâu hết một nhánhfunction dfs(node, visited) {if (visited.has(node)) returnvisited.add(node)for (const nb of adj[node]) {dfs(nb, visited)}}
Code mẫu
Hầu hết bài cùng chủ đề dùng chung mẫu này — copy rồi điền phần logic riêng của bài.
function dfs(node: Node, graph: Graph, visited = new Set<Node>()): R {
if (visited.has(node)) return
visited.add(node)
// Pre-order: xử lý node trước khi đệ quy
visit(node)
for (const next of graph.neighbors(node)) {
dfs(next, graph, visited)
}
// Post-order: xử lý khi quay lui (nếu cần)
// postVisit(node)
}Recap
Tổng hợp nhanh — đọc lại trước phỏng vấn
Điểm chính
DFS dùng ngăn xếp (đệ quy dùng call stack, lặp dùng stack tường minh)
Đánh dấu visited trước khi gọi đệ quy cho con → tránh đi lại
DFS không đảm bảo đường ngắn nhất trên đồ thị có trọng số — dùng BFS hoặc Dijkstra
Pre-order, in-order, post-order trên cây nhị phân đều là biến thể của DFS
Lỗi thường gặp
Quên đánh dấu visited → vòng lặp vô hạn trên đồ thị có chu trình
Nhầm DFS với BFS khi cần đường ngắn nhất (DFS không đảm bảo ngắn nhất)
Stack overflow khi đệ quy sâu trên đồ thị lớn — cân nhắc DFS dạng lặp
Độ phức tạp
Time O(V + E), Space O(V) cho stack — V là số đỉnh, E là số cạnhBài luyện theo chủ đề này
Phân theo độ khó — luyện tuần tự cho chắc tay