Duyệt theo chiều sâu (DFS)

Bạn sẽ học được gì

DFS — Depth-First Search (duyệt theo chiều sâu) chọn một nhánh và lao thật sâu tới khi cụt đường, rồi mới quay lui thử nhánh khác. Nó tự nhiên hợp với đệ quy (hoặc một stack thủ công), và là nền cho nhiều bài: thành phần liên thông, phát hiện chu trình, sắp xếp tô-pô.

1. Trực quan: đi trong mê cung

Tưởng tượng bạn lạc trong mê cung và áp dụng quy tắc "bám tường trái": cứ đi tới khi cụt đường, rồi lùi lại ngã rẽ gần nhất chưa thử và đi tiếp. Bạn đào sâu một hướng tới tận cùng trước khi quay lại — đó chính là DFS.

   Bat dau tu A (uu tien con trai):

        A
       / \
      B   C
     / \   \
    D   E   F

   Thu tu DFS: A -> B -> D (cut, lui)
               -> E (cut, lui ve A)
               -> C -> F
   => A B D E C F

So với BFS loang đều ra mọi hướng, DFS giống một mũi khoan: chọc sâu xuống một nhánh trước.

2. Cơ chế: đệ quy hoặc stack

DFS có hai cách cài đặt tương đương:

Cách	Cấu trúc	Ghi chú
Đệ quy	Call stack ngầm	Ngắn gọn, dễ đọc
Vòng lặp	Stack thủ công	Tránh tràn stack khi đồ thị rất sâu

Cả hai đều cần một tập visited để không thăm lại đỉnh cũ (nếu không sẽ lặp vô hạn trên chu trình).

3. Chạy debug: DFS đệ quy

🐞 DFS đệ quy từ ABước 1/8

1g = {"A": ["B", "C"], "B": ["D"], "C": [], "D": []}
2seen = set(); order = []
3def dfs(u):
4  seen.add(u)
5  order.append(u)
6  for v in g[u]:
7      if v not in seen:
8          dfs(v)
9dfs("A")

Biến tại bước này

stack	dfs(A)
seen	{}
order	[]

👉 Gọi dfs(A) — bắt đầu.

4. Code chạy được

Hai bản: đệ quy và vòng lặp (stack thủ công). Kết quả cùng "tập đỉnh", chỉ khác thứ tự chi tiết.

Đang tải trình chạy code…

5. Ứng dụng: liên thông và chu trình

DFS là công cụ đa năng. Hai ứng dụng kinh điển:

Đếm thành phần liên thông: gọi DFS từ mỗi đỉnh chưa thăm; mỗi lần khởi động một DFS mới là một thành phần mới.

Phát hiện chu trình: với đồ thị có hướng, nếu DFS gặp lại một đỉnh đang nằm trên đường đệ quy hiện tại (trạng thái "đang xử lý") thì có chu trình.

Đang tải trình chạy code…

6. Phân tích

Khía cạnh	Giá trị
Thời gian	O(V + E) — như BFS
Bộ nhớ	O(V) — độ sâu đệ quy / stack

Bẫy thường gặp:

• Đồ thị rất sâu → đệ quy có thể tràn stack; khi đó dùng bản vòng lặp.
• Quên visited → lặp vô hạn trên chu trình.
• Lẫn BFS và DFS: DFS không đảm bảo đường ngắn nhất.

7. Mẫu nhận diện

• "Khám phá toàn bộ", "đi hết một nhánh rồi quay lui", "quay lui (backtracking)" → DFS.
• "Thành phần liên thông", "tô màu vùng", "phát hiện chu trình" → DFS.
• "Tìm một đường đi bất kỳ" (không cần ngắn nhất) → DFS thường gọn hơn.

8. 🎮 Trò chơi: Hiểu DFS

🎮 Hiểu DFSCâu 1/4· Điểm 0· 🔥 0

DFS lao sâu một nhánh rồi quay lui. Cài bằng đệ quy hoặc stack LIFO.

DFS có đảm bảo tìm đường ngắn nhất (ít cạnh) không?

9. Quiz kiểm tra nhanh

📝 Quiz kiểm tra nhanh

1. Độ phức tạp thời gian của DFS (danh sách kề) là?

2. Rủi ro của DFS đệ quy trên đồ thị rất sâu là gì?

3. Để phát hiện chu trình trong đồ thị có hướng bằng DFS, ta theo dõi?

10. Hoàn thành

…

☑️ Tiếp theo: 3.3.3 — Sắp xếp tô-pô (xếp thứ tự công việc trên đồ thị có hướng không chu trình).