Giới thiệu

Chào mừng bạn quay lại với chuỗi bài về Thuật toán đồ thị! Sau tìm kiếm theo chiều sâu, chúng ta sẽ tìm hiểu tìm kiếm theo chiều rộng (BFS), thuật toán duyệt đồ thị cơ bản còn lại.

DFS đi sâu vào đồ thị, còn BFS khám phá theo từng lớp: trước tiên là đỉnh bắt đầu, tiếp theo là tất cả các đỉnh kề, rồi đến mọi đỉnh cách đó hai bước, cứ thế tiếp tục. Thứ tự theo từng lớp này chính là điều giúp BFS tìm đường đi ngắn nhất trong đồ thị không trọng số.

Như những bài khác trong chuỗi, đồ thị được biểu diễn bằng n (số lượng đỉnh, từ 0 đến n - 1) và edges, một mảng phẳng gồm các cặp đỉnh vô hướng [u0, v0, u1, v1, ...].

Bắt đầu nào!