Hình dung bạn khám phá một tòa nhà lạ. Có hai kiểu đi. Kiểu thứ nhất: đi hết cả một tầng — mở mọi cánh cửa trên tầng này — rồi mới xuống tầng dưới; muốn làm vậy bạn phải nhớ tất cả những cánh cửa đang chờ trên tầng hiện tại. Kiểu thứ hai: chọn một hành lang, đi thẳng tới cuối, đụng tường thì quay lại ngã rẽ gần nhất; bạn chỉ cần nhớ con đường từ cửa vào tới chỗ đang đứng. Kiểu thứ nhất là BFS (duyệt rộng trước), kiểu thứ hai là DFS (duyệt sâu trước) — và cái "phải nhớ bao nhiêu" ấy chính là khác biệt mà ít ai để ý.

Cả hai đều O(V+E) thời gian — chạm mọi đỉnh và cạnh đúng một lần. Sách thường trình bày chúng như "hai thứ tự duyệt khác nhau, chọn cái nào tùy bài toán", ngụ ý chi phí như nhau. Nhưng có một khác biệt lớn mà "O(V+E)" giấu đi: bộ nhớ đỉnh chúng đang giữ khác nhau — và khác đến mức một cái có thể ngốn cả gigabyte hoặc sập chương trình trong khi cái kia thảnh thơi, tùy hình dạng đồ thị. Tôi đo cả hai trong container gcc:13, và con số cho thấy "chọn BFS hay DFS" là một quyết định bộ nhớ, không chỉ thứ tự.

Hàng đợi giữ một tầng, ngăn xếp giữ một đường

BFS dùng một hàng đợi: nó xử lý hết tầng hiện tại trước khi sang tầng sau, nên tại mọi lúc hàng đợi giữ cả một tầng (frontier) các đỉnh chờ xử lý. Nếu đồ thị rộng — mỗi đỉnh có nhiều con — thì một tầng có thể khổng lồ. Bộ nhớ BFS là O(chiều rộng lớn nhất). Đây là "nhớ mọi cánh cửa trên tầng".

DFS dùng một ngăn xếp: nó đi sâu xuống một nhánh tới cùng rồi mới quay lại, nên ngăn xếp giữ một đường từ gốc xuống đỉnh hiện tại. Nếu đồ thị sâu — chuỗi dài — thì đường đó dài. Bộ nhớ DFS là O(chiều sâu lớn nhất). Đây là "nhớ con đường trong hành lang".

Và có một cái bẫy đặc biệt với DFS: nếu bạn viết DFS đệ quy (cách tự nhiên nhất), nó dùng ngăn xếp lời gọi hàm của chương trình, thường chỉ ~8 MB. Đồ thị sâu → đệ quy sâu → tràn ngăn xếp, chương trình sập (segfault). Đây không phải chậm — mà là chết.

Đo: BFS ngốn 500 lần ở đồ thị rộng, DFS tràn stack ở đồ thị sâu

Tôi đo đỉnh tối đa mà mỗi cách phải giữ, trên hai hình dạng đồ thị:

g++ -O2:

A. Đồ thị RỘNG NÔNG (cây phân nhánh 1000, ~1 triệu node):
   BFS hàng đợi tối đa : 1.000.000 đỉnh   (giữ cả một tầng = O(chiều rộng))
   DFS ngăn xếp tối đa :     1.999 đỉnh   (giữ một đường = O(chiều sâu nhỏ))
   -> BFS ngốn RAM gấp ~500 lần DFS

B. Đồ thị SÂU (chuỗi thẳng, độ sâu tới 1 triệu):
   BFS hàng đợi tối đa : 1 đỉnh   (mỗi tầng chỉ 1 đỉnh -> nhỏ xíu)
   DFS ĐỆ QUY          : chạy được tới độ sâu 200k, TRÀN STACK (segfault) ở 500k
                          (ngăn xếp chương trình mặc định 8 MB)
   C. Cách sửa: DFS LẶP với ngăn xếp tường minh trên heap -> không tràn

Nhìn A: trên cây phân nhánh cao (mỗi đỉnh 1000 con), khi BFS xuống tới tầng cuối, hàng đợi phải giữ cả một triệu đỉnh của tầng đó cùng lúc — vì BFS xử lý tầng theo tầng. DFS thì chỉ giữ 1.999 đỉnh (một đường từ gốc xuống, sâu 2 tầng). BFS ngốn RAM gấp 500 lần. Với đồ thị rộng, BFS có thể hết bộ nhớ trong khi DFS thảnh thơi.

Nhìn B: trên một chuỗi sâu, ngược lại hoàn toàn. BFS hàng đợi chỉ giữ 1 đỉnh mỗi lúc (mỗi tầng một đỉnh). Nhưng DFS đệ quy phải gọi hàm lồng nhau sâu bằng chiều dài chuỗi — và với ngăn xếp chương trình mặc định 8 MB, nó tràn ở độ sâu khoảng 500 nghìn (đo được: chạy xong ở 200k, segfault ở 500k). Chương trình sập. Cách cứu (C) là viết DFS lặp với một ngăn xếp tường minh đặt trên heap — heap lớn hơn nhiều và không giới hạn cứng như stack chương trình.

(Môi trường đo: container gcc:13 trên host ARM AArch64, g++ -O2, ngăn xếp chương trình mặc định 8 MB. Ngưỡng tràn stack đổi theo hệ và cỡ khung hàm; cái cần nhìn là dáng — BFS phình theo chiều rộng, DFS theo chiều sâu, và đệ quy có một trần cứng.)

Hai niềm tin đối nghịch, cùng sai

Tôi vào đo với niềm tin: "BFS và DFS đều O(V+E), chỉ khác thứ tự duyệt, bộ nhớ như nhau". Con số bác thẳng: bộ nhớ đỉnh đang giữ khác nhau theo hình dạng đồ thị — BFS ngốn RAM ở đồ thị rộng (500 lần), DFS ngốn ở đồ thị sâu. Không cái nào "ít nhớ hơn" tuyệt đối; nó phụ thuộc dữ liệu.

Nhưng niềm tin thứ hai còn phổ biến và nguy hiểm hơn: "DFS đệ quy là cách tự nhiên, viết vậy luôn ổn". Sai — đồ thị sâu làm đệ quy sâu, tràn ngăn xếp chương trình và sập ở độ sâu vài trăm nghìn. Với đồ thị lớn có đường dài (chuỗi phụ thuộc, cây khẳng khiu, danh sách liên kết coi như đồ thị), DFS đệ quy là một quả bom hẹn giờ — chạy ngon trên test nhỏ rồi segfault trên dữ liệu thật.

Về đến code hằng ngày

Điều đầu tiên: chọn BFS hay DFS theo hình dạng đồ thị và mục tiêu. Nếu đồ thị rộng nông (nhiều con mỗi đỉnh, ít tầng) và bạn lo bộ nhớ — DFS ít nhớ hơn. Nếu đồ thị sâu hẹp (đường dài) — BFS ít nhớ hơn, và tránh được tràn stack. Ngoài bộ nhớ, BFS còn cho đường đi ngắn nhất theo số cạnh (hữu ích cho tìm đường), DFS tự nhiên cho thứ tự topo, phát hiện chu trình, thành phần liên thông. Chọn theo cả hai.

Điều thứ hai: với đồ thị có thể sâu, dùng DFS lặp (stack tường minh), không đệ quy. Đây là một trong những nguyên nhân segfault khó chịu nhất trong xử lý đồ thị lớn: DFS đệ quy chạy tốt trên dữ liệu test nhỏ rồi sập trên dữ liệu thật có một chuỗi dài. Chuyển sang stack tường minh trên heap (hoặc tăng giới hạn stack, hoặc đảm bảo đệ quy đuôi để trình biên dịch tối ưu) loại bỏ rủi ro. Nhớ rằng "đồ thị" của bạn có thể sâu bất ngờ — một danh sách liên kết, một chuỗi phụ thuộc, một cây suy biến.

Chỗ này dân viết Java, Python hay làm hệ thống thật sẽ thấy đúng những vết xe đổ quen thuộc. Cả JVM lẫn CPython đều có trần đệ quy khá thấp — Python mặc định sys.setrecursionlimit khoảng 1000, và một DFS đệ quy trên đồ thị sâu ném RecursionError (hoặc StackOverflowError bên Java) đúng như segfault ở đây, chỉ là được bắt gọn hơn; đó là lý do các thư viện xử lý đồ thị và cây cú pháp lớn thường viết lại thành vòng lặp với stack tường minh. Ở tầng hệ thống, chính đánh đổi rộng-hay-sâu này quyết định kiến trúc: web crawler và trình duyệt mạng xã hội gần như luôn dùng BFS để lấy "hàng xóm gần trước" và giới hạn độ sâu, còn khi frontier phình quá RAM thì đẩy hàng đợi xuống đĩa hoặc Redis — đúng bài toán "một tầng khổng lồ" trong đo A. Cùng một câu hỏi khám-phá-theo-tầng-hay-theo-hành-lang, phóng to lên quy mô tỷ đỉnh.

Muốn tự thấy thì dựng hai đồ thị: một cây phân nhánh rất cao (mỗi đỉnh hàng trăm con, chỉ vài tầng) và một chuỗi thẳng rất dài (mỗi đỉnh một con, cả triệu tầng). Chạy BFS và DFS trên cả hai, đo số đỉnh tối đa trong hàng đợi (BFS) / ngăn xếp (DFS). Trên cây rộng, hàng đợi BFS phình lên cả một tầng khổng lồ trong khi ngăn xếp DFS chỉ bằng chiều sâu (nhỏ). Trên chuỗi sâu, ngược lại — và nếu bạn viết DFS đệ quy trên chuỗi triệu đỉnh, nó sẽ segfault vì tràn ngăn xếp chương trình. Vài phút đó cho bạn thấy điều mà "BFS và DFS đều O(V+E)" giấu đi: chi phí thời gian bằng nhau, nhưng chi phí bộ nhớ phụ thuộc hình dạng đồ thị — một cái ngốn RAM ở đồ thị rộng, cái kia sập ở đồ thị sâu. Chọn theo dữ liệu bạn thật sự có.