Giáo án chuyên đề Khoa học máy tính 12 cánh diều Bài 4: Duyệt đồ 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

- GV giới thiệu khái niệm và các phương pháp duyệt đồ thị, sau đó đặt câu hỏi:

+ Bài toán ở phần Khởi động có thể giải quyết bằng cách duyệt đồ thị như thế nào?

+ Theo em, duyệt đồ thị có những ứng dụng gì?

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.62 và trả lời các câu hỏi mà GV đưa ra.

- 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 nhận xét, bổ sung. 

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ính xác hoá lại các nội dung kiến thức.

- GV chuyển sang nội dung tiếp theo.

1. Khái niệm đồ thị

- Khái niệm: Duyệt đồ thị là đi thăm các đỉnh của đồ thị theo quy tắc ưu tiên định trước. 

- Trong quá trình duyệt, mỗi đỉnh được đánh dấu để đảm bảo không có đỉnh nào được thăm quá một lần.

- Có hai cách duyệt chính: 

+ Duyệt theo chiều rộng.

+ Duyệt theo chiều sâu. 

- Bài toán được đề cập ở phần khởi động có thể giải quyết bằng cách duyệt đồ thị xuất phát từ đỉnh tương ứng là người cần thông báo tin, đi thăm các đỉnh của đồ thị có thể tới được.

- Một số ứng dụng của duyệt đồ thị: 

+ Kiểm tra tính kết nối của đồ thị.

+ Tìm kiếm đường đi giữa các đỉnh.

+ Xác định các thuộc tính khác nhau 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

- GV giới thiệu phương pháp duyệt đồ thị theo chiều rộng.

- GV nhấn mạnh “Duyệt đồ thị theo chiều rộng sử dụng cấu trúc dữ liệu hàng đợi” sau đó yêu cầu HS nhắc lại kiến thức đã học:

+ Hàng đợi hoạt động theo cơ chế gì?

- GV trình bày các bước duyệt đồ thị theo chiều rộng.

- GV chia lớp thành các nhóm 3 – 4 HS và đặt câu hỏi cho các nhóm thảo luận:

+ Hãy mô tả thuật toán BFS trên đồ thị trong Hình 1 bắt đầu từ đỉnh A từ đó trả lời lại câu hỏi ở phần Khởi động.

+ Có phải khi nào duyệt đồ thị theo chiều rộng bắt đầu từ một đỉnh cũng đều thăm được hết toàn bộ các đỉnh của đồ thị không?

+ Để duyệt toàn bộ đồ thị theo chiều rộng, ta cần thực hiện như thế nào? Hãy viết mã giả mô tả thuật toán duyệt đồ thị theo chiều rộng bắt đầu từ đỉnh start và duyệt toàn bộ đồ thị.

- GV yêu cầu các nhóm thực hiện hoạt động Thực hành 1 SGK tr.65.

Thực hành 1: Mô phỏng thuật toán BFS trên đồ thị trong Hình 1 bắt đầu từ đỉnh E, em hãy cho biết những đỉnh nào có thể đến được từ đỉnh E.

Gợi ý: Thực hiện các bước của thuật toán duyệt đồ thị theo chiều rộng bắt đầu từ đỉnh E, sau khi duyệt xong hàng đợi Q sẽ như sau:

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 2 SGK tr.62 – 65 sau đó trao đổi, thảo luận thực hiện các yêu cầu mà GV đưa ra.

- 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

- GV mời đại diện các nhóm báo cáo kết quả thảo luận.

- Các nhóm nhận xét, bổ sung cho nhau.

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

- Từ kết quả thảo luận nhóm, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.

- GV chính xác hoá lại các nội dung kiến thức. 

- GV chuyển sang nội dung tiếp theo.

2. Duyệt đồ thị theo chiều rộng

- Duyệt đồ thị theo chiều rộng (Breadth First Search – viết tắt là BFS) bắt đầu từ một đỉnh là thực hiện thăm các đỉnh theo từng tầng bắt đầu từ đỉnh xuất phát đó. Các đỉnh đến được từ đỉnh xuất phát là các đỉnh thuộc tầng một, các đỉnh chưa đến được nhưng đến được từ các đỉnh thuộc tầng một là các đỉnh thuộc tầng hai,… Để duyệt đồ thị theo cách như vậy thì thứ tự đỉnh được lựa chọn để mở rộng đi tiếp là đỉnh được thăm sớm nhất trong các đỉnh chờ để mở rộng. 

- Duyệt đồ thị theo chiều rộng sử dụng cấu trúc dữ liệu hàng đợi, thăm các đỉnh theo nguyên tắc vào trước ra trước (FIFO – First In First Out).

- Các bước duyệt đồ thị theo chiều rộng bắt đầu từ đỉnh start sử dụng hàng đợi như sau:

Bước 1. Khởi tạo hàng đợi rỗng  Thêm đỉnh start vào hàng đợi  Thăm và đánh dấu đỉnh start đã thăm.

Bước 2. Gọi u là đỉnh ở đầu hàng đợi. Xét lần lượt từng đỉnh v thuộc tập đỉnh kề của u: 

• Nếu đỉnh v chưa được thăm thì thêm đỉnh v vào hàng đợi, thăm v và đánh dấu đỉnh v đã thăm. 

• Nếu đã xét hết các đỉnh kề của u thì xoá (lấy ra) u khỏi hàng đợi.

Bước 3. Nếu hàng đợi khác rỗng thì quay lại Bước 2. Ngược lại, kết thúc quá trình duyệt.

Ví dụ: Mô phỏng thuật toán BFS trên đồ thị trong Hình 1 bắt đầu từ đỉnh A.

Hình 1. Một đồ thị mô tả mối quan hệ 
có thể liên lạc

1. Khởi tạo hàng đợi Q rỗng, thêm đỉnh A vào hàng đợi Q, thăm A và đánh dấu đỉnh A đã thăm.

1. Hiện tại, đỉnh A là đỉnh ở đầu hàng đợi Q, xét đỉnh C là đỉnh kề của đỉnh A, vì đỉnh C chưa được thăm nên thêm đỉnh C vào hàng đợi Q, thăm C và đánh dấu đỉnh C đã thăm.

1. Tiếp tục xét đỉnh D là đỉnh kề của đỉnh A, vì đỉnh D chưa được thăm nên thêm đỉnh D vào hàng đợi Q, thăm D và đánh dấu đỉnh D đã thăm.

1. Đỉnh A đã xét hết các đỉnh kề, xoá đỉnh A khỏi hàng đợi Q.

1. Hiện tại, đỉnh C đứng ở đầu hàng đợi Q, xét đỉnh B là đỉnh kề của đỉnh C vì đỉnh B chưa được thăm nên thêm đỉnh B vào hàng đợi Q, thăm B và đánh dấu đỉnh B đã thăm.

1. Đỉnh C đã xét hết các đỉnh kề, xoá đỉnh C khỏi hàng đợi Q.

1. Hiện tại, đỉnh D đứng ở đầu hàng đợi Q, chỉ có đỉnh C là đỉnh kề của đỉnh D, nhưng đỉnh C đã thăm nên không được thêm vào hàng đợi Q. Khi đó, đỉnh D đã xét hết các đỉnh kề, xoá đỉnh D khỏi hàng đợi Q.

1. Hiện tại, đỉnh B đứng ở đầu hàng đợi Q, chỉ có đỉnh A là đỉnh kề của đỉnh B, nhưng đỉnh A đã thăm nên không được thêm vào hàng đợi Q. Khi đó, đỉnh B đã xét hết các đỉnh kề, xoá đỉnh B khỏi hàng đợi Q, hàng đợi Q rỗng, thuật toán kết thúc.

Sau khi thực hiện duyệt đồ thị theo chiều rộng bắt đầu từ đỉnh A, ta thấy từ đỉnh A có thể đi đến được các đỉnh C, D, B. 

Câu trả lời cho phần khởi động là: Nếu A muốn thông tin cho các bạn thì các bạn B, C, D sẽ nhận được thông tin.

- Khi duyệt đồ thị theo chiều rộng bắt đầu từ một đỉnh, chúng ta có thể chưa thăm được hết toàn bộ các đỉnh của đồ thị. Chẳng hạn, trong ví dụ trên đỉnh E chưa được thăm. 

- Để duyệt toàn bộ đồ thị theo chiều rộng, ta cần xét lần lượt từng đỉnh s của đồ thị, nếu đỉnh s chưa được thăm thì gọi hàm BFS bắt đầu từ đỉnh s. 

- Mã giả mô tả thuật toán duyệt đồ thị theo chiều rộng bắt đầu từ đỉnh start và duyệt toàn bộ đồ thị:

Hình 2. Mã giả mô tả thuật toán duyệt đồ thị theo chiều rộng

Hướng dẫn thực hiện hoạt động Thực hành 1 SGK tr.65:

1. Khởi tạo hàng đợi Q rỗng, thêm đỉnh E vào hàng đợi Q, thăm E và đánh dấu đỉnh E đã thăm.

1. Hiện tại, đỉnh E là đỉnh ở đầu hàng đợi Q, xét đỉnh D là đỉnh kề của đỉnh E, vì đỉnh D chưa được thăm nên thêm đỉnh D vào hàng đợi Q, thăm D và đánh dấu đỉnh D đã thăm.

1. Đỉnh E đã xét hết các đỉnh kề, xoá đỉnh E khỏi hàng đợi Q.

1. Hiện tại, đỉnh D đứng ở đầu hàng đợi Q, xét đỉnh C là đỉnh kề của đỉnh D vì đỉnh C chưa được thăm nên thêm đỉnh C vào hàng đợi Q, thăm C và đánh dấu đỉnh C đã thăm.

1. Đỉnh D đã xét hết các đỉnh kề, xoá đỉnh D khỏi hàng đợi Q.

1. Hiện tại, đỉnh C đứng ở đầu hàng đợi Q, xét đỉnh B là đỉnh kề của đỉnh C vì đỉnh B chưa được thăm nên thêm đỉnh B vào hàng đợi Q, thăm B và đánh dấu đỉnh B đã thăm.

1. Đỉnh C đã xét hết các đỉnh kề, xoá đỉnh C khỏi hàng đợi Q.

1. Hiện tại, đỉnh B đứng ở đầu hàng đợi Q, xét đỉnh A là đỉnh kề của đỉnh B vì đỉnh A chưa được thăm nên thêm đỉnh A vào hàng đợi Q, thăm A và đánh dấu đỉnh A đã thăm.

1. Đỉnh B đã xét hết các đỉnh kề, xoá đỉnh B khỏi hàng đợi Q.

1. Hiện tại, đỉnh A đứng ở đầu hàng đợi Q, có đỉnh C, D là đỉnh kề của đỉnh A, nhưng đỉnh C, D đã thăm nên không được thêm vào hàng đợi Q. Khi đó, đỉnh A đã xét hết các đỉnh kề, xoá đỉnh A khỏi hàng đợi Q, hàng đợi Q rỗng, thuật toán kết thúc.

Sau khi thực hiện duyệt đồ thị theo chiều rộng bắt đầu từ đỉnh E, ta thấy các đỉnh D, C, B, A có thể đến được từ đỉnh E.