Trang chủ > Khác > Cấu trúc dữ liệu và giải thuật > Tìm kiếm theo chiều rộng - Breadth First Traversal (Cấu trúc dữ liệu và giải thuật)

Tìm kiếm theo chiều rộng - Breadth First Traversal (Cấu trúc dữ liệu và giải thuật)

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à dùng hàng đợi (queue) để ghi nhớ đỉnh liền kề để bắt đầu thực hiện công 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.

Tìm kiếm theo chiều rộng - Breadth First Traversal ảnh 1

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

  • Qui tắc 1: Duyệt tiếp tới đỉnh liền kề bất kỳ mà chưa được duyệt. Đánh dấu đỉnh đã được duyệt. Hiển thị đỉnh đó và đặt vào trong một hàng đợi (queue)..

  • Qui tắc 2: Nếu trong trường hợp không tìm thấy đỉnh liền kề, thì thao tác 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 đến khi hàng đợi là trống.

Bảng sau đây đâ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:

Bước Duyệt Miêu tả
1.
Tìm kiếm theo chiều rộng - Breadth First Traversal ảnh 2
Khởi tạo hàng đợi (queue)
2.
Tìm kiếm theo chiều rộng - Breadth First Traversal ảnh 3
Chúng ta bắt đầu duyệt từ đỉnh S (đỉnh bắt đầu) và sau đó đánh dấu đỉnh này là đã duyệt.
3.
Tìm kiếm theo chiều rộng - Breadth First Traversal ảnh 4
Sau đó chúng ta sẽ tìm đỉnh liền kề với S mà chưa được duyệt. Trong ví dụ này thì chúng ta có ba đỉnh, và theo thứ tự chữ cái thì chúng ta lựa chọn đỉnh A đánh dấu là đã duyệt và đặt A vào hàng đợi.
4.
Tìm kiếm theo chiều rộng - Breadth First Traversal ảnh 5
Tiếp tục duyệt đỉnh liền kề với đỉnh S là đỉnh B. Đánh dấu là đã duyệt và đặt đỉnh này vào hàng đợi.
5.
Tìm kiếm theo chiều rộng - Breadth First Traversal ảnh 6
Tiếp tục duyệt đỉnh liền kề với đỉnh S là đỉnh C. Đánh dấu là đã được duyệt và đặt đỉnh này vào hàng đợi.
6.
Tìm kiếm theo chiều rộng - Breadth First Traversal ảnh 7
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 sẽ rút A từ hàng đợi.
7.
Tìm kiếm theo chiều rộng - Breadth First Traversal ảnh 8
Từ đỉnh A chúng ta có đỉnh liền kề là đỉnh D và là đỉnh chưa được duyệt. Đánh dấu đỉnh D là đã được duyệt và đặt vào hàng đợi.

Đến đây, chúng ta có thể thấy rằng không còn đỉnh nào là chưa được đánh dấu (chưa được duyệt như ở trong ví dụ trong bảng này). Nhưng giải thuật vẫn tiếp tục thực hiện, chúng ta vẫn tiếp tục rút các đỉnh từ hàng đợi ra 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ì khi đó giải thuật cũng kết thúc.