Cấu trúc dữ liệu - Truyền tải đầu tiên theo chiều rộng
Thuật toán Tìm kiếm đầu tiên theo chiều rộng (BFS) duyệt qua một đồ thị theo chuyển động theo chiều rộng và sử dụng một hàng đợi để nhớ lấy đỉnh tiếp theo để bắt đầu tìm kiếm, khi một điểm cuối xảy ra trong bất kỳ lần lặp nào.
Như trong ví dụ được đưa ra ở trên, thuật toán BFS truyền từ A đến B đến E đến F trước rồi đến C và G cuối cùng đến D. Nó sử dụng các quy tắc sau.
Rule 1- Ghé thăm đỉnh không được thăm liền kề. Đánh dấu nó là đã ghé thăm. Hiển thị nó. Chèn nó vào một hàng đợi.
Rule 2 - Nếu không tìm thấy đỉnh liền kề, loại bỏ đỉnh đầu tiên khỏi hàng đợi.
Rule 3 - Lặp lại Quy tắc 1 và Quy tắc 2 cho đến khi hàng đợi trống.
Bươc | Traversal | Sự miêu tả |
---|---|---|
1 |
|
Khởi tạo hàng đợi. |
2 |
|
Chúng tôi bắt đầu từ việc tham quan S (nút bắt đầu), và đánh dấu nó là đã truy cập. |
3 |
|
Sau đó, chúng tôi thấy một nút liền kề không được sử dụng từ S. Trong ví dụ này, chúng tôi có ba nút nhưng chúng tôi chọn theo thứ tự bảng chữ cáiA, đánh dấu nó là đã ghé thăm và xếp hàng. |
4 |
|
Tiếp theo, nút liền kề không được sử dụng từ S Là B. Chúng tôi đánh dấu nó là đã ghé thăm và xếp hàng. |
5 |
|
Tiếp theo, nút liền kề không được sử dụng từ S Là C. Chúng tôi đánh dấu nó là đã ghé thăm và xếp hàng. |
6 |
|
Hiện nay, Skhông có nút liền kề không được kiểm soát. Vì vậy, chúng tôi dequeue và tìmA. |
7 |
|
Từ A chúng ta có Ddưới dạng nút liền kề không được kiểm soát. Chúng tôi đánh dấu nó là đã ghé thăm và xếp hàng. |
Ở giai đoạn này, chúng ta không có nút nào chưa được đánh dấu (không được đánh dấu). Nhưng theo thuật toán, chúng tôi tiếp tục giảm giá trị để có được tất cả các nút chưa được sử dụng. Khi hàng đợi được làm trống, chương trình kết thúc.
Việc thực hiện thuật toán này trong ngôn ngữ lập trình C có thể được xem ở đây .