DFS — Giải thích thuật toán tìm kiếm theo chiều sâu

Tìm kiếm theo chiều sâu, hay DFS, là một thuật toán để khám phá cây hoặc đồ thị bằng cách đi theo một nhánh xa nhất có thể trước khi quay lui. Nói đơn giản: DFS cứ đi sâu cho đến khi không thể đi tiếp, rồi quay lại điểm gần nhất còn nhánh khác để đi.

Nếu chỉ nhớ một ý, hãy nhớ điều này: DFS nghĩa là "đi sâu, rồi quay lui".

DFS Làm Gì

DFS có thể dùng trên cây và cả đồ thị tổng quát. Bắt đầu từ một đỉnh, nó liên tục di chuyển sang một đỉnh kề chưa được thăm. Khi đến một đỉnh không còn đỉnh kề nào chưa được thăm, nó quay lui về đỉnh trước đó và tiếp tục từ đó.

Chính hành vi quay lui này là đặc trưng của DFS. Trong cách cài đặt đệ quy, ngăn xếp lời gọi hàm xử lý việc đó một cách tự động. Trong cách cài đặt lặp, một ngăn xếp tường minh sẽ đóng vai trò tương tự.

Vì Sao Thứ Tự DFS Có Thể Thay Đổi

DFS không tạo ra một thứ tự thăm duy nhất cho mọi trường hợp. Thứ tự chính xác phụ thuộc vào thứ tự mà các đỉnh kề được xét.

Ví dụ, nếu một đỉnh có hai đỉnh kề là $B$ và $C$, việc thăm $B$ trước có thể cho ra thứ tự DFS khác với việc thăm $C$ trước. Trong cả hai trường hợp, đó vẫn là DFS vì quy tắc vẫn giống nhau: luôn đi sâu trước khi khám phá một nhánh cùng cấp khác.

Ví Dụ DFS Trên Một Đồ Thị Nhỏ

Giả sử đồ thị có các kết nối sau:

• $A$ nối với $B$ và $C$
• $B$ nối với $D$ và $E$
• $C$ nối với $F$

Giả sử ta luôn xét các đỉnh kề từ trái sang phải và bắt đầu tại $A$.

DFS diễn ra như sau:

1. Thăm $A$
2. Đi tới $B$
3. Đi tới $D$
4. $D$ không còn đỉnh kề nào chưa được thăm, nên quay lui về $B$
5. Từ $B$, đi tới $E$
6. $E$ đã xong, nên quay lui về $B$, rồi về $A$
7. Từ $A$, đi tới $C$
8. Từ $C$, đi tới $F$

Vậy một thứ tự thăm DFS hợp lệ là:

$$A, B, D, E, C, F$$

Ý chính là DFS hoàn tất phía $A \to B$ trước khi bắt đầu phía $A \to C$. Nếu bạn thay đổi thứ tự xét đỉnh kề, thứ tự thăm cũng có thể thay đổi.

Vì Sao Quay Lui Dùng Ngăn Xếp

DFS luôn cần một cách để nhớ phải quay lại đâu sau khi chạm vào ngõ cụt. Đó là lý do ngăn xếp xuất hiện rất tự nhiên trong DFS.

Trong DFS đệ quy, mỗi lời gọi hàm sẽ chờ trong khi quá trình tìm kiếm đi sâu hơn, và chương trình quay trở lại theo thứ tự ngược khi quay lui. Trong DFS lặp, bạn đưa các đỉnh vào ngăn xếp và lấy chúng ra khi đến lúc tiếp tục từ điểm chưa hoàn tất gần nhất.

Độ Phức Tạp Thời Gian Và Bộ Nhớ Của DFS

Nếu đồ thị được lưu dưới dạng danh sách kề và mỗi đỉnh được đánh dấu ngay lần đầu được thăm, DFS chạy trong thời gian

$$O(V + E)$$

cho phần đồ thị có thể đi tới được, trong đó $V$ là số đỉnh và $E$ là số cạnh.

Bộ nhớ phụ thêm thường là

$$O(V)$$

vì cấu trúc đánh dấu đã thăm và ngăn xếp đệ quy hoặc ngăn xếp tường minh đều có thể tăng theo số lượng đỉnh.

Những Lỗi DFS Thường Gặp

Quên Đánh Dấu Các Đỉnh Đã Thăm

Trong đồ thị tổng quát, quên kiểm tra đã thăm có thể khiến DFS lặp mãi trong một chu trình. Ngay cả trong cây được lưu như một đồ thị vô hướng, bạn vẫn cần tránh đi ngược ngay về đỉnh cha trừ khi mã của bạn xử lý riêng trường hợp đó.

Cho Rằng DFS Tìm Được Đường Đi Ngắn Nhất

DFS có thể tìm ra một đường đi, nhưng nhìn chung không đảm bảo đó là đường đi ngắn nhất trong đồ thị không trọng số. Nếu mục tiêu là đường đi ngắn nhất và mọi cạnh đều có cùng trọng số, BFS thường là lựa chọn khởi đầu phù hợp hơn.

Xem Thứ Tự DFS Là Duy Nhất

Thứ tự phụ thuộc vào thứ tự xét các đỉnh kề. Nếu thứ tự đó thay đổi, thứ tự duyệt cũng có thể thay đổi.

Khi Nào Dùng Tìm Kiếm Theo Chiều Sâu

DFS hữu ích khi bạn muốn khám phá cấu trúc thay vì chỉ quan tâm đến khoảng cách gần nhất trước. Các ứng dụng phổ biến gồm:

• kiểm tra xem có thể đi tới một đỉnh hay không
• tìm các thành phần liên thông
• phát hiện chu trình trong một số bài toán đồ thị
• duyệt cây
• giải các bài toán kiểu quay lui như mê cung hoặc tìm kiếm lời giải cho câu đố

Lý do chính khiến DFS xuất hiện rất thường xuyên là vì cách "đi sâu, rồi quay lui" khớp với nhiều cấu trúc bài toán đệ quy.

DFS So Với BFS: Khác Biệt Trong Thực Tế

DFS đi xuống một nhánh trước. BFS khám phá tất cả các đỉnh ở cùng một khoảng cách trước khi chuyển sang khoảng cách tiếp theo.

Nếu bạn quan tâm đến việc khám phá toàn bộ hoặc cấu trúc đệ quy, DFS thường là lựa chọn tự nhiên. Nếu bạn quan tâm đến đường đi ngắn nhất trong đồ thị không trọng số, BFS thường là lựa chọn an toàn hơn để bắt đầu.

Hãy Thử Một Lần Duyệt Tương Tự

Hãy vẽ một đồ thị nhỏ có sáu đỉnh và chọn một thứ tự xét đỉnh kề cố định. Tự chạy DFS bằng tay và ghi lại chính xác lúc nào bạn đi tiếp và lúc nào bạn quay lui. Nếu thứ tự thay đổi sau khi bạn đổi thứ tự các đỉnh kề, đó không phải lỗi. Đó là một phần trong cách DFS hoạt động.