BFS (duyệt theo bề rộng) và DFS (duyệt theo chiều sâu) thường được dạy cạnh nhau như một cặp sinh đôi: cả hai duyệt đồ thị, cả hai thăm mỗi đỉnh đúng một lần, cả hai là O(V+E). Từ đó dễ rút ra kết luận rằng chúng thay thế được cho nhau — chỉ là hai cách viết cho cùng một việc. Bài này đo, và cho thấy đó là một trong những hiểu nhầm tốn kém nhất về đồ thị: hai thuật toán "giống nhau" này tìm ra những thứ khác hẳn nhau, và tốn bộ nhớ theo hai chiều hoàn toàn khác.
Cùng duyệt, nhưng đi theo hai kiểu
Khác biệt nằm ở thứ tự thăm. BFS dùng một hàng đợi: nó lan ra theo từng tầng — thăm hết các đỉnh cách gốc một bước, rồi hết các đỉnh cách hai bước, cứ thế như một mặt sóng loang đều. DFS dùng một ngăn xếp (hoặc đệ quy): nó lao sâu hết một nhánh cho tới khi hết đường mới lui về thử nhánh khác. Cùng một đồ thị, cùng thăm mọi đỉnh, nhưng một cái đi theo bề rộng, một cái đi theo chiều sâu. Sự khác biệt về thứ tự đó dẫn tới khác biệt về kết quả — và tôi đo nó trên một lưới ô vuông 1000×1000, đi từ góc này sang góc đối diện.
Đo: cùng O(V+E), nhưng đường lệch nhau 250 lần
Cả hai đều tìm được một đường từ góc trên-trái tới góc dưới-phải, và cả hai chạy trong khoảng 4–6 mili giây — đúng như O(V+E) hứa hẹn, thời gian gần như nhau. Nhưng đường chúng tìm ra thì khác một trời một vực:
đường tìm được đỉnh bộ nhớ dùng
BFS (hàng đợi) 1 998 cạnh 1 000 (bề rộng mặt sóng)
DFS (ngăn xếp) 499 500 cạnh 499 501 (chiều sâu nhánh)
BFS tìm ra đường 1 998 cạnh — đúng bằng khoảng cách ngắn nhất có thể trên lưới (999 bước sang phải cộng 999 bước xuống). DFS tìm ra một đường 499 500 cạnh — dài gấp 250 lần. Vì sao? Vì BFS, do loang đều theo tầng, chạm tới đích ngay khi vừa đủ số bước tối thiểu, nên đường nó dựng luôn là đường ngắn nhất (trên đồ thị không trọng số). Còn DFS lao sâu theo một nhánh, nó chạm đích qua chính cái nhánh ngoằn ngoèo nó đang đi — một đường bất kỳ, và trên lưới mở nó rắn rết qua gần nửa số ô trước khi tới góc. Nếu bạn cần đường đi ngắn nhất mà dùng DFS, bạn nhận về một con đường vòng vo dài gấp trăm lần.
Một lần tôi đo hớ: chúng không hề thay thế được nhau
Tôi vào bài với đúng cái hiểu nhầm phổ biến: BFS và DFS "như nhau, chỉ là hai cách duyệt, cùng O(V+E)" — nên cứ dùng cái nào tiện. Con số 1 998 so với 499 500 đập tan điều đó. Chúng không làm cùng một việc; chúng chỉ thăm cùng một tập đỉnh. BFS trả lời câu hỏi "đường ngắn nhất tới đích là bao nhiêu bước?"; DFS trả lời "có tồn tại một đường tới đích không, và đây là một trong số đó" — hai câu hỏi khác nhau, và trộn lẫn chúng là một lỗi âm thầm cho ra kết quả sai chứ không phải chậm.
Và có một khác biệt thứ hai, về bộ nhớ, cũng đo được rõ. Đỉnh bộ nhớ của BFS là 1 000 — bằng bề rộng của mặt sóng, tức số ô trong một tầng (đường chéo của lưới). Đỉnh bộ nhớ của DFS là 499 501 — bằng chiều sâu của nhánh nó đang lao. Hai con số này phình theo hai chiều khác nhau của đồ thị: BFS ngốn bộ nhớ theo bề rộng (một đồ thị bè ra nhiều nhánh sẽ có tầng khổng lồ, hàng đợi BFS nổ), DFS ngốn theo chiều sâu (một đồ thị dài ngoằng sẽ có nhánh cực sâu, ngăn xếp DFS nổ). Và nếu DFS viết bằng đệ quy, cái "ngăn xếp sâu" đó chính là ngăn xếp lời gọi của bài 17: tôi thử DFS đệ quy trên một đồ thị chuỗi dài một triệu đỉnh, nó tràn ngăn xếp và segfault đúng như đã đo ở bài đó, trong khi BFS và DFS viết bằng vòng lặp (ngăn xếp tường minh trên heap) chạy tốt. Bài học đo lường: "cùng độ phức tạp" chỉ nói về tổng công, không nói về cái chúng tìm ra hay bộ nhớ chúng ngốn theo chiều nào — và hai cái sau mới là thứ quyết định bạn chọn đúng hay sai.
DFS không phải BFS tồi — nó có việc riêng
Đừng đọc bài này thành "DFS thua BFS": nó chỉ khác việc. Đường dài 250 lần chỉ là điểm yếu khi bạn cần đường ngắn nhất — mà đó không phải việc DFS sinh ra để làm. DFS mạnh ở đúng những chỗ BFS vụng: phát hiện chu trình (đang lao sâu mà gặp lại một đỉnh còn trên nhánh hiện tại nghĩa là có vòng), sắp thứ tự tô-pô (thứ tự hoàn thành DFS đảo ngược cho ra thứ tự phụ thuộc), tìm thành phần liên thông, duyệt cây theo hậu tự. Với những bài này, lối "đi hết một nhánh rồi lui" của DFS là tự nhiên, còn BFS mới là cái vụng. Và trên một đồ thị sâu mà hẹp, DFS còn tiết kiệm bộ nhớ hơn BFS — chỉ giữ một nhánh thay vì cả một tầng. Điểm mấu chốt không phải cái nào tốt hơn, mà là chúng trả lời hai loại câu hỏi khác nhau.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên, thẳng và cụ thể: cần đường đi ngắn nhất trên đồ thị không trọng số thì dùng BFS, không phải DFS. Đây là lỗi hay gặp khi mới học đồ thị — dùng DFS (thường vì nó viết đệ quy gọn hơn) để tìm đường trong mê cung hay mạng lưới, rồi ngạc nhiên vì đường ra dài vô lý. DFS sẽ tìm được một đường, nhưng gần như chắc chắn không phải đường ngắn nhất. Ghi nhớ đơn giản: bề rộng cho khoảng cách ngắn nhất.
Hệ quả thứ hai: chọn giữa BFS và DFS theo hình dạng đồ thị và tài nguyên, không theo thói quen. Nếu đồ thị bè rộng (mỗi đỉnh nhiều hàng xóm, các tầng lớn), hàng đợi BFS có thể ngốn rất nhiều bộ nhớ — DFS tiết kiệm hơn ở đó. Nếu đồ thị sâu (nhánh dài), DFS đệ quy có nguy cơ tràn ngăn xếp — hãy dùng BFS, hoặc DFS với ngăn xếp tường minh. Mỗi thuật toán rẻ ở đúng chiều mà cái kia đắt; biết đồ thị của bạn phình theo chiều nào là biết chọn cái nào.
Hệ quả thứ ba là con số mang theo: BFS và DFS cùng O(V+E) nhưng tìm thứ khác hẳn — trên lưới 1000×1000, BFS cho đường ngắn nhất 1998 cạnh còn DFS cho đường 499500 cạnh (dài gấp 250 lần); bộ nhớ khác chiều — BFS theo bề rộng (1000), DFS theo chiều sâu (499501) — và DFS đệ quy tràn ngăn xếp trên đồ thị dài. Đừng để "cùng độ phức tạp" ru ngủ thành "thay thế được": hãy hỏi mỗi thuật toán tìm ra cái gì và ngốn bộ nhớ theo chiều nào, rồi chọn theo bài toán thật.
Thử ba mươi giây
Vẽ một lưới ô vuông nhỏ trên giấy, đánh dấu ô đầu và ô cuối, rồi tự "chạy" hai thuật toán bằng bút. Với BFS, tô lan đều thành từng vòng sóng quanh ô đầu — bạn sẽ thấy nó chạm ô cuối đúng lúc vừa đủ số bước, cho đường thẳng nhất. Với DFS, đi theo một hướng cố định (phải, rồi xuống, rồi trái...) cho tới khi kẹt mới quay lui — bạn sẽ thấy nó rắn rết khắp lưới, và đường tới đích dài lê thê. Cảm giác "sóng loang đều" so với "con rắn ngoằn ngoèo" đó là toàn bộ trực giác cần nhớ: BFS cho khoảng cách ngắn nhất và ngốn bộ nhớ theo bề rộng; DFS cho một đường bất kỳ và ngốn theo chiều sâu. Lần tới khi định dùng cái này cho việc của cái kia, nhớ tới con số 250 lần.
