Giải thuật tra cứu kiếm theo chiều rộng là gì?
Giải thuật search kiếm theo chiều rộng (Breadth First tìm kiếm – viết tắt là BFS) duyệt qua một đồ thị theo chiều rộng lớn và thực hiện hàng chờ (queue) nhằm ghi ghi nhớ đỉnh liền kề để bắt đầu việc tìm kiếm lúc không gặp được đỉnh sát trong bất kỳ vòng lặp nào.
Bạn đang xem: Code thuật toán tìm kiếm theo chiều rộng
Như vào hình lấy ví dụ như trên, giải mã tìm tìm theo chiều rộng để mắt tới từ A cho tới B cho tới E tới F tiếp nối tới C, tới G và sau cùng tới D. Giải mã này theo đúng qui tắc:
Qui tắc 1: chú tâm tiếp tới đỉnh cạnh bên mà chưa được duyệt. Đánh lốt đỉnh nhưng mà đã được duyệt. Hiển thị đỉnh đó và đẩy vào trong một hàng hóng (queue)..
Qui tắc 2: Nếu không kiếm thấy đỉnh tức khắc kề, thì xóa đỉnh đầu tiên trong hàng đợi.
Qui tắc 3: lặp lại Qui tắc 1 cùng 2 cho tới khi hàng ngóng là trống.
Bảng sau đâ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 và dễ dàng sau:
| 1. |  | Khởi tạo nên hàng ngóng (queue) |
| 2. |  | Chúng ta ban đầu duyệt đỉnh S (đỉnh bắt đầu) và khắc ghi đỉnh này là đã duyệt. |
| 3. |  | Sau đó chúng ta tìm đỉnh gần kề với Smà chưa được duyệt. Trong ví dụ này chúng ta có 3 đỉnh, và theo máy tự chữ cái họ chọn đỉnh A ghi lại là đã lưu ý và xếp A vào hàng đợi. |
| 4. |  | Tiếp tục ưng chuẩn đỉnh gần kề với S là B. Đánh vết là đã duyệt y và xếp đỉnh này vào hàng đợi. |
| 5. |  | Tiếp tục chăm bẵm đỉnh gần cạnh với S là C. Đánh vết là đã duyệt và xếp đỉnh này vào mặt hàng đợi. |
| 6. |  | Bây giờ đỉnh S không còn đỉnh nào gần cạnh mà không được duyệt. Hiện nay chúng ta rút A từ hàng đợi. |
| 7. |  | Từ đỉnh A chúng ta có đỉnh cạnh bên là D với là đỉnh không được duyệt. Đánh dấu đỉnh D là đã lưu ý và xếp vào mặt hàng đợi. Xem thêm: Ứng Dụng Công Nghệ Gen Trong Tạo Giống Bằng Công Nghệ Gen Hay, Chi Tiết |
Đến đây, bọn họ thấy rằng không còn đỉnh làm sao là chưa được đánh dấu (chưa được để ý với lấy một ví dụ trong bảng này). Nhưng lời giải vẫn tiếp tục, chúng ta vẫn liên tục rút các đỉnh từ bỏ hàng ngóng theo đồ vật tự để tìm tất cả các đỉnh mà không được duyệt. Khi hàng hóng là trống thì chính là lúc dứt giải thuật.
giải mã tìm tìm theo chiều sâu (Depth First Search)
học lập trình C/C++