Xem mã nguồn của Tìm kiếm theo chiều rộng

[[Tập tin:Tìm kiếm theo chiều rộng BFS.gif|nhỏ|310x310px|Mô phỏng tìm kiếm trên cây tìm kiếm theo thuật toán tìm kiếm theo chiều rộng]]
{{Infobox Algorithm
|class=[[Giải thuật tìm kiếm|Thuật toán tìm kiếm]]
|image=[[Hình:Breadth-first-tree.svg|none|300px|Thứ tự thăm các đỉnh]]
|caption = Thứ tự thăm các đỉnh</small>
|data=[[Đồ thị (cấu trúc dữ liệu)|Đồ thị]]
|time=<math>O(|V|+|E|) = O(b^d)</math>
|space=<math>O(|V|) = O(b^d)</math>
|optimal=tối ưu (cho đồ thị không trọng số)
}}
Trong [[lý thuyết đồ thị]], '''tìm kiếm theo [[chiều rộng]]''' ('''BFS''') là một [[thuật toán tìm kiếm trong đồ thị]] trong đó việc tìm kiếm chỉ bao gồm 2 thao tác: (a) cho trước một đỉnh của đồ thị; (b) thêm các đỉnh kề với đỉnh vừa cho vào danh sách có thể hướng tới tiếp theo. Có thể sử dụng thuật toán tìm kiếm theo [[chiều rộng]] cho hai mục đích: tìm kiếm đường đi từ một đỉnh gốc cho trước tới một đỉnh đích, và tìm kiếm đường đi từ đỉnh gốc tới tất cả các đỉnh khác. Trong đồ thị không có trọng số, thuật toán tìm kiếm theo [[chiều rộng]] luôn tìm ra đường đi ngắn nhất có thể. Thuật toán BFS bắt đầu từ đỉnh gốc và lần lượt nhìn các đỉnh kề với đỉnh gốc. Sau đó, với mỗi đỉnh trong số đó, thuật toán lại lần lượt nhìn trước các đỉnh kề với nó mà chưa được quan sát trước đó và lặp lại. Xem thêm thuật toán [[tìm kiếm theo chiều sâu]], trong đó cũng sử dụng 2 thao tác trên nhưng có trình tự quan sát các đỉnh khác với thuật toán tìm kiếm theo [[chiều rộng]].

Đây là một thuật toán trong [[trí tuệ nhân tạo]]. Cấu trúc dữ liệu được sử dụng là hàng đợi (queue). 

== Thuật toán ==
[[Hình:Animated BFS.gif|nhỏ|187px|phải|Hình động minh họa thuật toán tìm kiếm theo chiều rộng]]
Thuật toán sử dụng một cấu trúc dữ liệu [[hàng đợi]] để lưu trữ thông tin trung gian thu được trong quá trình tìm kiếm:

# Chèn đỉnh gốc vào hàng đợi (đang hướng tới)
# Lấy ra đỉnh đầu tiên trong hàng đợi và quan sát nó
#* Nếu đỉnh này chính là đỉnh đích, dừng quá trình tìm kiếm và trả về kết quả.
#* Nếu không phải thì chèn tất cả các đỉnh kề với đỉnh vừa thăm nhưng chưa được quan sát trước đó vào hàng đợi.
# Nếu hàng đợi là rỗng, thì tất cả các đỉnh có thể đến được đều đã được quan sát &ndash; dừng việc tìm kiếm và trả về "không thấy".
# Nếu hàng đợi không rỗng thì quay về bước 2.

'''Ghi chú''': Nếu sử dụng một [[ngăn xếp]] thay vì hàng đợi thì thuật toán trở thành thuật toán [[tìm kiếm theo chiều sâu]].

== Các đặc tính của thuật toán ==

=== Không gian ===

Nếu ''V'' là tập hợp đỉnh của đồ thị và <math>|V|</math> là số đỉnh thì không gian cần dùng của thuật toán là <math>O(|V|)</math>.

=== Thời gian ===

Nếu ''V'', và ''E'' là tập hợp các đỉnh và cung của đồ thị, thì thời gian thực thi của thuật toán là <math>O(|E|+|V|)</math> vì trong trường hợp xấu nhất, mỗi đỉnh và cung của đồ thị được thăm đúng một lần. Ghi chú: <math>O(|E|+|V|)</math> nằm trong khoảng từ <math>O(|V|)</math> đến <math>O(|V|^2)</math>, tùy theo số cung của đồ thị.{{Graph search algorithm}}
== Ứng dụng ==

Thuật toán tìm kiếm theo [[chiều rộng]] được dùng để giải nhiều bài toán trong lý thuyết đồ thị, chẳng hạn như:

* Tìm tất cả các đỉnh trong một [[thành phần liên thông (lý thuyết đồ thị)|thành phần liên thông]]
* [[Thuật toán Cheney]] cho việc dọn rác
* Tìm [[bài toán đường đi ngắn nhất|đường đi ngắn nhất]] giữa hai đỉnh ''u'' và ''v'' (với chiều dài đường đi tính bằng số cung)
* Kiểm tra xem một đồ thị có là [[đồ thị hai phía]]
* [[Thuật toán Cuthill–McKee]]
* [[Thuật toán Ford-Fulkerson|Thuật toán Ford&ndash;Fulkerson]] để tìm [[luồng cực đại]] trong mạng

=== Tìm các thành phần liên thông ===

Tập hợp các đỉnh đã được quan sát bởi thuật toán tìm kiếm theo [[chiều rộng]] chính là thành phần liên thông chứa đỉnh gốc.

=== Kiểm tra đồ thị hai phía ===

Có thể dùng thuật toán tìm kiếm theo [[chiều rộng]] để kiểm tra xem một đồ thị có phải đồ thị hai phía hay không, bằng cách tìm kiếm từ một đỉnh bất kì và gán nhãn chẵn lẻ cho các đỉnh được quan sát. Nghĩa là, gán nhãn 0 cho đỉnh gốc, 1 cho tất cả các đỉnh kề đỉnh gốc, 0 cho tất cả các đỉnh kề với một đỉnh kề đỉnh gốc, và tiếp tục như vậy. Nếu ở một bước nào đó, có hai đỉnh kề nhau có cùng nhãn, thì đồ thị không là hai phía. Nếu quá trình tìm kiếm kết thúc mà điều này không xảy ra thì đồ thị là hai phía.

== Xem thêm ==
* [[Tìm kiếm theo chiều sâu]]

==Tham khảo==
{{Tham khảo}}
{{refbegin}}
* {{chú thích
 | last=Knuth
 | first=Donald E.
 | title=The Art Of Computer Programming
 | volume=1
 | edition=3
 | publisher=Addison-Wesley
 | place=Boston
 | year=1997
 | ISBN=0-201-89683-4
 | url=http://www-cs-faculty.stanford.edu/~knuth/taocp.html
 | access-date=2012-09-09
 | archive-date=2008-09-04
 | archive-url=https://web.archive.org/web/20080904163709/http://www-cs-faculty.stanford.edu/~knuth/taocp.html
 }}
{{refend}}

{{thể loại Commons|Breadth-first search}}

==Liên kết ngoài==
* [http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch14.html#QQ1-46-92 Mô tả thuật toán tìm kiếm theo chiều rộng có kèm ví dụ] {{Webarchive|url=https://web.archive.org/web/20121113095237/http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch14.html#QQ1-46-92 |date=2012-11-13 }}

[[Thể loại:Giải thuật lý thuyết đồ thị]]
[[Thể loại:Thuật toán tìm kiếm]]
[[Thể loại:Giải thuật tìm kiếm]]