Thuật toán Breadth First Search (BFS) đi qua một đồ thị theo chuyển động rộng và sử dụng một hàng đợi để ghi nhớ đỉnh tiếp theo để bắt đầu tìm kiếm, khi một ngõ cụt xảy ra trong bất kỳ lần lặp nào.
Như trong ví dụ đã nêu ở trên, thuật toán BFS đi qua từ A đến B đến E đến F trước rồi đến C và G cuối cùng đến D. Nó sử dụng các quy tắc sau.
- Quy tắc 1 - Ghé thăm đỉnh không mong muốn liền kề. Đánh dấu nó như đã truy cập. Hiển thị nó. Chèn nó vào hàng đợi
- Quy tắc 2 - Nếu không tìm thấy đỉnh liền kề, hãy xóa đỉnh đầu tiên khỏi hàng đợi.
- Quy tắc 3 - Lặp lại quy tắc 1 và quy tắc 2 cho đến khi hàng đợi trống.
Ở giai đoạn này, chúng ta không còn các nút không được đánh dấu (không được đánh dấu). Nhưng theo thuật toán, chúng tôi tiếp tục thực hiện để có được tất cả các nút không mong muốn. Khi hàng đợi được làm trống, chương trình kết thúc.
Được cập nhật: 16 tháng 4 lúc 14:22:02 | Lượt xem: 450
