Duyệt đồ thị theo chiều rộng

     

Giải thuật tìm kiếm theo chiều rộng lớn 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 một đồ thị theo chiều rộng lớn và thực hiện hàng hóng (queue) nhằm ghi lưu giữ đỉnh tiếp giáp để ban đầu việc search kiếm lúc không gặp gỡ được đỉnh tiếp giáp trong ngẫu nhiên vòng lặp nào.

Bạn đang xem: Duyệt đồ thị theo chiều rộng

*

Như trong hình lấy một ví dụ trên, giải thuật tìm kiếm theo chiều rộng chăm bẵm từ A cho tới B tới E cho tới F kế tiếp tới C, tới G và sau cuối tới D. Giải thuật này tuân theo qui tắc:

Qui tắc 1: phê chuẩn tiếp tới đỉnh cạnh bên mà không được duyệt. Đánh vết đỉnh nhưng đã được duyệt. Hiển thị đỉnh đó cùng đẩy vào trong một hàng chờ (queue)..

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

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

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

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

Xem thêm: Định Luật Ôm, Công Thức Định Luật Ôm Là Gì ? Công Thức, Cách Tính Và Ứng Dụng

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

Xem thêm: Ngâm Một Lá Fe Trong Dung Dịch Cuso4, Sau Một Thời Gian

Đến đây, họ thấy rằng không còn đỉnh như thế nào là chưa được lưu lại (chưa được trông nom với ví dụ trong bảng này). Nhưng giải thuật vẫn tiếp tục, bọn họ vẫn tiếp tục rút những đỉnh tự hàng hóng theo sản phẩm công nghệ tự nhằm tìm toàn bộ các đỉnh mà chưa được duyệt. Lúc hàng đợi là trống thì đó là lúc ngừng giải thuật.


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