Bài 16. Kĩ thuật duyệt đồ thị theo chiều rộng
KĨ THUẬT DUYỆT ĐỒ THỊ THEO CHIỀU RỘNG
Sau bài học này em sẽ:
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.
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?
1. Ý tưởng
Hoạt động 1. Làm quen với duyệt đồ thị theo chiều rộng
Thực hiện công việc duyệt theo chiều rộng của đồ thị Hình 16.1b, bắt đầu từ đỉnh 0. Các bước thực hiện sẽ duyệt các đỉnh theo trình tự sau:
Quá trình cứ tiếp tục như vậy cho đến khi không thể duyệt thêm được nữa.
Trao đổi, thảo luận nhóm để nhận biết sự khác biệt giữa hai phương pháp duyệt đồ thị theo chiều sâu và chiều rộng khác nhau như thế nào.
Thiết lập bảng sau và điền các thông tin vào các cột: các đỉnh được duyệt theo chiều rộng, xuất phát từ đỉnh 0.
Như vậy nếu duyệt theo cách trên thì thứ tự các đỉnh được duyệt là:
| Mức | Các đỉnh được duyệt | Ghi chú |
| 0 | 0 | Mức 0 chỉ có đúng phần tử ban đầu 0 |
| 1 26 9 | Các đỉnh kề của 0 | |
| 2 | 3 4 7 8 | Các đỉnh kề với các đỉnh mức 1 (nhung không nằm trong mức 0 và 1), tức là có đường đi qua 2 canh xuất phát từ 0. |
| 3 | 10 | Đường đi từ 0: 0 ~ 6 ~ 4 ~ 10 Lưu ý: Có cách đi khác từ 0 đến 10 qua 4 cạnh nhưng chúng ta không chọn (0, 2, 3, 4, 10). |
| 4 | 5 | |
| 5 | <không có> | Dừng tim kiếm |
Theo cách trên, 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 mức 0. Đỉ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.
Nếu f là đỉnh ở mức k 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.
Lưu ý: 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.
Như vậy ý tưởng của thuật toán duyệt theo chiều rộng có thể như sau:
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.
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
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 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ế ngăn xếp bằng hàng đợi. Cụ thể, 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.
Hàm chính duyệt theo chiều rộng được mô tả như sau:
def BFS(Adj, s):
Q = Queue()
enqueue(Q, s)
while not isEmptyQueue(Q):
v = dequeue(Q)
if not mark[v]:
mark[v] = True # Đánh dấu đỉnh v
for u in Adj[v]:
enqueue(Q, u)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 O(V+E) nếu đồ thị G có hướng.
Mô phỏng thủ công thuật toán trên với đồ thị Hình 16.3 có thể như sau.
Bảng 16.2 sẽ mô tả lại dữ liệu được cập nhật theo từng bước của vòng lặp tại dòng 4. 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.
Thứ tự các đỉnh đã đánh dấu: 0 1 2 6 9 7 8 3 4 10 5.
| STT | Queue | Dequeue | Mark | Trang thái |
| 0 | 0 | Đánh dấu 0 | ||
| 2 | 1 2 6 9 | Đánh dấu 1 | ||
| 3 | 2,6, 9 0, 7, 8 | 2 | 2 | Đánh dấu 2 |
| 4 | 6, 9,0, 7,8, 0, 3 | 6 | 6 | Đánh dấu 6 |
| 5 | 9 | 9 | Đánh dấu 9 | |
| 6 | ||||
| 7 | 7,8,0, 3,0, 4, 0 | 7 | Đánh dấu 7 | |
| 8 | 8,0, 3, 0, 4, 0,1 | 8 | 8 | Đánh dấu 8 |
| 9 | 0 | |||
| 10 | 3,0, 4, 0, 1,1 | 3 | 3 | Đánh dấu 3 |
| 11 | 0 | |||
| 12 | 4, 0, 1,1, 2,4 | Đánh dấu 4 | ||
| 13 | 0, 1,1, 2,4, 3, 6, 10 | |||
| 14 | ||||
| 15 | ||||
| 16 | 2,4, 3, 6,10 | |||
| 17 | 4, 3,6 10 | |||
| 18 | 3,6,10 | 3 | ||
| 19 | 6, 10 | 6 | ||
| 20 | 10 | 10 | 10 | Đánh dấu 10 |
| 21 | 4 5 | 4 | ||
| 22 | 5 | 5 | 5 | Đánh dấu 5 |
| 23 | 10 | 10 | ||
| 24 | <rỗng> |
Chúng ta sẽ 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):
def BFS_Traversal(V, Adj):
mark = [False] * len(V)
for s in V:
if not mark[s]:
BFS(Adj, s)Đoạn chương trình sau 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:
from Queue import *
fname = input()
V, Adj = BuildGraph(fname)
BFS_Traversal(V, Adj)Thuật toán duyệt đồ thị theo chiều rộng bắt đầu tại đỉnh s sẽ lần lượt duyệt các đỉnh.
Thuật toán BFS có cấu trúc điều khiển tương tự như thuật toán duyệt không đệ quy theo chiều sâu DFS, trong đó sử dụng hàng đợi thay thế cho ngăn xếp.
