BFS (duyệt rộng trước) và DFS (duyệt sâu trước) là hai cách đi qua một đồ thị, và 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).
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).
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. 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ột lần tôi đo hớ: "bộ nhớ như nhau" và "DFS đệ quy luôn ổn"
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". Đo phá tan: 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. Còn niềm tin thứ hai, phổ biến và nguy hiểm: "DFS đệ quy là cách tự nhiên, 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 như đồ thị), DFS đệ quy là quả bom.
Bài học đo lường: BFS và DFS đều O(V+E) thời gian nhưng BỘ NHỚ khác theo HÌNH DẠNG — BFS hàng đợi giữ cả một tầng O(chiều rộng), ngốn RAM ở đồ thị RỘNG (cây phân nhánh 1000: hàng đợi tối đa 1 triệu đỉnh vs DFS ngăn xếp 1.999 = 500x); DFS ngăn xếp giữ một đường O(chiều sâu), và DFS ĐỆ QUY tràn ngăn xếp chương trình (8 MB) ở đồ thị SÂU (đo: chuỗi segfault ở độ sâu ~500k) — phải DFS LẶP với stack tường minh trên heap. Nếu tôi tin "bộ nhớ như nhau" tôi chọn nhầm cái ngốn RAM cho đúng hình dạng đồ thị của mình; nếu tôi tin "DFS đệ quy luôn ổn" tôi viết một chương trình sập với dữ liệu thật có đường dài.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầ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.
Hệ quả 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.
Hệ quả thứ ba là tinh thần đo lường: "cùng độ phức tạp thời gian" không có nghĩa "cùng bộ nhớ" — và bộ nhớ phụ thuộc dữ liệu, không chỉ thuật toán. Con số mang theo: BFS (queue, O(chiều rộng)) vs DFS (stack, O(chiều sâu)) — cùng O(V+E) thời gian nhưng bộ nhớ khác theo hình dạng: đồ thị RỘNG (cây B=1000, 1tr node) BFS hàng đợi 1 triệu đỉnh vs DFS 1.999 = ngốn 500x; đồ thị SÂU (chuỗi) BFS queue 1 vs DFS đệ quy TRÀN STACK (segfault ~500k, stack 8MB). BFS chết ở đồ thị rộng, DFS chết ở đồ thị sâu; DFS sâu phải dùng stack tường minh trên heap. Chọn theo hình dạng đồ thị, không theo "cái nào quen tay".
Thử ba mươi giây
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, và đ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. Ba mươi giây đó 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ó.
