Giáo án điện tử chuyên đề Khoa học máy tính 12 kết nối Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu

NHIỆT LIỆT CHÀO MỪNG CÁC EM ĐẾN VỚI BÀI HỌC MỚI!

KHỞI ĐỘNG

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

a)

b)

Hình 14.1. Duyệt đồ thị

a)

b)

Hình 14.1. Duyệt đồ thị

Có thể duyệt đồ thị theo các cách sau:

• Duyệt theo chiều sâu: Bắt đầu từ một đỉnh, tiếp tục đi sâu vào đồ thị theo một nhánh cho đến khi không thể đi xa hơn, sau đó quay lại và tiếp tục với nhánh khác.
• Duyệt theo chiều rộng: Bắt đầu từ một đỉnh, duyệt tất cả các đỉnh kề với nó trước, sau đó mới chuyển sang duyệt các đỉnh ở mức độ sâu tiếp theo.

BÀI 14: KĨ THUẬT DUYỆT ĐỒ THỊ THEO CHIỀU SÂU

NỘI DUNG BÀI HỌC

Bài toán duyệt đồ thị

Thuật toán duyệt theo chiều sâu DFS

02

BÀI TOÁN DUYỆT ĐỒ THỊ

• Theo em, bài toán duyệt đồ thị là gì?
• Tìm hiểu ý tưởng của thuật toán duyệt đồ thị theo chiều sâu.

Bài toán duyệt đồ thị là: cần duyệt (đánh dấu) tất cả các đỉnh bằng cách đi theo các cạnh của đồ thị.

• Ý tưởng của thuật toán duyệt đồ thị theo chiều sâu:

- Mỗi khi xuất phát từ một đỉnh chưa được duyệt, cần đi dọc theo các cạnh theo hướng “sâu” nhất có thể.

- Luôn cố gắng duyệt theo hướng “ra xa” khỏi đỉnh ban đầu, đi tới đỉnh nào thì đánh dấu (duyệt) đỉnh đó, duyệt cho đến khi không đi được nữa thì quay lại đỉnh trước để tìm cách đi khác, cứ như vậy cho đến khi không tìm được đường đi nào nữa thì dừng lại.

- Lặp lại cho đến khi tất cả các đỉnh của đồ thị đã được đánh dấu.

Ví dụ:

Thuật toán duyệt đồ thị vô hướng trong Hình 14.1a theo chiều sâu. Giả sử bắt đầu duyệt từ đỉnh 0. Mũi tên màu đỏ chỉ hướng đi theo cạnh.

1. Bắt đầu từ đỉnh 0. Duyệt (đánh dấu) đỉnh 0.

2. Danh sách kề của 0 là [5].

Tìm được 5 chưa duyệt. Duyệt đỉnh 5.

3. Danh sách kề của 5 là [0,1,4,6,7]. Tìm được 1 chưa duyệt. Duyệt đỉnh 1.

4. Danh sách kề của 1 là [5,6].

Tìm được 6 chưa duyệt. Duyệt đỉnh 6.

5. Danh sách kề của 6 là [1,3,5,7]. Tìm được 3 chưa duyệt. Duyệt đỉnh 3.

6. Danh sách kề của 3 là [2,4,6]. Tìm được 2 chưa duyệt. Duyệt đỉnh 2.

7. Danh sách kề của 2 là [3,7]. Tìm thấy 7 chưa duyệt. Duyệt đỉnh 7.

8. Danh sách kề của 7 là [2,5,6]. Không tìm thấy. Quay lại đỉnh 2.

9. Danh sách kề của 2 là [3,7]. Không tìm thấy. Quay lại đỉnh 3.

10. Danh sách kề của 3 là [2,4,6]. Tìm thấy 4 chưa duyệt. Duyệt đỉnh 4.

11. Danh sách kề của 4 là [3,5]. Không tìm thấy. Quay lại đỉnh 3.

12. Từ đỉnh 3, không tìm thấy, lần lượt quay lại 6, quay lại 1, quay lại 5, quay lại 0.

Bảng 14.1. Các bước duyệt đồ thị

Lưu ý:

- Màu đỏ: các đỉnh đã được duyệt.

- In đậm: đỉnh đầu tiên trong danh sách kề chưa được duyệt.

- Nếu tất cả các đỉnh trong danh sách đỉnh kề đều đã duyệt (màu đỏ) thì thực hiện quay lại đỉnh của bước trước đó.

Bảng 14.1. Các bước duyệt đồ thị

• Thứ tự các đỉnh được duyệt là: 0 5 1 6 3 2 7 4.
• Thuật toán duyệt như trên được gọi là duyệt theo chiều sâu (DFS – Depth First Search).
• Áp dụng cho cả đồ thị vô hướng và có hướng.

Củng cố kiến thức

Câu 1. 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?

Có.

Câu 2. 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.

Hình 14.1b. Duyệt đồ thị

THUẬT TOÁN DUYỆT THEO CHIỀU SÂU DFS

Thảo luận nhóm: 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ì.

• Cho đồ thị G = (V, E) vô hướng hoặc có hướng.
• Ban đầu, tất cả các đỉnh của đồ thị là chưa đánh dấu.
• Thuật toán DFS(Adj,u) thực hiện công việc duyệt đồ thị theo chiều sâu bắt đầu từ đỉnh u chưa đánh dấu.

Thiết lập tất cả các đỉnh của đồ thị là chưa đánh dấu.

Duyệt đồ thị G theo chiều sâu có sử dụng thuật toán DFS(Adj,u) để bắt đầu duyệt từ đỉnh u.

DFS(Adj,u):

DFS_Traversal(G):

• Giả sử đồ thị G = (V, E) được biểu diễn bằng danh sách kề Adj. Mảng mark[] dùng để đánh dấu các đỉnh:

- mark[v] = False nghĩa là đỉnh v chưa được đánh dấu.

- mark[v] = True nghĩa là đỉnh v đã được đánh dấu.

- Ban đầu, mark[v] = False với mọi đỉnh v.

Hàm đệ quy DFS(Adj,u) trong Python dùng để duyệt đồ thị theo chiều sâu bắt đầu từ đỉnh u chưa đánh dấu.

Giải thích:

• Dòng lệnh 2 cho biết đỉnh u đã được đánh dấu.
• Dòng lệnh 3 kiểm tra các đỉnh kề v của đỉnh u.
• Khi kết thúc thực hiện hàm DFS(Adj,u) thì tất cả các đỉnh mà có đường đi từ đỉnh u đều được đánh dấu.

Hàm DFS_Traversal(V,Adj) sẽ duyệt đồ thị theo chiều sâu với bộ dữ liệu (V, Adj)

Chương trình sau đây sẽ tạo đồ thị từ tệp danh sách kề, sau đó duyệt đồ thị này theo chiều sâu dùng hàm DFS_Traversal():

Phân tích thời gian của DFS

• Mỗi đỉnh chỉ có thể duyệt đúng một lần → độ phức tạp thời gian duyệt các đỉnh của đồ thị là O(|V|) (kí hiệu O(V)
• Thời gian tìm đỉnh cần đi tiếp trong danh sách kề tại dòng 3, 4 sẽ tính như sau:

Phân tích thời gian của DFS

Độ phức tạp thời gian duyệt theo chiều sâu là:

• O(V+E) nếu đồ thị có hướng.
• O(V+2E) nếu đồ thị vô hướng.

Củng cố kiến thức

Câu 1. 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?

Nếu đồ thị G chỉ bao gồm các đỉnh biệt lập thì tất cả các lệnh DFS(v) sẽ chỉ đánh dấu đúng một đỉnh v. Do vậy thuật toán duyệt theo chiều sâu DFSTraversal(G) sẽ đánh dấu từng đỉnh của G bằng lời gọi hàm DFS(v), mỗi lệnh như vậy đánh dấu đúng một đỉnh.

Câu 2. 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.

Nếu kiểm tra thì sẽ thấy kết quả dãy các đỉnh đã được duyệt trùng khớp với kết quả duyệt thủ công trong Hoạt động 1.

Thảo luận nhóm: 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.

Thuật toán không đệ quy DFS sử dụng ngăn xếp (hoạt động theo cơ chế “vào sau, ra trước” – LIFO) để duyệt theo chiều sâu, bắt đầu từ đỉnh u.

Chương trình đọc dữ liệu từ tập đầu vào và thực hiện lệnh duyệt theo chiều sâu bắt đầu từ đỉnh 0.

Ví dụ: Với dữ liệu của danh sách kề Adj ở Bảng 14.1, khi thực hiện hàm duyệt DFS(Adj,0), kết quả thứ tự duyệt các đỉnh của đồ thị là: 0 5 7 6 3 4 2 1.

• Chương trình đọc dữ liệu từ tệp đầu vào và duyệt đồ thị theo chiều sâu như sau:
• Có thể thiết lập hàm duyệt theo chiều sâu áp dụng tổng quát đồ thị G với bộ dữ liệu (V, Adj) như sau:

Lưu ý: Độ phức tạp thời gian của thuật toán DFS không đệ quy giống như thuật toán DFS đệ quy.

Củng cố kiến thức

Câu 1. 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?

• Thứ tự các đỉnh được duyệt theo thuật toán DFS đệ quy là: 0 5 1 6 7 2 3 4.
• Thứ tự các đỉnh được duyệt theo thuật toán DFS không đệ quy là: 0 5 7 2 3 6 1 4.

Câu 2. 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).

• Theo thuật toán DFS đệ quy là: 0 1 2 4 5 3 6 7 8.
• Theo thuật toán DFS không đệ quy là: 0 3 8 7 6 2 5 4 1.

Hình 14.3. Đồ thị dạng cây

LUYỆN TẬP

(Trả lời câu hỏi trắc nghiệm)

$

Duyệt đồ thị theo chiều sâu sử dụng loại cấu trúc dữ liệu nào?

A. Mảng.

B. Hàng đợi.

C. Ngăn xếp.

D. Danh sách liên kết.

C. Ngăn xếp.

Câu 1

Thuật toán không đệ quy DFS sử dụng hàm nào để thực hiện xoá một đỉnh khỏi ngăn xếp?

A. top(S).

B. remove(S).

C. front(S).

D. pop(S).

D. pop(S).

Câu 2

--------------- Còn tiếp ---------------