Tìm đường đi ngắn nhất bằng BFS trong Java

1. Biểu diễn khuôn viên thành đồ thị

Giả sử cần chỉ đường từ cổng đến phòng thực hành theo số đoạn đường ít nhất. Mỗi địa điểm là một đỉnh. Hai địa điểm có đường nối trực tiếp thì thêm cạnh. Ví dụ dùng đường hai chiều, nên mỗi cạnh xuất hiện trong danh sách kề của cả hai đầu. Nhà kho được đưa vào dữ liệu như một điểm tách biệt để kiểm tra trường hợp không thể đi đến.

Giả định quan trọng là mỗi đoạn đường có cùng chi phí. Lộ trình ít đoạn nhất có thể dài hơn nếu một đoạn rất xa hoặc có cầu thang. Bài này dùng BFS để tối thiểu số cạnh. Nếu đưa thời gian hoặc độ dài vào từng cạnh, hãy chọn thuật toán đường đi ngắn phù hợp với trọng số.

2. Duyệt theo lớp khoảng cách

BFS bắt đầu từ Cổng. Hàng đợi nhận hai đỉnh kề là Hành lang và Sân. Khi lấy Hành lang ra, chương trình phát hiện Phòng lab. Khi lấy Sân ra, chương trình phát hiện Thư viện. Hàng đợi phục vụ đỉnh phát hiện trước, nên các đỉnh cách Cổng một cạnh được xử lý trước các đỉnh cách Cổng hai cạnh.

Khi phát hiện một đỉnh mới, lưu đỉnh đã dẫn đến nó. Bảng parent kiêm vai trò đánh dấu đã thăm. Đánh dấu ngay khi thêm vào hàng đợi để một đỉnh có nhiều đường dẫn đến chỉ được thêm một lần.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class CampusBfs {
    static List<String> shortestPath(Map<String, List<String>> graph,
                                     String start, String target) {
        if (!graph.containsKey(start) || !graph.containsKey(target)) {
            return List.of();
        }
        Queue<String> queue = new ArrayDeque<>();
        Map<String, String> parent = new HashMap<>();
        parent.put(start, null);
        queue.add(start);

        while (!queue.isEmpty()) {
            String current = queue.remove();
            if (current.equals(target)) break;
            for (String next : graph.getOrDefault(current, List.of())) {
                if (parent.containsKey(next)) continue;
                parent.put(next, current);
                queue.add(next);
            }
        }

        if (!parent.containsKey(target)) return List.of();
        List<String> path = new ArrayList<>();
        for (String node = target; node != null; node = parent.get(node)) {
            path.add(node);
        }
        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {
        Map<String, List<String>> campus = Map.of(
            "Cổng", List.of("Hành lang", "Sân"),
            "Hành lang", List.of("Cổng", "Phòng lab"),
            "Sân", List.of("Cổng", "Thư viện"),
            "Phòng lab", List.of("Hành lang", "Thư viện"),
            "Thư viện", List.of("Sân", "Phòng lab"),
            "Nhà kho", List.of()
        );

        List<String> path = shortestPath(campus, "Cổng", "Phòng lab");
        if (!path.equals(List.of("Cổng", "Hành lang", "Phòng lab"))) {
            throw new AssertionError(path);
        }
        if (!shortestPath(campus, "Cổng", "Nhà kho").isEmpty()) {
            throw new AssertionError("Nhà kho phải tách biệt");
        }
        if (!shortestPath(campus, "Cổng", "Cổng").equals(List.of("Cổng"))) {
            throw new AssertionError("Điểm đầu trùng điểm cuối");
        }
        System.out.println(String.join(" -> ", path));
    }
}

3. Khôi phục lộ trình từ thông tin cha

Sau khi duyệt, parent.get("Phòng lab") là Hành lang, còn cha của Hành lang là Cổng. Chương trình đi ngược từ đích về nguồn rồi đảo danh sách. Nhờ đó mỗi phần tử trong hàng đợi chỉ cần lưu tên đỉnh, thay vì sao chép toàn bộ đường đi tại mỗi bước.

Với danh sách kề, mỗi đỉnh được thêm vào hàng đợi nhiều nhất một lần. Mỗi cạnh được xét khi duyệt các đầu mút của nó. Thời gian là O(V + E) với phép tra bảng băm có chi phí trung bình hằng số, còn bộ nhớ phụ là O(V) cho hàng đợi, bảng cha và đường đi.

4. Chạy chương trình và thay dữ liệu

javac -encoding UTF-8 CampusBfs.java
java CampusBfs
# Kết quả: Cổng -> Hành lang -> Phòng lab

Ví dụ tự kiểm tra trường hợp có đường, không có đường và điểm đầu trùng điểm cuối. Hãy thử thêm một cạnh từ Cổng tới Phòng lab ở cả hai danh sách kề. Đường mong đợi chỉ còn một cạnh. Sau đó bỏ đường Hành lang–Phòng lab để buộc chương trình tìm đường qua Sân và Thư viện.

Nếu có hai lộ trình cùng độ dài, thứ tự danh sách kề quyết định lộ trình mẫu mà hàm trả về. Muốn kết quả ổn định khi đọc dữ liệu từ một nguồn có thứ tự tùy ý, có thể sắp thứ tự danh sách kề trước khi duyệt và ghi rõ quy tắc trong tài liệu.

Đọc thêm tại Java API · ArrayDeque.