Giáo án điện tử chuyên đề Khoa học máy tính 12 chân trời Bài 3.3: Duyệt đồ thị theo chiều rộng

CHÀO MỪNG

CÁC EM ĐẾN BUỔI HỌC NÀY!

KHỞI ĐỘNG

Bản đồ giao thông kết nối 8 địa điểm nổi tiếng được mô tả như đồ thị G, (Hình 1). Theo em, có tồn tại một hành trình đi từ địa điểm D đến địa điểm G sao cho phải đi qua ít địa điểm trung gian nhất không? Chỉ ra hành trình đó.

Đường đi D-C-E-G là ngắn nhất.

CHỦ ĐỀ 3. TÌM HIỂU KĨ THUẬT

DUYỆT ĐỒ THỊ VÀ ỨNG DỤNG

BÀI 3.3. DUYỆT ĐỒ THỊ

THEO CHIỀU RỘNG

NỘI DUNG BÀI HỌC

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

Thuật toán duyệt đồ thị theo chiều rộng

1

2

DUYỆT ĐỒ THỊ

THEO CHIỀU RỘNG

1

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

Câu 1: Định nghĩa thuật toán duyệt đồ thị theo chiều rộng (BFS) là gì?

Câu 2: Ưu điểm chính của thuật toán BFS là gì?

Câu 3: Trình bày các bước cơ bản để thực hiện thuật toán BFS.

Thuật toán duyệt qua tất cả các đỉnh của đồ thị và mỗi đỉnh chỉ được duyệt đúng một lần.

Duyệt theo từng lớp: duyệt hết các đỉnh kề với đỉnh bắt đầu trước khi duyệt đến các đỉnh ở lớp tiếp theo.

BFS

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

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

Ưu điểm

Tìm đường đi ngắn nhất (về số cạnh) từ một đỉnh đến tất cả các đỉnh khác trong đồ thị.

Có thể được sử dụng để tìm các thành phần liên thông của đồ thị.

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

Các bước cơ bản để thực hiện thuật toán BFS

• Bắt đầu từ một đỉnh nguồn.
• Thêm đỉnh nguồn vào hàng đợi (Queue).
• Lặp lại các bước sau cho đến khi hàng đợi rỗng:
• Lấy một đỉnh từ đầu hàng đợi.
• Duyệt tất cả các đỉnh kề với đỉnh vừa lấy ra và thêm chúng vào hàng đợi (nếu chúng chưa được duyệt).

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

1. Trong bảng minh họa, thuật toán BFS bắt đầu từ đỉnh nào của đồ thị G1?

2. Hàng đợi (Queue) dùng để làm gì trong quá trình duyệt BFS?

3. Tại bước thứ 3 của bảng minh họa, đỉnh nào được lấy ra khỏi hàng đợi và các đỉnh nào được thêm vào? Vì sao?

4. Tại sao ở bước 5b, khi đỉnh A được lấy ra khỏi hàng đợi, không có đỉnh nào được thêm vào?

5. Thứ tự duyệt các đỉnh của đồ thị G1 khi thực hiện BFS từ đỉnh D là gì?

Quan sát bảng minh họa SGK tr.59-61 và trả lời câu hỏi.

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

Thuật toán BFS bắt đầu từ đỉnh D của đồ thị G1.

Duyệt đỉnh D và thêm đỉnh D vào hàng đợi.

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

Hàng đợi dùng để lưu trữ các đỉnh đang chờ được duyệt. Các đỉnh được thêm vào hàng đợi theo thứ tự duyệt của thuật toán.

Lấy đỉnh D ra khỏi hàng đợi, đỉnh C kế với D chưa được duyệt. Duyệt đỉnh C và thêm C vào hàng đợi.

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

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

Đỉnh C được lấy ra. Các đỉnh B và E được thêm vào vì chúng là các đỉnh kề với C và chưa được duyệt.

Lấy đỉnh B ra khỏi hàng đợi, các đỉnh kề với B chưa được duyệt là A và H. Duyệt A và H, thêm A và H vào hàng đợi.

Ở bước 5b, khi đỉnh A được lấy ra khỏi hàng đợi, không có đỉnh nào được thêm vào vì không có đỉnh nào kề với A mà chưa được duyệt.

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

Thứ tự duyệt các đỉnh của đồ thị G1 khi thực hiện BFS từ đỉnh D:

D, C, B, E, A, H, F, G

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

Nhận xét: Cách duyệt đồ thị theo chiều rộng như trên → cách đi từ đỉnh D tới đỉnh G mà phải qua ít đỉnh trung gian nhất.

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

Hãy cho biết thứ tự duyệt các đỉnh với phương pháp duyệt đồ thị theo chiều rộng xuất phát từ đỉnh X của đồ thị G2 ở hình 2.

X, C, D, H, B, A, F, K, E, G

CÂU HỎI (SGK TR.61)

Hình 2. Đồ thị G2

THUẬT TOÁN DUYỆT

ĐỒ THỊ THEO

CHIỀU RỘNG

2

2. Thuật toán duyệt đồ thị theo chiều rộng

Thuật toán duyệt đồ thị theo chiều rộng

2. Thuật toán duyệt đồ thị theo chiều rộng

Khi đó, thủ tục thực hiện duyệt đồ thị G = (V, E) theo chiều rộng như sau:

Ý tưởng chính của thuật toán BFS

• BFS sử dụng hàng đợi (queue) để lưu trữ các đỉnh trong quá trình duyệt.
• Thuật toán bắt đầu từ một đỉnh u chưa được duyệt của đồ thị.
• Đỉnh u được thêm vào hàng đợi.
• Sau đó, đỉnh u được lấy ra khỏi hàng đợi, duyệt các đỉnh kề với u mà chúng chưa được duyệt và thêm các đỉnh này vào hàng đợi.
• Quá trình này lặp lại cho đến khi hàng đợi rỗng.

GIẢI THÍCH:

GIẢI THÍCH:

• Dòng 01: Chú thích, cho biết rằng thủ tục (function) này sẽ duyệt đồ thị G bắt đầu từ đỉnh u.
• Dòng 02: Định nghĩa một thủ tục (function) có tên là bft (viết tắt của “Breadth-First Traversal”), nhận vào một đồ thị G và một đỉnh u làm đầu vào.
• Dòng 03: Tạo một hàng đợi (queue) có tên là Q. Hàng đợi này sẽ được sử dụng để lưu trữ các đỉnh cần được duyệt.
• Dòng 04: Đánh dấu đỉnh u là đã được duyệt (visited). Điều này giúp tránh việc duyệt lại cùng một đỉnh nhiều lần.

GIẢI THÍCH:

• Dòng 05: Thêm đỉnh u vào hàng đợi Q.
• Dòng 06: Bắt đầu một vòng lặp while. Vòng lặp này sẽ tiếp tục cho đến khi hàng đợi Q trở nên rỗng.
• Dòng 07: Lấy (dequeue) đỉnh đầu tiên ra khỏi hàng đợi Q và gán biến u.
• Dòng 08: “Xử lý” đỉnh u. Tùy thuộc vào bài toán cụ thể, bạn có thể thực hiện các thao tác khác nhau trên đỉnh u ở bước này (ví dụ: in ra tên đỉnh, tính toán một giá trị liên quan đến đỉnh,...).
• Dòng 09: Chú thích, cho biết các dòng tiếp theo sẽ thêm các đỉnh kề của đỉnh u vào hàng đợi Q.

GIẢI THÍCH:

• Dòng 10: Bắt đầu một vòng lặp for. Vòng lặp này sẽ duyệt qua tất cả các đỉnh v thuộc tập đỉnh kề của đỉnh u.
• Dòng 11: Kiểm tra xem đỉnh v đã được duyệt hay chưa.
• Dòng 12: Nếu đỉnh v chưa được duyệt, đánh dấu đỉnh v là đã được duyệt.
• Dòng 13: Thêm đỉnh v vào hàng đợi Q.

GIẢI THÍCH:

• Dòng 01: Chú thích, cho biết thủ tục này sẽ duyệt đồ thị G theo chiều rộng.
• Dòng 02: Định nghĩa một thủ tục có tên là bfs, nhận vào một đồ thị G làm đầu vào.

GIẢI THÍCH:

• Dòng 03: Chú thích, cho biết các dòng tiếp theo sẽ đánh dấu tất cả các đỉnh của đồ thị là chưa được duyệt.
• Dòng 04: Bắt đầu một vòng lặp for. Vòng lặp này sẽ duyệt qua tất cả các đỉnh u thuộc đồ thị G.
• Dòng 05: Đánh dấu đỉnh u là chưa được duyệt.
• Dòng 06: Chú thích, cho biết các dòng tiếp theo sẽ duyệt các đỉnh của đồ thị G.

GIẢI THÍCH:

• Dòng 07: Bắt đầu một vòng lặp for. Vòng lặp này sẽ duyệt qua tất cả các đỉnh u thuộc đồ thị G.
• Dòng 08: Kiểm tra xem đỉnh u đã được duyệt hay chưa.
• Dòng 09: Nếu đỉnh u chưa được duyệt, gọi thủ tục bft (đã định nghĩa ở trên) để duyệt đồ thị bắt đầu từ đỉnh u.

CÂU HỎI (SGK TR.62)

Cho đồ thị G₁ (trong Hình 1). Hãy thực hiện các yêu cầu sau:

a. Dùng thuật toán duyệt đồ thị theo chiều rộng để tìm đường đi ngắn nhất từ đỉnh C đến tất cả các đỉnh của đồ thị.

b. Từ câu a, mô tả cách duyệt cây theo chiều rộng bắt đầu từ đỉnh C.

CÂU HỎI (SGK TR.62)

• Sử dụng thuật toán duyệt đồ thị theo chiều rộng bắt đầu từ đỉnh C, xây dựng được cây như Hình 1.
• Từ cây này, đường đi xuất phát từ C tới các đỉnh chính là đường đi ngắn nhất từ C tới các đỉnh đó.
• VD một cách duyệt cây theo chiều rộng bắt đầu từ đỉnh C: C, B, D, E, A, H, F, G.

Thuật toán duyệt đồ thị theo chiều rộng sử dụng hàng đợi để lưu các đỉnh trong quá trình duyệt. Giả sử quá trình duyệt bắt đầu từ một đỉnh u chưa được duyệt của đồ thị. Ban đầu, duyệt đỉnh u và thêm đỉnh u vào hàng đợi. Sau đó, lấy đỉnh u ra khỏi hàng đợi, duyệt các đỉnh kề của đỉnh u mà chúng chưa được duyệt và thêm các đỉnh này vào hàng đợi.

GHI NHỚ

LUYỆN TẬP

Câu 1: Thuật toán duyệt đồ thị theo chiều rộng (BFS) sử dụng cấu trúc dữ liệu nào để lưu trữ các đỉnh trong quá trình duyệt?

A. Stack (ngăn xếp)

C. Linked List

(danh sách liên kết)

B. Queue (hàng đợi)

D. Tree (cây)

B. Queue (hàng đợi)

Câu 2: Trong thuật toán BFS, đỉnh nào được xử lý trước?

A. Đỉnh mới được thêm vào hàng đợi gần nhất.

C. Đỉnh được thêm vào

hàng đợi lâu nhất.

B. Đỉnh có bậc lớn nhất.

D. Đỉnh có bậc nhỏ nhất.

C. Đỉnh được thêm vào

hàng đợi lâu nhất.

Câu 3: Giả sử bạn đang duyệt đồ thị theo chiều rộng,

bắt đầu từ đỉnh A. Đỉnh B kề với A và chưa được duyệt. Điều gì xảy ra tiếp theo?

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