Thuật toán duyệt đồ thị ưu tiên chiều rộng
Thuật toán duyệt đồ thị ưu tiên chiều rộng [Breadth-first search - BFS] là một trong những thuật toán tìm kiếm cơ bản và thiết yếu trên đồ thị. Mà trong đó, những đỉnh nào gần đỉnh xuất phát hơn sẽ được duyệt trước.
Ứng dụng của $BFS$ có thể giúp ta giải quyết tốt một số bài toán trong thời gian và không gian tối thiểu. Đặc biệt là bài toán tìm kiếm đường đi ngắn nhất từ một đỉnh gốc tới tất cả các đỉnh khác. Trong đồ thị không có trọng số hoặc tất cả trọng số bằng nhau, thuật toán sẽ luôn trả ra đường đi ngắn nhất có thể. Ngoài ra, thuật toán này còn được dùng để tìm các thành phần liên thông của đồ thị, hoặc kiểm tra đồ thị hai phía, …
Ý tưởng
Với đồ thị không trọng số và đỉnh nguồn $s$. Đồ thị này có thể là đồ thị có hướng hoặc vô hướng, điều đó không quan trọng đối với thuật toán.
Có thể hiểu thuật toán như một ngọn lửa lan rộng trên đồ thị:
- Ở bước thứ $0$, chỉ có đỉnh nguồn $s$ đang cháy.
- Ở mỗi bước tiếp theo, ngọn lửa đang cháy ở mỗi đỉnh lại lan sang tất cả các đỉnh kề với nó.
Trong mỗi lần lặp của thuật toán, "vòng lửa" lại lan rộng ra theo chiều rộng. Những đỉnh nào gần $s$ hơn sẽ bùng cháy trước.
Chính xác hơn, thuật toán có thể được mô tả như sau:
- Đầu tiên ta thăm đỉnh nguồn $s$.
- Việc thăm đỉnh $s$ sẽ phát sinh thứ tự thăm các đỉnh $[u_1, u_2, … u_p]$ kề với $s$ [những đỉnh gần $s$ nhất]. Tiếp theo, ta thăm đỉnh $u_1$, khi thăm đỉnh $u_1$ sẽ lại phát sinh yêu cầu thăm những đỉnh $[v_1, v_2, …, v_q]$ kề với $u_1$. Nhưng rõ ràng những đỉnh $v$ này “xa” $s$ hơn những đỉnh $u$ nên chúng chỉ được thăm khi tất cả những đỉnh $u$ đều đã được thăm. Tức là thứ tự thăm các đỉnh sẽ là: $s, u_1, u_2, …, u_p, v_1, v_2, …, v_q, …$
Thuật toán tìm kiếm theo chiều rộng sử dụng một danh sách để chứa những đỉnh đang “chờ” thăm. Tại mỗi bước, ta thăm một đỉnh đầu danh sách, loại nó ra khỏi danh sách và cho những đỉnh kề với nó chưa được thăm xếp hàng vào cuối danh sách. Thuật toán sẽ kết thúc khi danh sách rỗng.
Thuật toán
Thuật toán sử dụng một cấu trúc dữ liệu hàng đợi [queue] để chứa các đỉnh sẽ được duyệt theo thứ tự ưu tiên chiều rộng.
Bước 1: Khởi tạo
- Các đỉnh đều ở trạng thái chưa được đánh dấu. Ngoại trừ đỉnh nguồn $s$ đã được đánh dấu.
- Một hàng đợi ban đầu chỉ chứa $1$ phần tử là $s$.
Bước 2: Lặp lại các bước sau cho đến khi hàng đợi rỗng:
- Lấy đỉnh $u$ ra khỏi hàng đợi.
- Xét tất cả những đỉnh $v$ kề với $u$ mà chưa được đánh dấu, với mỗi đỉnh $v$ đó:
- Đánh dấu $v$ đã thăm.
- Lưu lại vết đường đi từ $u$ đến $v$.
- Đẩy $v$ vào trong hàng đợi [đỉnh $v$ sẽ chờ được duyệt tại những bước sau].
Bước 3: Truy vết tìm đường đi.
Mô tả
- Xét đồ thị sau đây, với đỉnh nguồn $s=1$ :
- Quá trình:
Cài đặt
Cấu trúc dữ liệu:
- Biến
if [!visit[u]] cout