Cộng đồng chia sẻ tri thức Lib24.vn

Cấu trúc dữ liệu - Độ sâu truyền tải đầu tiên

Gửi bởi: Võ Thị Hường 13 tháng 2 2020 lúc 11:48:14


Thuật toán Depth First Search (DFS) đi ngang qua một đồ thị theo chuyển động 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 một ngõ cụt xảy ra trong bất kỳ lần lặp nào.

Như trong ví dụ đã nêu ở trên, thuật toán DFS đi qua 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.

  1. Quy tắc 1 - Ghé thăm đỉnh không mong muốn liền kề. Đánh dấu nó như đã truy cập. Hiển thị nó. Đẩy nó trong một ngăn xếp.
  2. Quy tắc 2 - Nếu không tìm thấy đỉnh liền kề, hãy 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, không có các đỉnh liền kề.)
  3. Quy tắc 3 - Lặp lại quy tắc 1 và quy tắc 2 cho đến khi ngăn xếp trống.
Cấu trúc dữ liệu - Độ sâu truyền tải đầu tiên

  Vì C không có bất kỳ nút lân cận không được chú ý nào, 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ó một nút liền kề không được chú ý. Trong trường hợp này, không có gì và chúng tôi tiếp tục bật cho đến khi ngăn xếp trống.  


Được cập nhật: hôm qua lúc 2:52:30 | Lượt xem: 410

Các bài học liên quan