Giải chuyên đề Tin 12 KNTT Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu có đáp án

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ị đó.

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

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?

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.

Quan sát, thảo luận và tìm hiểu thuật toán duyệt theo chiều sâu trên đồ thị bất kì.

Nếu đồ thị G chỉ bao gồm các đỉnh biệt lập, không có cạnh nào thì thuật toán duyệt sâu DFS sẽ được thực hiện như thế nào? 

Chỉnh sửa hàm DFS() bổ sung lệnh in thông tin của các đỉnh khi duyệt. Ví dụ hàm DFS() có thể viết lại như sau:

Sử dụng hàm trên áp dụng duyệt các phần tử của đồ thị Hình 14.1a trong phần khởi động. Kiểm tra thứ tự các đỉnh đã duyệt có trùng khớp với thứ tự các đỉnh đã duyệt (bằng tay) trong Hoạt động 1 hay không.

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.

Nếu áp dụng thuật toán duyệt DFS cho đồ thị có hướng Hình 14.1b trong phần khởi động thì thứ tự các đỉnh được đánh dấu sẽ theo thứ tự nào?

Với đồ thị Hình 14.3 thì thứ tự các đỉnh đã duyệt theo chiều sâu, bắt đầu từ đỉnh 0 sẽ như thế nào? (theo cả hai cách đệ quy và không đệ quy).

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

Hàm DFS(Adj,u) có thể viết theo một cách khác, việc kiểm tra đỉnh u đã đánh dấu chưa được đưa vào bên trong hàm như sau:

a) Trong trường hợp này, phần chương trình chính cần viết lại như thế nào?

b) Viết lại toàn bộ chương trình duyệt đồ thị theo chiều sâu theo hàm mô tả trên. Cách duyệt này có tương đương với cách đã thực hiện trong Hoạt động 2 không?

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.

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.

Cho đồ thị G = (V, E) và hai đỉnh s, t bất kì. Chứng minh tính chất: Tồn tại đường đi từ s đến t khi và chỉ khi quá trình duyệt theo chiều sâu từ đỉnh s sẽ duyệt qua đỉnh t, hay nói cách khác, quá trình duệt theo chiều sâu từ đỉnh s sẽ đi qua tất cả các đỉnh nằm trong thành phần liên thông chứa đỉnh s, trong đó có đỉnh t.