Biểu diễn đồ thị và BFS tìm đường ngắn nhất

Giới thiệu

Bài này học biểu diễn đồ thị và thuật toán BFS. BFS này giúp tìm đường ít chặng nhất.

Kiến thức cần nhớ

Đồ thị và danh sách kề

• Đồ thị gồm đỉnh nối nhau bằng cạnh.
• Vô hướng như bạn bè, có hướng như theo dõi.
• Danh sách kề: mỗi đỉnh lưu tập đỉnh kề nó.
• Ví dụ đời thường: danh bạ lưu bạn của từng người.

BFS lan theo lớp

• Dùng hàng đợi FIFO: vào trước xét trước.
• Cần tập đã thăm để tránh quay vòng.
• Thăm hết lớp gần rồi mới sang lớp xa.
• Ví dụ đời thường: sóng nước lan tròn từ tâm.

# BFS: hàng đợi + tập đã thăm
from collections import deque
def bfs(graph, start):
    tham = {start}  # đánh dấu đã thăm
    q = deque([start])  # hàng đợi lớp hiện tại
    while q:  # còn nút là còn lan
        u = q.popleft()  # lấy đầu hàng
        for v in graph[u]:  # xét từng lân cận
            if v not in tham:  # chưa thăm
                tham.add(v)  # đánh dấu
                q.append(v)  # xếp cuối hàng
    return tham

Vì sao ra đường ngắn nhất

• Lớp gần được xét trước nên chạm trước là gần nhất.
• Muốn đường cụ thể thì lưu thêm cha mỗi nút.
• Thời gian tuyến tính theo đỉnh cộng cạnh.
• Ví dụ đời thường: tìm bạn chung 1 cầu trước khi tìm 2 cầu.

Ví dụ

• Input: mạng 6 người, BFS từ Amin -> Output: thăm đủ 6 người theo lớp.
• Câu này cho thấy sóng lan lớp 1, lớp 2, lớp 3.
• Input: đồ thị 2 vùng rời, BFS từ vùng 1 -> Output: chỉ thăm vùng 1.
• Câu này cho thấy BFS không bay qua vùng rời.

💻 Bài tập

Ngôn ngữ: C++. Nộp vào day-040/.

Bài 1: Đồ thị danh sách kề

class Graph {
 public:
  Graph(int n, bool directed);
  void addEdge(int u, int v);
  const std::vector<int> &neighbors(int u) const;
  int n() const;
  static Graph fromFile(const std::string &path);   // dòng đầu "n m directed", m dòng "u v"
};

Viết thêm std::vector<std::vector<bool>> toMatrix(). Ghi vào README.md bộ nhớ của 2 cách lưu với $n = 10^5$, $m = 5 \cdot 10^5$.

Bài 2: BFS và đường đi ngắn nhất

Cạnh vô hướng: 0-1, 0-2, 1-3, 2-3, 3-4, 5-6
bfsDist(0)          -> [0,1,1,2,3,-1,-1]
shortestPath(0, 4)  -> [0,1,3,4]
shortestPath(0, 6)  -> []
components          -> 2

Độ phức tạp phải là $O(V + E)$.

Bài 3: BFS trên lưới (nâng cao)

1. Mê cung đọc từ file, # là tường, S bắt đầu, E kết thúc. In độ dài đường ngắn nhất và vẽ đường đi bằng *.
2. Multi-source BFS: lưới có nhiều ô F là đám cháy. Tính mỗi ô cách đám cháy gần nhất bao nhiêu bước.
3. Bipartite: kiểm tra đồ thị có tô được 2 màu không bằng BFS.

S . . #
# # . #
. . . E   -> độ dài 5

✅ Tiêu chí hoàn thành

• Test mẫu pass.
• shortestPath dựng lại đường từ mảng cha đúng.
• Bài 3 in mê cung có vẽ đường.
• Chứng minh bằng lời vì sao BFS cho đường ngắn nhất trên đồ thị không trọng số.

❓ Câu hỏi ôn tập

• Danh sách kề lưu đồ thị thế nào?
• BFS dùng cấu trúc gì để lan lớp?
• Vì sao cần tập đã thăm?
• Khi nào BFS không còn đúng nữa?

🌕 Bạn đã hoàn thành ngày 40. Làm hết bài tập phía trên rồi sang ngày tiếp theo.