Tìm kiếm theo chiều rộng

Một thuật toán duyệt đồ thị cơ bản khám phá các nút theo từng lớp để khảo sát hệ thống tất cả các đỉnh có thể truy cập được từ điểm bắt đầu.

Định nghĩa

Tìm kiếm theo chiều rộng (BFS) là một chiến lược hệ thống để duyệt hoặc tìm kiếm các cấu trúc đồ thị và cây bằng cách thăm các nút theo từng cấp độ từ một nút nguồn đã cho, đảm bảo tất cả các hàng xóm liền kề được xử lý trước các nút sâu hơn. Nó sử dụng hàng đợi để quản lý biên giới khám phá, giữ nguyên thứ tự của các nút được phát hiện chờ xử lý. BFS đặc biệt hiệu quả trong các đồ thị không trọng số để tìm đường đi ngắn nhất (theo số cạnh) đến một đỉnh đích và phân tích theo chiều rộng. Phương pháp này đảm bảo tính đầy đủ trong các đồ thị hữu hạn, có nghĩa là nó sẽ tìm thấy một giải pháp hợp lệ nếu tồn tại. BFS cũng là nền tảng cho nhiều thuật toán đồ thị và ứng dụng thực tế trong mạng, trí tuệ nhân tạo và phân tích dữ liệu.

Ưu điểm

• Luôn tìm được đường đi ngắn nhất trong đồ thị không trọng số nhờ đặc điểm khám phá theo từng cấp độ.
• Đảm bảo tính đầy đủ: sẽ tìm thấy giải pháp nếu tồn tại (trong không gian tìm kiếm hữu hạn).
• Thứ tự duyệt có thể dự đoán và hệ thống, hữu ích cho nhiều nhiệm vụ phân tích.
• Dễ dàng triển khai với cấu trúc dữ liệu hàng đợi chuẩn.
• Hỗ trợ xây dựng cây đường đi ngắn nhất và các ứng dụng thuật toán khác.

Nhược điểm

• Sử dụng bộ nhớ có thể lớn do lưu trữ tất cả các nút biên tại mỗi cấp độ.
• Hiệu quả kém hơn so với các phương pháp theo chiều sâu trong đồ thị rất sâu hoặc lớn.
• Hiệu suất có thể giảm sút trên dữ liệu có kết nối cao do biên rộng.
• Yêu cầu ghi chép thêm để tránh thăm lại nút trong đồ thị có chu trình.
• Không phù hợp với đồ thị có trọng số mà không sửa đổi (ví dụ: thuật toán Dijkstra).

Trường hợp sử dụng

• Quét web và khám phá liên kết có cấu trúc từ một URL nguồn.
• Tìm đường đi ngắn nhất hoặc kết nối trong mạng không trọng số như đồ thị xã hội.
• Duyệt theo cấp độ của cây, chẳng hạn như mở rộng chiều rộng trong cây nhị phân.
• Phát hiện đường đi ngắn nhất trong trí tuệ nhân tạo, định hướng đường đi cho robot và giải mê cung.
• Nền tảng cho các thuật toán đồ thị nâng cao như kiểm tra tính liên thông và cấu trúc cây khung.