Tìm_kiếm theo chiều rộng 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 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 BULLET 1 Chèn đỉnh gốc vào hàng đợi đang hướng tới BULLET 2 Lấy ra đỉnh đầu_tiên trong hàng đợi và quan_sát nó BULLET 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ả BULLET 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 BULLET 3 Nếu hàng đợi là rỗng thì tất_cả các đỉnh có_thể đến được đều đã được quan_sát dừng việc tìm_kiếm và trả về không thấy BULLET 4 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à formula _ 1 là số đỉnh thì không_gian cần dùng của thuật_toán là formula _ 2 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à formula _ 3 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ú formula _ 3 nằm trong khoảng từ formula _ 2 đến formula _ 6 tuỳ theo số cung của đồ_thị Ứ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ư BULLET Tìm tất_cả các đỉnh trong một thành_phần liên_thông BULLET Thuật_toán Cheney cho việc dọn rác BULLET Tìm đườ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 BULLET Kiểm_tra xem một đồ_thị có là đồ_thị hai phía BULLET Thuật_toán Cuthill_McKee_BULLET_Thuật toán Ford 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 BULLET Tìm_kiếm theo chiều sâu Liên_kết ngoài BULLET Mô_tả thuật_toán tìm_kiếm theo chiều rộng có kèm ví_dụ
Tìm_kiếm theo chiều rộng