Trang chủ > Khác > Cấu trúc dữ liệu và giải thuật > Tìm kiếm theo chiều sâu - Depth First Traversal (Cấu trúc dữ liệu và giải thuật)

Tìm kiếm theo chiều sâu - Depth First Traversal (Cấu trúc dữ liệu và giải thuật)

Giải thuật tìm kiếm theo chiều sâu (Depth First Search – được viết tắt là DFS), còn được gọi là giải thuật tìm kiếm ưu tiên theo chiều sâu, là giải thuật duyệt hoặc tìm kiếm trên một một đồ thị hoặc một cây và có sử dụng stack (ngăn xếp) để ghi nhớ đỉnh liền kề để bắt đầu công việc việc tìm kiếm khi không gặp được đỉnh liền kề trong một vòng lặp bất kỳ nào. Giải thuật sẽ tiếp tục thực hiên cho đến khi gặp được đỉnh cần tìm hoặc tìm tới một nút không có con. Khi đó giải thuật sẽ quay lui về đỉnh vừa mới tìm kiếm được ở bước trước.

Trong hình minh họa ở trên, giải thuật tìm kiếm theo chiều sâu đầu tiên bắt đầu duyệt từ đỉnh A tới B tới C tới D sau đó đến E, sau đó tới F và cuối cùng là đến G. Giải thuật này sẽ tuân theo qui tắc sau:

  • Qui tắc 1: Duyệt tiếp tới đỉnh liền kề mà chưa được duyệt. Đánh dấu vào đỉnh mà đã được duyệt. Hiển thị đỉnh đó và đẩy vào trong một ngăn xếp (stack).

  • Qui tắc 2: Nếu không thể tìm thấy đỉnh liền kề, thì sẽ lấy một đỉnh từ trong ngăn xếp (thao tác pop up). (Giải thuật sẽ lấy tất cả các đỉnh bên trong ngăn xếp mà không có các đỉnh liền kề nào)

  • Qui tắc 3: Lặp lại các qui tắc 1 và qui tắc 2 cho đến khi ngăn xếp đã hết.

Bảng sau đây minh họa các qui tắc với hình ví dụ trên:

Bước Duyệt Miêu tả
1.
Khởi tạo ngăn xếp (stack)
2.
Đánh dấu đỉnh S là đã duyệt và đặt đỉnh này vào bên trong ngăn xếp. Tìm kiếm bất kỳ đỉnh liền kề nào mà chưa được duyệt bắt đầu từ đỉnh S. Chúng ta có ba đỉnh và chúng ta có thể chọn bất kỳ đỉnh nào trong số chúng. Ví dụ, chúng ta lấy đỉnh A theo thứ tự chữ cái.
3.
Đánh dấu đỉnh A là đã duyệt và đặt vào trong ngăn xếp. Tìm kiếm đỉnh liền kề bất kỳ với đỉnh A. Cả S và D đều là hai đỉnh liền kề với A nhưng chúng ta chỉ cần quan tâm về đỉnh chưa được duyệt.
4.
Duyệt đỉnh D, đánh dấu đỉnh này là đã được duyệt và đặt vào trong ngăn xếp. Ở đây, chúng ta có đỉnh B và C là 2 đỉnh kề với D và cả 2 đỉnh này đều là chưa được duyệt. Chúng ta sẽ lựa chọn theo thứ tự chữ cái một lần nữa.
5.
Chọn B, đánh dấu là đã được duyệt và đặt vào trong ngăn xếp. Ở đây B không có đỉnh liền kề nào mà chưa được duyệt. Chính vì thế chúng ta cần lấy B ra khỏi ngăn xếp.
6.
Kiểm tra phần tử trên cùng của ngăn xếp để trở về nút đã được duyệt trước đó và sau đó kiểm tra xem đỉnh này có đỉnh liền kề nào mà chưa được duyệt hay không. Ở đây, chúng ta sẽ tìm thấy đỉnh D nằm ở trên cùng của ngăn xếp.
7.
Chỉ có duy nhất một đỉnh liền kề với D mà chưa được duyệt, đó chính là đỉnh C. Chúng ta sẽ duyệt C, đánh dấu là đã được duyệt và đặt vào trong ngăn xếp.

Vì C không có bất kỳ đỉnh liền kề nào mà chưa được duyệt, chúng ta sẽ lấy các đỉnh từ trong ngăn xếp ra để kiểm tra xem có còn bất kỳ đỉnh nào liền kề mà chưa được duyệt hay không. Trong ví dụ này là kết quả không có, và chúng ta vẫn tiếp tục cho đến khi nào ngăn xếp là trống.