Hãy tưởng tượng bạn đang đứng ở trung tâm một mê cung và muốn tìm đường ra. Bạn sẽ làm gì? Một cách tự nhiên, bạn có thể sẽ thử tất cả các lối đi gần bạn trước, sau đó mới đến các lối đi xa hơn, đúng không? Đó chính là ý tưởng cốt lõi của thuật toán BFS!
1. Khái niệm cơ bản về thuật toán BFS
BFS (Breadth-First Search), hay còn gọi là tìm kiếm theo chiều rộng, là một thuật toán duyệt đồ thị (graph) hoặc cây (tree). Nó bắt đầu từ một nút gốc (root) và khám phá tất cả các nút lân cận ở mức hiện tại trước khi chuyển sang các nút ở mức tiếp theo.
Điểm mấu chốt của BFS là “duyệt theo lớp”. Nó giống như việc bạn thả một hòn đá xuống mặt hồ phẳng lặng. Các vòng tròn đồng tâm sẽ lan rộng ra từ từ. BFS cũng hoạt động tương tự, nó “lan tỏa” từ nút gốc sang các nút lân cận, rồi đến các nút lân cận của các nút lân cận, và cứ thế tiếp tục cho đến khi tìm thấy nút đích hoặc đã duyệt hết tất cả các nút.
Ứng dụng thực tế của BFS rất đa dạng:
- Tìm đường đi ngắn nhất trong đồ thị không trọng số: Ví dụ như tìm đường đi ngắn nhất giữa hai thành phố trên bản đồ giao thông.
- Tìm kiếm trong các hệ thống ngang hàng (peer-to-peer networks): Tìm kiếm tài nguyên hoặc người dùng trong mạng.
- Thu thập dữ liệu của các công cụ tìm kiếm (web crawlers): Duyệt qua các trang web theo chiều rộng để lập chỉ mục.
- Kiểm tra tính liên thông của đồ thị: Xác định xem tất cả các nút trong đồ thị có thể được kết nối với nhau hay không.
- Giải các bài toán về mê cung hoặc trò chơi: Tìm đường đi hoặc trạng thái tối ưu.
2. Nguyên lý hoạt động của BFS
Giả sử chúng ta có một đồ thị và một nút xuất phát. BFS hoạt động theo các bước sau:
1. Khởi tạo:
- Tạo một hàng đợi (queue) để lưu trữ các nút sẽ được thăm.
- Đánh dấu nút xuất phát là đã được thăm (visited) và thêm nó vào hàng đợi.
- Có thể sử dụng một mảng hoặc một tập hợp để theo dõi các nút đã được thăm.
2. Duyệt:
Trong khi hàng đợi không rỗng:
- Lấy ra (dequeue) một nút u từ đầu hàng đợi.
- Duyệt qua tất cả các nút lân cận v của nút u.
- Nếu nút v chưa được thăm:
- Đánh dấu nút v là đã được thăm.
- Thêm nút v vào cuối hàng đợi.
- Quá trình này tiếp tục cho đến khi hàng đợi trở nên rỗng, nghĩa là tất cả các nút có thể truy cập được từ nút xuất phát đã được duyệt.
Một ví dụ minh họa:
Hãy xem xét một đồ thị đơn giản với các nút A, B, C, D, E và các cạnh sau: A-B, A-C, B-D, C-E. Giả sử chúng ta bắt đầu từ nút A.
Bước 1 - Khởi tạo: Hàng đợi = [A], Đã thăm = {A}
Lặp 1:
- Lấy A ra khỏi hàng đợi. Hàng đợi = [].
- Các nút lân cận của A là B và C. Cả B và C đều chưa được thăm.
- Đánh dấu B và C là đã thăm và thêm chúng vào hàng đợi. Hàng đợi = [B, C], Đã thăm = {A, B, C}.
Lặp 2:
- Lấy B ra khỏi hàng đợi. Hàng đợi = [C].
- Nút lân cận của B là D. D chưa được thăm.
- Đánh dấu D là đã thăm và thêm nó vào hàng đợi. Hàng đợi = [C, D], Đã thăm = {A, B, C, D}.
Lặp 3:
- Lấy C ra khỏi hàng đợi. Hàng đợi = [D].
- Nút lân cận của C là E. E chưa được thăm.
- Đánh dấu E là đã thăm và thêm nó vào hàng đợi. Hàng đợi = [D, E], Đã thăm = {A, B, C, D, E}.
Lặp 4:
- Lấy D ra khỏi hàng đợi. Hàng đợi = [E].
- B không có nút lân cận chưa được thăm (B đã được thăm).
Lặp 5:
- Lấy E ra khỏi hàng đợi. Hàng đợi = [].
- E không có nút lân cận.
Hàng đợi bây giờ rỗng, thuật toán kết thúc. Thứ tự duyệt các nút là: A, B, C, D, E. Bạn có thể thấy cách thuật toán duyệt các nút theo từng “mức” (A ở mức 0, B và C ở mức 1, D và E ở mức 2).
3. Triển khai thuật toán BFS trong Java
Bài toán : Tìm đường đi ngắn nhất từ một nút đến tất cả các nút khác trong đồ thị không trọng số.
Mô tả: Cho một đồ thị vô hướng không trọng số và một nút nguồn. Hãy sử dụng thuật toán BFS để tìm độ dài đường đi ngắn nhất từ nút nguồn đến tất cả các nút khác trong đồ thị. Độ dài đường đi ở đây được tính bằng số cạnh trên đường đi.
Nút nguồn là 0
Đồ thị:
0 -- 1 | | 2 -- 3
```import java.util.*;
public class BFSShortestPath {
public static void main(String[] args) {
int numNodes = 4;
List<List<Integer>> adj = new ArrayList<>(numNodes);
for (int i = 0; i < numNodes; i++) {
adj.add(new ArrayList<>());
}
adj.get(0).addAll(Arrays.asList(1, 2));
adj.get(1).addAll(Arrays.asList(0, 3));
adj.get(2).addAll(Arrays.asList(0, 3));
adj.get(3).addAll(Arrays.asList(1, 2));
int source = 0;
int[] distance = bfsShortestPath(adj, source, numNodes);
System.out.println("Đường đi ngắn nhất từ nút " + source + " đến các nút khác:");
for (int i = 0; i < numNodes; i++) {
System.out.println("Đến nút " + i + ": " + distance[i]);
}
}
public static int[] bfsShortestPath(List<List<Integer>> adj, int source, int numNodes) {
int[] distance = new int[numNodes];
Arrays.fill(distance, -1); // Initialize distances to -1 (representing infinity)
distance[source] = 0;
Queue<Integer> queue = new LinkedList<>();
queue.offer(source);
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : adj.get(u)) {
if (distance[v] == -1) {
distance[v] = distance[u] + 1;
queue.offer(v);
}
}
}
return distance;
}
}
Bình luận