Siêu phẩm 30 đề thi thử THPT quốc gia 2024 do thầy cô VietJack biên soạn, chỉ từ 100k trên Shopee Mall.
Quảng cáo
Trả lời:
Thuật toán duyệt theo chiều rộng (Breadth-First Search, BFS) là một thuật toán duyệt hoặc tìm kiếm trên cây hoặc đồ thị. BFS bắt đầu từ một đỉnh gốc và khám phá các đỉnh lân cận trước khi di chuyển đến các đỉnh xa hơn. Đây là một phương pháp duyệt theo tầng (level-order traversal).
Cài đặt thuật toán BFS
Để cài đặt BFS, chúng ta cần sử dụng một hàng đợi (queue) để theo dõi các đỉnh sẽ được thăm tiếp theo. Hàng đợi đảm bảo rằng các đỉnh được thăm theo thứ tự mà chúng được khám phá.
Dưới đây là các bước cơ bản để cài đặt BFS:
- Khởi tạo hàng đợi: Đẩy đỉnh bắt đầu vào hàng đợi và đánh dấu nó đã được thăm.
- Duyệt đỉnh: Lặp lại quá trình sau cho đến khi hàng đợi rỗng:
+ Lấy đỉnh ở đầu hàng đợi ra.
+ Duyệt tất cả các đỉnh kề của đỉnh này. Nếu một đỉnh kề chưa được thăm, đánh dấu nó đã được thăm và đẩy nó vào hàng đợi.
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 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.
Câu 2:
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âu 3:
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 4:
Cho đồ thị Hình 16.4. Nếu thực hiện duyệt theo chiều sâu và chiều rộng bắt đầu từ đỉnh a thì thứ tự các đỉnh được duyệt sẽ như thế nào?
Câu 5:
Viết lại hàm BFS() duyệt theo chiều rộng nhưng sử dụng dữ liệu là ma trận kề A của đồ thị.
Câu 6:
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.12.
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?
Câu 7:
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?
về câu hỏi!