Code Thuật Toán Tìm Kiếm Theo Chiều Rộng

Giải thuật kiếm tìm kiếm theo chiều rộng là gì?

Giải thuật kiếm tìm kiếm theo chiều rộng lớn (Breadth First search – viết tắt là BFS) duyệt sang 1 đồ thị theo chiều rộng lớn và sử dụng hàng hóng (queue) để ghi ghi nhớ đỉnh ngay cạnh để bắt đầu việc tìm kiếm lúc không gặp được đỉnh liền kề 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ụ trên, giải mã tìm kiếm theo chiều rộng để mắt từ A tới B cho tới E tới F sau đó tới C, cho tới G và ở đầu cuối tới D. Giải thuật này tuân theo qui tắc:

Qui tắc 1: chu đáo tiếp tới đỉnh gần cạnh mà chưa được duyệt. Đánh dấu đỉnh mà đã được duyệt. Hiển thị đỉnh đó và đẩy vào vào một hàng ngóng (queue)..

Qui tắc 2: Nếu không tìm kiếm thấy đỉnh ngay thức thì kề, thì xóa đỉnh thứ nhất trong hàng đợi.

Qui tắc 3: tái diễn Qui tắc 1 cùng 2 cho tới khi hàng hóng là trống.

Bảng sau đây minh họa cách lời giải tìm tìm theo chiều rộng thao tác với một ví dụ đơn giản dễ dàng sau:

BướcDuyệtMô tả
1.
*
Khởi chế tạo ra hàng ngóng (queue)
2.
*
Chúng ta ban đầu duyệt đỉnh S (đỉnh bắt đầu) và ghi lại đỉnh này là đã duyệt.
3.
*
Sau đó bọn họ tìm đỉnh sát với Smà không được duyệt. Trong lấy ví dụ như này bọn họ có 3 đỉnh, với theo máy tự chữ cái chúng ta chọn đỉnh A khắc ghi là đã chu đáo và xếp A vào sản phẩm đợi.

Xem thêm: Tủ Lạnh Vẫn Chạy Nhưng Không Đông Đá ? Nguyên Nhân Và Cách Chữa

4.
*
Tiếp tục lưu ý đỉnh liền kề với SB. Đánh vệt là đã chú ý và xếp đỉnh này vào mặt hàng đợi.
5.
*
Tiếp tục chú ý đỉnh sát với SC. Đánh dấu là đã chú ý và xếp đỉnh này vào mặt hàng đợi.
6.
*
Bây giờ đồng hồ đỉnh S không hề đỉnh nào gần kề mà không được duyệt. Hiện nay chúng ta rút A từ mặt hàng đợi.
7.
*
Từ đỉnh A bọn họ có đỉnh liền kề là D cùng là đỉnh chưa được duyệt. Đánh vệt đỉnh D là đã để ý và xếp vào sản phẩm đợi.

Đến đây, họ thấy rằng không thể đỉnh như thế nào là chưa được đánh dấu (chưa được chú ý với lấy ví dụ như trong bảng này). Nhưng lời giải vẫn tiếp tục, bọn họ vẫn liên tục rút những đỉnh trường đoản cú hàng chờ theo trang bị tự để tìm toàn bộ các đỉnh mà chưa được duyệt. Lúc hàng đợi là trống thì chính là lúc xong giải thuật.


giải mã tìm tìm theo chiều sâu (Depth First Search)
học tập lập trình C/C++