Giáo án điện tử chuyên đề Khoa học máy tính 12 kết nối Bài 16: Kĩ thuật duyệt đồ thị theo chiều rộng

CHÀO MỪNG CÁC EM ĐẾN VỚI BUỔI HỌC NGÀY HÔM NAY!

KHỞI ĐỘNG

Chúng ta đã làm quen với thuật toán duyệt đồ thị theo chiều sâu, quá trình duyệt đi “sâu” nhất có thể theo các cạnh của đồ thị. Ngoài ra còn có cách duyệt đồ thị theo chiều rộng, được hình dung như khi đổ nước xuống một sàn nhà phẳng, nước sẽ lan toả ra xung quanh theo các hình tròn đồng tâm. Cách duyệt theo chiều rộng có thể được mô phỏng như Hình 16.1a.

a)

b)

Hình 16.1. Duyệt đồ thị lan toả theo các mức

Giả sử ta bắt đầu duyệt từ đỉnh 0 của đồ thị Hình 16.1b theo chiều rộng. Theo em, chúng ta sẽ duyệt các đỉnh theo nguyên tắc nào và duyệt theo thứ tự nào?

Thứ tự duyệt:

- Bắt đầu từ đỉnh 0, thăm tất cả các đỉnh kề với đỉnh 0.

- Duyệt qua các đỉnh kề với các đỉnh đã thăm theo thứ tự từ hàng đợi.

- Tiếp tục quá trình này cho đến khi tất cả các đỉnh đều được thăm.

Nguyên tắc duyệt:

- Duyệt tất cả các đỉnh kề với đỉnh hiện tại trước khi chuyển sang đỉnh kề tiếp theo.

- Sử dụng hàng đợi (queue) để lưu trữ thứ tự duyệt.

BÀI 16: KĨ THUẬT DUYỆT ĐỒ THỊ THEO CHIỀU RỘNG

6th Grade

NỘI DUNG BÀI HỌC

Thuật toán duyệt đồ thị theo chiều rộng (BFS – Breadth First Search)

Ý tưởng duyệt đồ thị theo chiều rộng

01

02

PHẦN 1.

Ý TƯỞNG DUYỆT ĐỒ THỊ THEO CHIỀU RỘNG

Hoạt động 1. Làm quen ý tưởng của thuật toán duyệt đồ thị theo chiều rộng

Bảng 16.1. Duyệt các đỉnh theo mức

Các đỉnh được duyệt là:

0 1 2 6 9 3 4 7 8 10 5

Em hãy trình bày các bước duyệt đồ thị theo chiều rộng bắt đầu từ đỉnh s bất kì.

Việc duyệt đồ thị theo chiều rộng được bắt đầu từ đỉnh s bất kì. Thực hiện lần lượt theo các đỉnh cùng mức 0, 1, 2,…

Đỉnh mức 0 chính là s.

Mức 1 bao gồm các đỉnh kề với s.

Mức k sẽ bao gồm các đỉnh kề với đỉnh mức k − 1, tức là có tồn tại đường đi k cạnh từ đỉnh s.

Cho trước hai đỉnh s và f:

Nếu tồn tại đường đi k cạnh từ s đến f và k là số nhỏ nhất thì ta nói f có khoảng cách k đến đỉnh s.

Nếu không có đường đi từ s đến f thì ta nói khoảng cách từ s đến f là ∞ (vô cùng).

Nếu từ đỉnh s có nhiều đường đi đến đỉnh f thì khoảng cách được hiểu là đường đi ngắn nhất (ít cạnh nhất) trong số các đường đi.

• Ý tưởng của thuật toán duyệt theo chiều rộng có thể như sau:

Với đỉnh s bất kì, ý tưởng của thuật toán duyệt đồ thị theo chiều rộng xuất phát từ đỉnh s là sẽ lần lượt duyệt các đỉnh theo từng mức hay theo khoảng cách từ đỉnh s đến đỉnh được duyệt.

Củng cố kiến thức

Câu 1: Mệnh đề sau đúng hay sai?

Giả sử gọi BFS(Adj,s) là chương trình duyệt đồ thị theo chiều rộng bắt đầu từ đỉnh s. Khi đó với mọi đỉnh v thuộc V, hàm BFS(Adj,s) sẽ duyệt qua đỉnh v khi và chỉ khi tồn tại đường đi từ s đến v.

Có.

a) Các đỉnh kề với đỉnh a là b, c.

b) Khoảng cách từ a đến e là 3 (đi qua các đỉnh c, h, e).

c) Thứ tự duyệt các đỉnh từ a sẽ là: a, b, c, d, f, h, e, g.

Câu 2: Trả lời các câu hỏi dựa trên đồ thị Hình 16.2.

a) Các đỉnh kề với a là đỉnh nào?

b) Khoảng cách từ đỉnh a đến e là bao nhiêu?

c) Nếu thực hiện duyệt đồ thị theo chiều rộng bắt đầu từ đỉnh a thì thứ tự các đỉnh được duyệt có thể như thế nào?

PHẦN 2.

THUẬT TOÁN DUYỆT ĐỒ THỊ THEO CHIỀU RỘNG (BFS – BREADTH FIRST SEARCH)

Hoạt động 2. Tìm hiểu thuật toán duyệt đồ thị theo chiều rộng

Thuật toán duyệt đồ thị theo chiều rộng được thiết kế gần giống như bản không đệ quy của duyệt đồ thị theo chiều sâu, sự khác biệt chỉ là thay thế công cụ ngăn xếp bằng hàng đợi (hoạt động theo cơ chế “vào trước, ra trước” – FIFO).

Tìm hiểu, thảo luận về cách cài đặt thuật toán duyệt theo chiều rộng.

Thuật toán chính là hàm BFS(Adj,s) thiết lập duyệt theo chiều rộng bắt đầu từ đỉnh s:

Mảng mark[] dùng để đánh dấu các đỉnh đã duyệt.

Ban đầu cần thiết lập mark[v] = False với mọi đỉnh v.

Giải thích

Hàm được thiết lập để duyệt bắt đầu từ đỉnh s chưa được đánh dấu.

Khi bắt đầu, hàng đợi Q được thiết lập và s được đưa vào Q tại dòng 2 và 3.

Thao tác duyệt theo chiều rộng được thực hiện tại vòng lặp 4. Vòng lặp này sẽ thực hiện cho đến khi Q rỗng.

Lần lượt lấy v ra khỏi Q, nếu v chưa được đánh dấu thì đánh dấu v và đưa các đỉnh kề của v vào hàng đợi Q.

Lập luận tương tự với DFS, ta tính được độ phức tạp thời gian của thuật toán BFS là:

O(V+2E) nếu G là đồ thị vô hướng.

O(V+E) nếu đồ thị G có hướng.

Ví dụ:

Mô phỏng thủ công thuật toán trên với đồ thị Hình 16.3.

Hình 16.3. Đồ thị và dữ liệu danh sách kề

Hình 16.2. Chi tiết các bước duyệt theo BFS

• Các thông tin được ghi lại là hàng đợi Q, đỉnh v = dequeue() tại dòng 5 và đỉnh được đánh dấu tại dòng 7.
• Các đỉnh in đậm là mới được bổ sung vào hàng đợi, các đỉnh này là đỉnh kề của đỉnh vừa được đánh dấu ở hàng trên.

• Thiết lập hàm thực hiện thuật toán duyệt theo chiều rộng trên toàn bộ đồ thị G. Nếu bộ dữ liệu đầu vào của đồ thị là (V, Adj) thì hàm duyệt sẽ có dạng BFS_Traversal(V,Adj).
• Đoạn chương trình mô tả phần thiết lập thông tin ban đầu của đồ thị, sau đó thực hiện thuật toán duyệt theo chiều rộng trên toàn bộ đồ thị G.

Củng cố kiến thức

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