Cấu trúc dữ liệu - Truyền tải đầu tiên theo chiều sâu
Thuật toán Tìm kiếm đầu tiên theo chiều sâu (DFS) duyệt đồ thị theo chuyển động theo chiều sâu và sử dụng một ngăn xếp để ghi nhớ để lấy đỉnh tiếp theo để bắt đầu tìm kiếm, khi điểm cuối xảy ra trong bất kỳ lần lặp nào.
Như trong ví dụ được đưa ra ở trên, thuật toán DFS truyền từ S đến A đến D đến G đến E đến B trước, sau đó đến F và cuối cùng là C. Nó sử dụng các quy tắc sau.
Rule 1- Ghé thăm đỉnh không được thăm liền kề. Đánh dấu nó là đã ghé thăm. Hiển thị nó. Đẩy nó vào một ngăn xếp.
Rule 2- Nếu không tìm thấy đỉnh liền kề, bật lên một đỉnh từ ngăn xếp. (Nó sẽ bật lên tất cả các đỉnh từ ngăn xếp, mà không có các đỉnh liền kề.)
Rule 3 - Lặp lại Quy tắc 1 và Quy tắc 2 cho đến khi ngăn xếp trống.
| Bươc | Traversal | Sự miêu tả |
|---|---|---|
| 1 |
|
Khởi tạo ngăn xếp. |
| 2 |
|
dấu Snhư đã thăm và đặt nó vào ngăn xếp. Khám phá bất kỳ nút liền kề nào chưa được sử dụngS. Chúng tôi có ba nút và chúng tôi có thể chọn bất kỳ nút nào trong số đó. Đối với ví dụ này, chúng ta sẽ lấy nút theo thứ tự bảng chữ cái. |
| 3 |
|
dấu Anhư đã thăm và đặt nó vào ngăn xếp. Khám phá bất kỳ nút liền kề không được mong đợi nào từ A. Cả haiS và D tiếp giáp với A nhưng chúng tôi chỉ quan tâm đến các nút không được truy cập. |
| 4 |
|
Chuyến thăm Dvà đánh dấu nó là đã thăm và đặt vào ngăn xếp. Ở đây chúng tôi cóB và C các nút tiếp giáp với Dvà cả hai đều không được mời. Tuy nhiên, chúng ta sẽ chọn lại theo thứ tự bảng chữ cái. |
| 5 |
|
Chúng tôi chọn B, đánh dấu nó là đã thăm và đặt vào ngăn xếp. ĐâyBkhông có bất kỳ nút liền kề không được truy cập nào. Vì vậy, chúng tôi bậtB từ ngăn xếp. |
| 6 |
|
Chúng tôi kiểm tra đỉnh ngăn xếp để quay lại nút trước đó và kiểm tra xem nó có bất kỳ nút nào chưa được truy cập hay không. Ở đây, chúng tôi tìm thấyD ở trên cùng của ngăn xếp. |
| 7 |
|
Chỉ có nút liền kề không được kiểm soát là từ D Là Chiện nay. Vì vậy, chúng tôi đến thămC, đánh dấu nó là đã thăm và đặt nó vào ngăn xếp. |
Như Ckhông có bất kỳ nút liền kề nào chưa được duyệt, vì vậy chúng tôi tiếp tục bật ngăn xếp cho đến khi chúng tôi tìm thấy một nút có nút liền kề không được truy cập. Trong trường hợp này, không có gì và chúng tôi tiếp tục xuất hiện cho đến khi ngăn xếp trống.
Để biết về việc thực hiện thuật toán này trong ngôn ngữ lập trình C, hãy nhấp vào đây .