BFS (tìm kiếm theo chiều rộng) là một phương pháp duyệt đồ thị, thường được sử dụng trong cả thuật toán đơn giản và nâng cao. Tìm kiếm theo chiều rộng hoạt động bằng cách đi qua các cấp độ riêng lẻ của biểu đồ, bắt đầu từ nút nguồn và dần dần di chuyển ra khỏi nút đó. Điều này được thể hiện rõ ràng trong hình ảnh động.
Để viết một BFS đơn giản, bạn cần có khả năng làm việc với hàng đợi, một cấu trúc dữ liệu cho phép bạn lấy từ đầu và đưa nó vào cuối, đồng thời có thể lưu trữ biểu đồ dưới dạng của một danh sách kề.
Mô tả chính thức của thuật toán
1) Đặt số đỉnh bắt đầu tìm kiếm vào hàng đợi trống ban đầu.
2) Trích xuất đỉnh U từ đầu hàng đợi và đánh dấu nó là được sử dụng trong một mảng riêng.
3) Ở cuối hàng đợi, thêm tất cả các đỉnh mà chúng ta có thể tiếp cận bằng cách sử dụng cạnh từ đỉnh U và chưa được đánh dấu.
4) Nếu hàng đợi trống thì tất cả các nút của biểu đồ liên thông đã được quét, nếu không thì quay lại bước 2.
Khó khăn trong công việc
Vì trong trường hợp xấu nhất, thuật toán thăm tất cả các nút của đồ thị nên khi lưu trữ đồ thị dưới dạng danh sách kề, độ phức tạp thời gian của thuật toán là O(|V| + |E|), trong đó V là tập hợp của các đỉnh của đồ thị và E là tập hợp các cạnh. ;
Nói cách khác, thuật toán hoạt động trong trường hợp xấu nhất đối với số cạnh + số đỉnh.