Đồ thị và BFS

Xe giao hàng đi từ kho qua các điểm nối nhau bằng đường. Từ kho tới điểm D phải qua ít nhất mấy điểm? Dữ liệu dạng "điểm nối với điểm" là đồ thị, và câu hỏi "ít bước nhất" được giải bằng BFS, dùng đúng queue của chương 2.

Khái niệm

🕸️ Đồ thị (graph): tập các đỉnh (vertex) nối với nhau bằng cạnh (edge), ở bài này đỉnh là điểm giao hàng, cạnh là con đường.

🌊 BFS (breadth-first search, tìm theo chiều rộng): đi từ điểm xuất phát, thăm hết các điểm cách 1 bước, rồi tới các điểm cách 2 bước, cứ thế ra xa dần.

Đồ thị thường lưu bằng danh sách kề: mỗi đỉnh giữ list các đỉnh nối trực tiếp với nó. Trong Java, đó là Map<String, List<String>>. Cây ở hai bài trước là một loại đồ thị không có vòng (đường đi quay lại đỉnh cũ).

Ví dụ

// Main.java
Map<String, List<String>> roads = new HashMap<>();

void main() {
    addRoad("Kho", "A");
    addRoad("Kho", "B");
    addRoad("A", "C");
    addRoad("B", "C");
    addRoad("C", "D");

    Map<String, Integer> steps = bfs("Kho");
    for (var item : steps.entrySet()) {
        System.out.println("%s: %d".formatted(
            item.getKey(), item.getValue()));
    }
}

void addRoad(String from, String to) {
    if (!roads.containsKey(from)) {
        roads.put(from, new ArrayList<>());
    }
    if (!roads.containsKey(to)) {
        roads.put(to, new ArrayList<>());
    }
    roads.get(from).add(to);
    roads.get(to).add(from);
}

Map<String, Integer> bfs(String start) {
    Map<String, Integer> distance =
        new LinkedHashMap<>();
    var queue = new ArrayDeque<String>();
    distance.put(start, 0);
    queue.offer(start);
    while (!queue.isEmpty()) {
        String current = queue.poll();
        for (String next : roads.get(current)) {
            if (!distance.containsKey(next)) {
                distance.put(next,
                    distance.get(current) + 1);
                queue.offer(next);
            }
        }
    }
    return distance;
}

roads khai báo ngoài main, nên mọi method trong file đều dùng được. Đường đi được hai chiều, nên addRoad thêm vào list của cả hai đầu.
distance vừa ghi số bước, vừa đánh dấu điểm đã thăm để không thăm lại. LinkedHashMap giống HashMap nhưng giữ thứ tự thêm vào.
Queue đảm bảo điểm gần được xử lý hết trước điểm xa, nên số bước ghi lần đầu cho mỗi điểm là ít nhất.
Mỗi điểm vào queue một lần, mỗi con đường được xét từ hai đầu: O(số đỉnh + số cạnh).

Các điểm giao hàng, có vòng Kho - A - C - B - Kho

Thử ngay

Chạy ví dụ, rồi thêm System.out.println("Thăm " + current); ngay dưới dòng String current = queue.poll(); và chạy lại.

Đoán trước khi chạy: D cách kho mấy bước? Các điểm được thăm theo thứ tự nào?

Xem kết quả

Thăm Kho
Thăm A
Thăm B
Thăm C
Thăm D
Kho: 0
A: 1
B: 1
C: 2
D: 3

D cách kho 3 bước: Kho → A → C → D. BFS thăm hết các điểm cách 1 bước (A, B) rồi mới tới điểm cách 2 bước (C).

Lỗi hay gặp

Không đánh dấu điểm đã thăm. Đường đi hai chiều và có vòng, nên từ một điểm luôn quay lại được điểm cũ. Không đánh dấu thì BFS đi vòng mãi, queue không bao giờ rỗng.

// SAI — không kiểm tra đã thăm, chạy mãi không dừng
for (String next : roads.get(current)) {
    queue.offer(next);
}

// ĐÚNG — chỉ thêm điểm chưa có trong distance
Map<String, Integer> distance = new HashMap<>();
var queue = new ArrayDeque<String>();
distance.put("Kho", 0);
queue.offer("Kho");
while (!queue.isEmpty()) {
    String current = queue.poll();
    for (String next : roads.get(current)) {
        if (!distance.containsKey(next)) {
            distance.put(next,
                distance.get(current) + 1);
            queue.offer(next);
        }
    }
}

Tóm tắt

Đồ thị gồm đỉnh và cạnh, lưu bằng danh sách kề Map<String, List<String>>.
BFS dùng queue, thăm theo từng lớp khoảng cách.
BFS cho số bước ít nhất khi mọi cạnh dài như nhau.
Luôn đánh dấu đỉnh đã thăm.

Khái niệm

🕸️ Đồ thị (graph): tập các đỉnh (vertex) nối với nhau bằng cạnh (edge), ở bài này đỉnh là điểm giao hàng, cạnh là con đường.

Ví dụ

// Main.java
Map<String, List<String>> roads = new HashMap<>();

void main() {
    addRoad("Kho", "A");
    addRoad("Kho", "B");
    addRoad("A", "C");
    addRoad("B", "C");
    addRoad("C", "D");

    Map<String, Integer> steps = bfs("Kho");
    for (var item : steps.entrySet()) {
        System.out.println("%s: %d".formatted(
            item.getKey(), item.getValue()));
    }
}

void addRoad(String from, String to) {
    if (!roads.containsKey(from)) {
        roads.put(from, new ArrayList<>());
    }
    if (!roads.containsKey(to)) {
        roads.put(to, new ArrayList<>());
    }
    roads.get(from).add(to);
    roads.get(to).add(from);
}

Map<String, Integer> bfs(String start) {
    Map<String, Integer> distance =
        new LinkedHashMap<>();
    var queue = new ArrayDeque<String>();
    distance.put(start, 0);
    queue.offer(start);
    while (!queue.isEmpty()) {
        String current = queue.poll();
        for (String next : roads.get(current)) {
            if (!distance.containsKey(next)) {
                distance.put(next,
                    distance.get(current) + 1);
                queue.offer(next);
            }
        }
    }
    return distance;
}

roads khai báo ngoài main, nên mọi method trong file đều dùng được. Đường đi được hai chiều, nên addRoad thêm vào list của cả hai đầu.

distance vừa ghi số bước, vừa đánh dấu điểm đã thăm để không thăm lại. LinkedHashMap giống HashMap nhưng giữ thứ tự thêm vào.

Queue đảm bảo điểm gần được xử lý hết trước điểm xa, nên số bước ghi lần đầu cho mỗi điểm là ít nhất.

Mỗi điểm vào queue một lần, mỗi con đường được xét từ hai đầu: O(số đỉnh + số cạnh).

Các điểm giao hàng, có vòng Kho - A - C - B - Kho

Thử ngay

Chạy ví dụ, rồi thêm System.out.println("Thăm " + current); ngay dưới dòng String current = queue.poll(); và chạy lại.

Đoán trước khi chạy: D cách kho mấy bước? Các điểm được thăm theo thứ tự nào?

Xem kết quả

Thăm Kho
Thăm A
Thăm B
Thăm C
Thăm D
Kho: 0
A: 1
B: 1
C: 2
D: 3

D cách kho 3 bước: Kho → A → C → D. BFS thăm hết các điểm cách 1 bước (A, B) rồi mới tới điểm cách 2 bước (C).

Lỗi hay gặp

// SAI — không kiểm tra đã thăm, chạy mãi không dừng
for (String next : roads.get(current)) {
    queue.offer(next);
}

// ĐÚNG — chỉ thêm điểm chưa có trong distance
Map<String, Integer> distance = new HashMap<>();
var queue = new ArrayDeque<String>();
distance.put("Kho", 0);
queue.offer("Kho");
while (!queue.isEmpty()) {
    String current = queue.poll();
    for (String next : roads.get(current)) {
        if (!distance.containsKey(next)) {
            distance.put(next,
                distance.get(current) + 1);
            queue.offer(next);
        }
    }
}

Khái niệm

Ví dụ

Thử ngay

Lỗi hay gặp

Tóm tắt

Tự kiểm tra

Đồ thị và BFS

Khái niệm

Ví dụ

Thử ngay

Lỗi hay gặp

Tóm tắt

Tự kiểm tra