Giáo án 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

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

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- Từ hoạt động Khởi động, GV yêu cầu HS suy nghĩ và trả lời câu hỏi:

+ Theo em, bài toán duyệt đồ thị là gì?

- GV yêu cầu HS đọc Hoạt động 1 – Tìm hiểu ý tưởng của thuật toán duyệt đồ thị theo chiều sâu SGK tr.65, từ đó dẫn dắt HS tìm hiểu kiến thức.

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

- GV trình bày ý tưởng của thuật toán duyệt đồ thị theo chiều sâu và hướng dẫn HS cách duyệt thông qua ví dụ cụ thể.

- GV yêu cầu HS vận dụng kiến thức vừa tìm hiểu, thực hiện hoạt động Củng cố kiến thức tr.67 SGK:

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

Bước 2: HS thực hiện nhiệm vụ học tập

- HS tìm hiểu nội dung mục 1 SGK tr.65 – 67 và thực hiện các nhiệm vụ học tập.

- GV quan sát và trợ giúp HS (nếu cần thiết).

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- HS lần lượt trả lời các câu hỏi.

- HS khác lắng nghe và nhận xét, bổ sung cho nhau. 

Hướng dẫn thực hiện hoạt động Củng cố kiến thức SGK tr.67:

Câu 1. Có.

Câu 2. Quá trình duyệt theo chiều sâu của đồ thị có hướng trong Hình 14.1b xuất phát từ đỉnh 4:

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

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

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

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

5. Đỉnh 1 không có đỉnh kề. Quay lại đỉnh 6.

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

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

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

9. Từ đỉnh 7, không tìm thấy, lần lượt quay lại đỉnh 6, quay lại đỉnh 3, quay lại đỉnh 4.

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

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

12. Danh sách kề của 4 là [3,5]. Không tìm thấy. Kết thúc duyệt.

Thứ tự các đỉnh được duyệt là: 4 3 6 1 7 2 5.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- Từ câu trả lời của HS, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.

- GV chốt kiến thức theo Hộp kiến thức.

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

- 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ể, tức là 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. Quá trình như vậy 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.

Hình 14.2. Chi tiết các bước duyệt theo chiều sâu, bắt đầu từ đỉnh 0

Chi tiết các bước của duyệt đồ thị trên được mô tả trong Bảng 14.1.

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

Lưu ý: 

• Màu đỏ là các đỉnh đã được duyệt (đánh dấu) trước đó. 

• In đậm là đỉnh đầu tiên trong danh sách kề chưa được duyệt, đỉnh này được đánh dấu “tìm thấy” để thực hiện bước đi tiếp theo. 

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

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). Thuật toán duyệt này áp dụng cho cả đồ thị vô hướng và có hướng.

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV yêu cầu HS đọc Hoạt động 2 – Tìm hiểu thuật toán duyệt DFS SGK tr.68, từ đó dẫn dắt HS tìm hiểu kiến thức.

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

- Dựa vào ý tưởng thuật toán thực hiện trong Hoạt động 1, GV hướng dẫn HS viết mã giả và các hàm tương ứng bằng Python.

- GV yêu cầu HS quan sát hàm DFS(Adj,u) và giải thích ý nghĩa của các dòng lệnh.

- GV phân tích thời gian của DFS từ đó yêu cầu HS:

+ Em hãy xác định độ phức tạp thời gian của thuật toán duyệt theo chiều sâu trong cả hai trường hợp đồ thị có hướng và vô hướng.

- GV yêu cầu HS vận dụng kiến thức vừa tìm hiểu, thực hiện hoạt động Củng cố kiến thức tr.69 SGK:

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?

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.

Bước 2: HS thực hiện nhiệm vụ học tập

- HS thực hiện nhiệm vụ học tập theo yêu cầu của GV.

- GV quan sát và trợ giúp HS (nếu cần thiết).

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- HS lần lượt trả lời các câu hỏi.

- HS khác lắng nghe và nhận xét, bổ sung cho nhau. 

Hướng dẫn thực hiện hoạt động Củng cố kiến thức SGK tr.69:

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

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

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- Từ câu trả lời của HS, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.

- GV chốt kiến thức theo Hộp kiến thức.

…………………

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

Cho trước đồ 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.

- Đoạn mã giả sau thực hiện các công việc: 

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

DFS_Traversal(G):

• 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):

- 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 như sau:

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. Nếu có đỉnh v chưa được đánh dấu thì gọi đệ quy cho đỉnh này. Đây chính là ý tưởng của duyệt đồ thị theo chiều sâu đã mô tả trong Hoạt động 1. 

• 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) như sau:

+ 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:

• Theo cách thiết lập tại dòng 2 thì mỗi đỉnh của đồ thị G chỉ có thể duyệt đúng một lần, do đó độ phức tạp thời gian duyệt các đỉnh của đồ thị sẽ là O(|V|). Kí hiệu đơn giản 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: Vì tổng tất cả các việc tìm đỉnh kề tại dòng 3 sẽ bằng chính số các cạnh của đồ thị G, tức là bằng |E|. Với đồ thị có hướng thì mỗi cạnh được duyệt một lần trong lệnh 3, còn nếu G là đồ thị vô hướng thì số lần duyệt các đỉnh kề sẽ bằng 2|E| vì mỗi cạnh sẽ được tìm duyệt hai lần.

Độ phức tạp thời gian duyệt theo chiều sâu là O(V+E) nếu đồ thị có hướng và là O(V+2E) nếu đồ thị vô hướng.

………………………….