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

CHÀO MỪNG CẢ LỚP

ĐẾN BUỔI HỌC MỚI!

KHỞI ĐỘNG

Có 5 bạn A, B, C, D và E, biết rằng A có số điện thoại của C và D, do đó A có thể liên lạc với C, D; tương tự B có số điện thoại của A; C có số điện thoại của B; D có số điện thoại của C; E có số điện thoại của D. Nếu biểu diễn A, B, C, D, E là các đỉnh của đồ thị và xét mối quan hệ có số điện thoại (có thể liên lạc), ta có đồ thị như Hình 1.

Em hãy cho biết nếu A cần thông báo một thông tin thì những ai có thể nhận được thông tin đó. Câu hỏi tương tự nếu người cần thông báo thông tin là E.

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

• Từ A có thể thông báo cho B, C, D.

• Từ E có thể thông báo cho A, B, C, D.

BÀI 4:

DUYỆT ĐỒ THỊ

NỘI DUNG BÀI HỌC

1

Duyệt đồ thị

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

Duyệt đồ thị theo chiều sâu

1. DUYỆT ĐỒ 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.

1. Duyệt đồ thị

Hai cách duyệt chính

Duyệt theo chiều rộng.

Duyệt theo chiều sâu.

1. Duyệt đồ thị

• 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ì?

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

1. Duyệt đồ thị

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

Bài toán 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.

1. Duyệt đồ thị

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

2. DUYỆT ĐỒ THỊ

THEO CHIỀU RỘNG

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

• Duyệt đồ thị theo chiều rộng (Breadth First Search – 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,…
• 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.

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

Duyệt đồ thị theo chiều rộng sử dụng cấu trúc dữ liệu hàng đợi.

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

Vào trước ra trước (FIFO – First In First Out).

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

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.

• 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?

THẢO LUẬN NHÓM

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

• Để 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ị.

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

Ví dụ

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

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

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.

2

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.

3

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

4

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.

5

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

6

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.

7

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.

8

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.

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

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.

Trả lời phần Khởi động

• Khi duyệt đồ thị theo chiều rộng bắt đầu từ một đỉnh, có thể chưa thăm được hết toàn bộ các đỉnh của đồ thị.
• Để duyệt toàn bộ đồ thị theo chiều rộng, 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.

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

Đỉnh E chưa được thăm.

• 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

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:

Hướng dẫn thực hiện

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.

2

Hướng dẫn thực hiện

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

3

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.

4

Hướng dẫn thực hiện

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

5

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.

6

Hướng dẫn thực hiện

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

7

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.

8

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

9

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.

10

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.

3. DUYỆT ĐỒ THỊ

THEO CHIỀU SÂU

2. Duyệt đồ thị theo chiều sâu

• Duyệt đồ thị theo chiều sâu (Depth First Search – viết tắt là DFS) bắt đầu từ một đỉnh là thực hiện thăm tất cả các đỉnh trong nhánh của đỉnh xuất phát (nhánh của một đỉnh là tập hợp tất cả các đỉnh có thể đến được từ đỉnh đó).
• Việc thăm một nhánh được thực hiện bằng cách đi sâu theo cạnh của đồ thị vào nhánh con chưa được thăm để thăm tất cả các đỉnh trong nhánh đó, rồi quay lại và đi nhánh con tiếp theo.

2. Duyệt đồ thị theo chiều sâu

Duyệt đồ thị theo chiều sâu sử dụng cấu trúc dữ liệu ngăn xếp.

Ngăn xếp hoạt động theo cơ chế gì?

Vào sau ra trước (LIFO – Last In First Out).

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

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