Giải thuật tìm kiếm theo chiều rộng
Giải thuật tìm kiếm theo chiều rộng là gì?
Giải thuật tìm kiếm theo chiều rộng (Breadth First Search – viết tắt là BFS) duyệt qua một đồ thị theo chiều rộng và sử dụng hàng đợi (queue) để ghi nhớ đỉnh liền kề để bắt đầu việc tìm kiếm khi không gặp được đỉnh liền kề trong bất kỳ vòng lặp nào.
Như trong hình ví dụ trên, giải thuật tìm kiếm theo chiều rộng duyệt từ A tới B tới E tới F sau đó tới C, tới G và cuối cùng tới D. Giải thuật này tuân theo qui tắc:
Qui tắc 1: Duyệt tiếp tới đỉnh liền kề mà chưa được duyệt. Đánh dấu đỉnh mà đã được duyệt. Hiển thị đỉnh đó và đẩy vào trong một hàng đợi (queue)..
Qui tắc 2: Nếu không tìm thấy đỉnh liền kề, thì xóa đỉnh đầu tiên trong hàng đợi.
Qui tắc 3: Lặp lại Qui tắc 1 và 2 cho tới khi hàng đợi là trống.
Bảng dưới đây minh họa cách giải thuật tìm kiếm theo chiều rộng làm việc với một ví dụ đơn giản sau:
Khởi tạo hàng đợi (queue)
Chúng ta bắt đầu duyệt đỉnh S (đỉnh bắt đầu) và đánh dấu đỉnh này là đã duyệt.
Sau đó chúng ta tìm đỉnh liền kề với S mà chưa được duyệt. Trong ví dụ này chúng ta có 3 đỉnh, và theo thứ tự chữ cái chúng ta chọn đỉnh A đánh dấu là đã duyệt và xếp A vào hàng đợi.
Tiếp tục duyệt đỉnh liền kề với S là B. Đánh dấu là đã duyệt và xếp đỉnh này vào hàng đợi.
Tiếp tục duyệt đỉnh liền kề với S là C. Đánh dấu là đã duyệt và xếp đỉnh này vào hàng đợi.
Bây giờ đỉnh S không còn đỉnh nào liền kề mà chưa được duyệt. Bây giờ chúng ta rút A từ hàng đợi.
Từ đỉnh A chúng ta có đỉnh liền kề là D và là đỉnh chưa được duyệt. Đánh dấu đỉnh D là đã duyệt và xếp vào hàng đợi.
Đến đây, chúng ta thấy rằng không còn đỉnh nào là chưa được đánh dấu (chưa được duyệt với ví dụ trong bảng này). Nhưng giải thuật vẫn tiếp tục, chúng ta vẫn tiếp tục rút các đỉnh từ hàng đợi theo thứ tự để tìm tất cả các đỉnh mà chưa được duyệt. Khi hàng đợi là trống thì đó là lúc kết thúc giải thuật.
Theo Tutorialspoint
Bài trước: Giải thuật tìm kiếm theo chiều sâu
Bài tiếp: Cấu trúc dữ liệu cây
Bạn nên đọc
-
Trọng tâm là gì? Công thức tính trọng tâm của tam giác
-
Các công thức đạo hàm và đạo hàm lượng giác đầy đủ nhất
-
Công thức tính đường chéo hình vuông, đường chéo hình chữ nhật
-
Công thức tính diện tích tam giác: vuông, thường, cân, đều
-
Công thức tính tỉ số thể tích các khối đa diện
-
Diện tích hình trụ: Diện tích xung quanh hình trụ, diện tích toàn phần hình trụ
Theo Nghị định 147/2024/ND-CP, bạn cần xác thực tài khoản trước khi sử dụng tính năng này. Chúng tôi sẽ gửi mã xác thực qua SMS hoặc Zalo tới số điện thoại mà bạn nhập dưới đây:

Cũ vẫn chất
-
‘Để giành’ hay ‘để dành’, ‘dành cho’ hay ‘giành cho’, cách viết nào đúng chính tả?
Hôm qua -
Antimalware Service Executable là gì và tại sao nó lại chạy trên máy tính?
Hôm qua -
Cách sửa lỗi 0x0000011b khi in qua mạng trên Windows 10
Hôm qua 12 -
Đáp án Thử Tài Lịch Sử Liên Quân FULL các đáp án, gợi ý
Hôm qua 21 -
11 địa danh bí ẩn bị làm mờ trên Google Maps, điều gì đang bị che giấu?
Hôm qua -
12 giờ trưa là AM hay PM trong tiếng Anh?
Hôm qua 1 -
Cách cài Ubuntu song song với Windows bằng USB
Hôm qua -
Cách chuyển đổi từ Legacy sang UEFI trong BIOS
Hôm qua 4 -
8 cách kiểm tra ổ cứng hiệu quả giúp khám sức khỏe định kỳ của ổ cứng
Hôm qua -
Cách tắt chế độ Secure Boot và mở chế độ Boot Legacy
Hôm qua