Câu hỏi:
11/07/2024 194
Mô tả quá trình duyệt theo chiều sâu của đồ thị có hướng trong Hình 14.1b nếu xuất phát từ đỉnh 4.
Mô tả quá trình duyệt theo chiều sâu của đồ thị có hướng trong Hình 14.1b nếu xuất phát từ đỉnh 4.
Quảng cáo
Trả lời:
Quá trình duyệt theo chiều sâu (DFS) của đồ thị có hướng bắt đầu từ đỉnh 4 được mô tả như sau:
1. Bắt đầu tại đỉnh 4: Đánh dấu đỉnh 4 là đã thăm.
2. Thăm đỉnh kề: Chọn một trong các đỉnh kề với đỉnh 4 để thăm tiếp theo. Đỉnh 4 có cạnh đi ra đến đỉnh 3 và đỉnh 2.
o Nếu chọn đỉnh 3 trước:
a) Thăm đỉnh 3 và đánh dấu là đã thăm.
b) Tiếp tục thăm đỉnh kề của đỉnh 3 là đỉnh 6.
c) Thăm đỉnh 6 và đánh dấu là đã thăm.
d) Thăm đỉnh kề của đỉnh 6 là đỉnh 7 và đánh dấu là đã thăm.
e) Quay trở lại đỉnh 4 và thăm đỉnh 2, sau đó là đỉnh 7 nếu chưa được thăm.
* Nếu chọn đỉnh 2 trước:
a) Thăm đỉnh 2 và đánh dấu là đã thăm.
b) Thăm đỉnh kề của đỉnh 2 là đỉnh 7 và đánh dấu là đã thăm.
c) Quay trở lại đỉnh 4 và thăm đỉnh 3, sau đó là đỉnh 6 và đỉnh 7 nếu chưa được thăm.
Quá trình này tiếp tục cho đến khi tất cả các đỉnh có thể tiếp cận từ đỉnh xuất phát đã được thăm. Trong DFS, chúng ta sẽ đi sâu vào từng nhánh một cách càng sâu càng tốt trước khi quay trở lại (backtrack).
Hot: 500+ Đề thi thử tốt nghiệp THPT các môn, ĐGNL các trường ĐH... file word có đáp án (2025). Tải ngay
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Lời giải
Ý tưởng chính của DFS:
DFS hoạt động bằng cách bắt đầu từ một đỉnh nguồn, đánh dấu nó là đã thăm, sau đó tiếp tục đi sâu vào các đỉnh kề chưa thăm cho đến khi không thể đi tiếp được nữa. Khi không thể đi tiếp, thuật toán quay lui về các đỉnh trước đó để tiếp tục tìm kiếm các đường đi mới.
Lời giải
Để cài đặt thuật toán duyệt theo chiều sâu (DFS) mà không sử dụng đệ quy, chúng ta có thể sử dụng ngăn xếp (stack) để theo dõi các đỉnh và thực hiện duyệt. Dưới đây là một số cách cài đặt DFS không sử dụng đệ quy:
1. Sử dụng ngăn xếp (Stack):
- Bắt đầu bằng việc đưa một đỉnh bất kỳ vào ngăn xếp.
- Lặp qua các bước sau cho đến khi ngăn xếp trống:
a) Lấy đỉnh trên cùng của ngăn xếp (top value).
b) Đánh dấu đỉnh này là đã thăm (thêm vào danh sách visited).
c) Thêm tất cả các đỉnh kề của đỉnh đang xét vào ngăn xếp, nếu chưa được thăm.
d) Lặp lại bước a) cho đến khi không còn đỉnh kề nào để thêm vào ngăn xếp.
2. Sử dụng hàng đợi (Queue):
- Tương tự như cách sử dụng ngăn xếp, nhưng thay vì ngăn xếp, chúng ta sử dụng hàng đợi.
- Bắt đầu bằng việc đưa một đỉnh bất kỳ vào hàng đợi.
- Lặp qua các bước sau cho đến khi hàng đợi trống:
a) Lấy đỉnh đầu tiên của hàng đợi.
b) Đánh dấu đỉnh này là đã thăm.
c) Thêm tất cả các đỉnh kề của đỉnh đang xét vào hàng đợi, nếu chưa được thăm.
d) Lặp lại bước a) cho đến khi không còn đỉnh kề nào để thêm vào hàng đợi.
3. Sử dụng danh sách liên kết (Linked List):
- Thay vì sử dụng ngăn xếp hoặc hàng đợi, chúng ta có thể sử dụng danh sách liên kết để lưu trữ các đỉnh.
- Bắt đầu bằng việc đưa một đỉnh bất kỳ vào danh sách liên kết.
- Lặp qua các bước sau cho đến khi danh sách liên kết trống:
a) Lấy đỉnh đầu tiên của danh sách liên kết.
b) Đánh dấu đỉnh này là đã thăm.
c) Thêm tất cả các đỉnh kề của đỉnh đang xét vào danh sách liên kết
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.