Giáo án điện tử chuyên đề Khoa học máy tính 12 cánh diều Bài 5: Thực hành duyệt đồ thị

CHÀO MỪNG CÁC EM ĐẾN

BUỔI HỌC NGÀY HÔM NAY!

KHỞI ĐỘNG

Hãy liệt kê thứ tự duyệt các đỉnh với thuật toán duyệt đồ thị theo chiều sâu xuất phát từ đỉnh A của đồ thị sau:

KHỞI ĐỘNG

Có nhiều kết quả duyệt theo chiều sâu xuất phát từ đỉnh A, ví dụ: A, G, F, I, H, J…

BÀI 5:

THỰC HÀNH

DUYỆT ĐỒ THỊ

NỘI DUNG BÀI HỌC

Thực hành: Bài toán Phân nhóm người nghi nhiễm COVID-19

Luyện tập

Vận dụng

THỰC HÀNH: BÀI TOÁN

PHÂN NHÓM NGƯỜI

NGHI NHIỄM COVID-19

Thảo luận nhóm

Bài toán Phân nhóm người nghi nhiễm COVID-19

Một nhóm gồm 7 người được đánh số từ 0 đến 6, có một số cặp người thường xuyên tiếp xúc trao đổi với nhau được mô tả như trong Hình 1.

Một ngày, người 0 xét nghiệm và được xác định là bị nhiễm COVID-19, người ta cần phân 7 người thành các nhóm, người 0 sẽ thuộc nhóm F0, những người tiếp xúc với người ở nhóm F0 sẽ được xếp vào nhóm F1, những người tiếp xúc với người ở nhóm F1 sẽ được xếp vào nhóm F2,…

Hình 1. Nhóm gồm 7 người và mối quan hệ thường xuyên tiếp xúc

Thảo luận nhóm

Hình 2. Trạng thái ở bước 1

Hình 3. Trạng thái ở bước 2

Hình 4. Trạng thái ở bước 3

Nhiệm vụ: Dùng thuật toán duyệt đồ thị theo chiều rộng bắt đầu từ người 0 để phân nhóm người nghi nhiễm COVID-19.

GỢI Ý:

Dùng mảng hàng đợi Q để thăm các đỉnh theo chiều rộng, mảng level để ghi nhận nhóm nghi nhiễm, Hình 2, 3, 4 mô tả ba bước đầu tiên trong quá trình thực hiện.

Quá trình thực hiện phân nhóm người nghi nhiễm COVID-19:

Bài toán Phân nhóm người nghi nhiễm COVID-19

Quá trình thực hiện phân nhóm người nghi nhiễm COVID-19:

Bài toán Phân nhóm người nghi nhiễm COVID-19

Bước 5:

Bước 7:

Bước 6:

Bước 8:

LUYỆN TẬP

Cho đồ thị như hình. Nếu thực hiện duyệt theo chiều sâu bắt đầu từ đỉnh A thì thứ tự các đỉnh được duyệt sẽ như thế nào?

♦ Bước 1: Thực hiện DFS(A), đánh dấu đỉnh A đã thăm và thêm đỉnh A vào ngăn xếp; chỉ có B là đỉnh kề của đỉnh A và đỉnh B chưa được thăm, gọi DFS(B).

visited

Stack

♦ Bước 2: Thực hiện DFS(B), đánh dấu đỉnh B đã thăm và thêm đỉnh B vào ngăn xếp. Có hai đỉnh C, H kề với B và đều chưa được thăm, theo thứ tự DFS(C) được gọi và thực hiện trước.

visited

Stack

♦ Bước 3: Thực hiện DFS(C), đánh dấu đỉnh C đã thăm và thêm đỉnh C vào ngăn xếp. Có hai đỉnh D, E kề với C và đều chưa được thăm, theo thứ tự DFS(D) được gọi và thực hiện trước.

visited

Stack

♦ Bước 4: Thực hiện DFS(D), đánh dấu đỉnh D đã thăm và thêm đỉnh D vào ngăn xếp.

visited

Stack

• Do đã xét hết đỉnh kề của đỉnh D nên DFS(D) kết thúc. Lấy đỉnh D ra khỏi ngăn xếp.

Stack

♦ Bước 5: Quay về DFS(C), xét E là đỉnh kề tiếp theo của đỉnh C; vì đỉnh E chưa được thăm nên gọi DFS(E).

• Thực hiện DFS(E), đánh dấu đỉnh E đã thăm và thêm đỉnh E vào ngăn xếp. Có ba đỉnh F, G, H kề với E và đều chưa được thăm, theo thứ tự DFS(F) được gọi và thực hiện trước.

visited

Stack

♦ Bước 6: Thực hiện DFS(F), đánh dấu đỉnh F đã thăm và thêm đỉnh F vào ngăn xếp.

--------------------------------------

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