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

Hoạt động 1

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:

- Mức 0: Bản thân đỉnh 0.

- Mức 1: Các đỉnh kề với đỉnh mức 0.

- Mức 2: Các đỉnh là kề với đỉnh mức 1. Đỉnh mức 2 là các đỉnh mà tồn tại đường đi từ đỉnh 0 đến đỉnh này theo 2 cạnh, qua đỉnh mức 1.

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.

Câu hỏi 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?

Câu hỏi 1: Thứ tự các đỉnh có trong danh sách đỉnh kề Adj có ảnh hưởng đến thứ tự các đỉnh được đánh dấu trong thuật toán duyệt theo chiều rộng hay không?

Luyện tập

1. Viết lại hàm BFS() in ra các đỉnh đã duyệt. Áp dụng vào đồ thị trong bài để kiểm tra thứ tự các đỉnh đã duyệt có đúng như phần mô phỏng thủ công các hoạt động trên không.

Vận dụng

1. Cho đơn đồ thị vô hướng G = (V, E). Sử dụng thuật toán duyệt theo chiều rộng BFS, viết chương trình kiểm tra xem G có chu trình hay không. Chu trình (cycle) ở đây được hiểu là một đường đi khép kín, đỉnh xuất phát trùng với đỉnh kết thúc. Cần thiết lập hàm dạng Acycle(G), hàm trả lại True nếu G không có chu trình, ngược lại hàm trả lại False.