BFS — Giải thích thuật toán tìm kiếm theo chiều rộng

Tìm kiếm theo chiều rộng, hay BFS, là một thuật toán trên đồ thị duyệt các đỉnh theo thứ tự khoảng cách của chúng tới một đỉnh bắt đầu. Nó kiểm tra mọi đỉnh cách một cạnh trước, rồi mới chuyển sang các đỉnh cách hai cạnh, rồi ba cạnh, và cứ tiếp tục như vậy.

Thứ tự theo từng lớp đó là ý tưởng cốt lõi. Nếu đồ thị là không trọng số, hoặc mọi cạnh đều có cùng chi phí, BFS cũng cho độ dài đường đi ngắn nhất từ đỉnh bắt đầu đến mọi đỉnh có thể đi tới.

Breadth-First Search Làm Gì

BFS sử dụng một hàng đợi, tức là một danh sách vào trước ra trước. Hàng đợi chính là thứ giữ nguyên thứ tự theo lớp: các đỉnh được phát hiện sớm hơn sẽ được xử lý sớm hơn.

Mẫu thực hiện thông thường là:

• đánh dấu đỉnh bắt đầu là đã thăm
• đưa nó vào hàng đợi
• lấy đỉnh ở đầu hàng đợi ra
• thêm từng đỉnh kề chưa thăm vào cuối hàng đợi
• lặp lại cho đến khi hàng đợi rỗng

Nếu bạn cũng lưu đỉnh cha của mỗi đỉnh, bạn có thể khôi phục một đường đi ngắn nhất sau khi quá trình tìm kiếm kết thúc.

Vì Sao Hàng Đợi Tạo Ra Các Lớp

Giả sử đỉnh $A$ là điểm bắt đầu. Các đỉnh kề trực tiếp của nó có khoảng cách $1$ từ $A$, nên chúng vào hàng đợi trước. Chỉ sau khi các đỉnh đó được xử lý thì các đỉnh kề chưa thăm của chúng mới được thêm vào, nghĩa là làn sóng tiếp theo có khoảng cách $2$.

Đó là lý do BFS tự nhiên nhóm các đỉnh theo khoảng cách tới điểm bắt đầu. Nó không ước lượng đường nào là ngắn. Hàng đợi buộc quá trình tìm kiếm phải hoàn tất mọi đường có ít cạnh hơn trước khi xét đến các đường dài hơn.

Ví dụ BFS: Tìm Đường Đi Ngắn Nhất Theo Số Cạnh

Dùng đồ thị sau:

$$A \to \{B, C\}, \qquad B \to \{D\}, \qquad C \to \{E\}, \qquad D \to \{F\}, \qquad E \to \{F\}$$

Bắt đầu từ $A$. Hàng đợi thay đổi như sau:

$$[A] \to [B, C] \to [C, D] \to [D, E] \to [E, F] \to [F]$$

Ý nghĩa là như sau:

Đầu tiên, xử lý $A$, rồi thêm $B$ và $C$. Tiếp theo, xử lý $B$ rồi đến $C$, từ đó thêm $D$ và $E$. Sau đó, xử lý $D$ và $E$, và khi đó đi tới $F$.

Vì vậy thứ tự BFS thăm các đỉnh là:

$$A,\ B,\ C,\ D,\ E,\ F$$

Các khoảng cách từ $A$ là:

$$\operatorname{dist}(A)=0,\quad \operatorname{dist}(B)=1,\quad \operatorname{dist}(C)=1,\quad \operatorname{dist}(D)=2,\quad \operatorname{dist}(E)=2,\quad \operatorname{dist}(F)=3$$

Điều này cho thấy lợi ích chính. BFS đi tới $F$ ở khoảng cách $3$, nên đường đi ngắn nhất từ $A$ đến $F$ dùng $3$ cạnh. Một đường đi ngắn nhất là $A \to B \to D \to F$. Một đường khác là $A \to C \to E \to F$.

Những Lỗi BFS Thường Gặp

Cho Rằng BFS Luôn Tìm Được Đường Đi Rẻ Nhất

Điều đó chỉ đúng khi mọi cạnh có cùng chi phí, hoặc khi đồ thị được xem là không trọng số. Nếu các cạnh có trọng số khác nhau, BFS có thể tìm ra một đường có ít cạnh hơn nhưng tổng chi phí lại lớn hơn.

Đánh Dấu Một Đỉnh Quá Muộn

Trong BFS chuẩn, một đỉnh thường được đánh dấu là đã thăm ngay khi nó được đưa vào hàng đợi, chứ không phải khi nó được lấy ra sau đó. Cách này ngăn cùng một đỉnh bị thêm vào hàng đợi nhiều lần.

Nhầm Lẫn Giữa BFS Và DFS

BFS khám phá theo từng lớp. Tìm kiếm theo chiều sâu, hay DFS, sẽ tiếp tục đi theo một nhánh trước khi quay lui. Hai thuật toán này phù hợp với những loại câu hỏi khác nhau.

Quên Rằng Thứ Tự Có Thể Phụ Thuộc Vào Thứ Tự Các Đỉnh Kề

Thứ tự thăm chính xác bên trong cùng một lớp có thể thay đổi tùy theo cách liệt kê các đỉnh kề. Các đảm bảo về khoảng cách vẫn đúng, nhưng thứ tự duyệt có thể khác.

Khi Nào Dùng Breadth-First Search

BFS hữu ích khi bạn quan tâm đến khả năng đi tới, duyệt cây theo từng mức, hoặc độ dài đường đi ngắn nhất được đo bằng số cạnh.

Nó cũng xuất hiện trong các bài toán không gian trạng thái, nơi mỗi bước di chuyển có cùng chi phí. Trong điều kiện đó, BFS thường là cách rõ ràng nhất để tìm số bước di chuyển ít nhất.

Cách Đơn Giản Để Ghi Nhớ BFS

Hãy hình dung BFS như một gợn sóng lan ra từ đỉnh bắt đầu. Mỗi bước lan sóng thêm một cạnh khoảng cách.

Để tự thử, hãy vẽ một đồ thị nhỏ, chọn một đỉnh bắt đầu, và ghi lại hàng đợi sau mỗi bước. Nếu muốn đi tiếp, hãy giải một bài toán duyệt đồ thị tương tự và kiểm tra xem kết luận về đường đi ngắn nhất còn đúng hay không khi đồ thị có trọng số.