Câu hỏi:

11/07/2024 148

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.

Sách mới 2k7: Bộ 20 đề minh họa Toán, Lí, Hóa, Văn, Sử, Địa…. form chuẩn 2025 của Bộ giáo dục (chỉ từ 49k/cuốn).

Đề toán-lý-hóa Đề văn-sử-địa Tiếng anh & các môn khác

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

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).

Bình luận


Bình luận

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1:

Tìm hiểu ý tưởng của thuật toán duyệt đồ thị theo chiều sâu (DFS – Depth First Search).

Xem đáp án » 11/07/2024 395

Câu 2:

Tìm hiểu một cách cài đặt khác của thuật toán duyệt theo chiều sâu DFS không sử dụng kĩ thuật đệ quy.

Xem đáp án » 11/07/2024 302

Câu 3:

Viết chương trình in ra thứ tự các đỉnh đã được duyệt bằng thuật toán DFS theo cả hai cách đệ quy và không đệ quy, áp dụng cho đồ thị có hướng Hình 14.1b trong phần Khởi động.

Xem đáp án » 11/07/2024 302

Câu 4:

Sửa chương trình của thuật toán DFS không đệ quy sao cho chương trình trong khi duyệt sẽ in ra các bước với thông tin sau:

– Thông tin ngăn xếp (hiện thời).

– Phần tử được lấy ra từ ngăn xếp.

– Phần tử được đánh dấu để chuẩn bị cho bước sau (mark).

Xem đáp án » 11/07/2024 277

Câu 5:

Chúng ta đã biết bài toán và thuật toán duyệt (tìm kiếm) dữ liệu trên các cấu trúc dữ liệu khác nhau:

– Kiểu dữ liệu mảng (một hoặc hai chiều).

– Kiểu dữ liệu cây (cây nhị phân và cây tìm kiếm nhị phân).

Vậy với dữ liệu của đồ thị, việc duyệt các đỉnh của đồ thị sẽ được thực hiện như thế nào? Quan sát hai đồ thị ở Hình 14.1 và thảo luận với bạn cách thực hiện duyệt trên các đỉnh của đồ thị đó.

Chúng ta đã biết bài toán và thuật toán duyệt (tìm kiếm) dữ liệu trên các cấu trúc dữ liệu khác nhau: – Kiểu dữ liệu mảng (một hoặc hai chiều). – Kiểu dữ liệu cây (cây nhị phân và cây tìm kiếm nhị phân). Vậy với dữ liệu của đồ thị, việc duyệt các đỉnh của đồ thị sẽ được thực hiện như thế nào? Quan sát hai đồ thị ở Hình 14.1 và thảo luận với bạn cách thực hiện duyệt trên các đỉnh của đồ thị đó. (ảnh 1)

Xem đáp án » 26/06/2024 215

Câu 6:

Thứ tự các đỉnh trong danh sách kề có ảnh hưởng đến thứ tự các đỉnh được duyệt của thuật toán DFS không?

Xem đáp án » 11/07/2024 182

Câu 7:

Các thuật toán DFS đã mô tả trong các phần trên đều thực hiện trên đồ thị được biểu diễn bằng danh sách kề Adj. Hãy viết lại hàm DFS() được thực hiện trên đồ thị được biểu diễn bằng ma trận kề A.

Xem đáp án » 11/07/2024 151