BFS và DFS khác nhau thế nào? Chọn theo kết quả cần tìm

So sánh bằng một mục tiêu cụ thể

Bạn có thể học hai mẫu code rất giống nhau: một mẫu lấy ở đầu hàng đợi, mẫu còn lại lấy ở cuối stack. Nhưng quyết định dùng thuật toán nào không nên chỉ dựa vào số dòng code. Hãy bắt đầu từ việc đề bài cần trả về một giá trị khoảng cách, một nhóm đỉnh hay thông tin thứ tự xử lý.

BFS giữ thứ tự từng lớp khoảng cách. DFS đi sâu theo lựa chọn nhánh hiện tại, rồi quay về những việc còn chờ. Hai phép duyệt có thể gặp cùng tập đỉnh nhưng bằng các đường khác nhau. Mảng visited chỉ cho biết đỉnh đã được xử lý theo quy ước nào đó, không tự chứng minh mọi thông tin gắn lúc gặp đầu đều tối ưu.

Phản ví dụ: DFS gặp đích bằng đường dài hơn

Xét đồ thị vô hướng bốn đỉnh với cạnh 0–1, 1–2, 2–3 và 0–3. Từ 0 tới 3 có cạnh trực tiếp dài một bước, nhưng cũng có đường vòng 0–1–2–3 dài ba bước. Nếu DFS chọn đi nhánh 1 trước, nó có thể tới 3 theo đường vòng trước khi quay lại xét cạnh trực tiếp.

Không có mâu thuẫn: hai cột đang đo hai thứ khác nhau. Cột BFS là tối ưu số cạnh; cột DFS chỉ là độ sâu của đường mà mẫu duyệt chọn. Đổi thứ tự các hàng xóm có thể làm cột DFS khác đi nhưng không đổi khoảng cách BFS.

Code đối chiếu C++ và Python

#include <algorithm>
#include <functional>
#include <iostream>
#include <numeric>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
const long long INF=1LL<<60;
vector<int> compare_search(int n,const vector<pair<int,int>>&edges,int s){
    vector<vector<int>>adj(n);for(auto[u,v]:edges){adj[u].push_back(v);adj[v].push_back(u);}
    vector<int>b(n,-1),d(n,-1);queue<int>q;b[s]=0;q.push(s);
    while(!q.empty()){int u=q.front();q.pop();for(int v:adj[u])if(b[v]<0){b[v]=b[u]+1;q.push(v);}}
    vector<pair<int,int>>st{{s,0}};
    while(!st.empty()){
        auto[u,depth]=st.back();st.pop_back();if(d[u]>=0)continue;d[u]=depth;
        for(auto it=adj[u].rbegin();it!=adj[u].rend();++it)if(d[*it]<0)st.emplace_back(*it,depth+1);
    }
    b.insert(b.end(),d.begin(),d.end());return b;
}

int main(){int n=4,m,s=0;vector<pair<int,int>>edges={{0,1},{1,2},{2,3},{0,3}};
if(cin>>n>>m>>s){edges.resize(m);for(auto&[u,v]:edges)cin>>u>>v;}
for(auto x:compare_search(n,edges,s)) { cout<<x<<' '; }
cout<<'\n';}

INF=1<<60
def solve(n,edges,s):
    from collections import deque
    adj=[[] for _ in range(n)]
    for u,v in edges:adj[u].append(v);adj[v].append(u)
    b=[-1]*n;b[s]=0;q=deque([s])
    while q:
        u=q.popleft()
        for v in adj[u]:
            if b[v]<0:b[v]=b[u]+1;q.append(v)
    d=[-1]*n;st=[(s,0)]
    while st:
        u,depth=st.pop()
        if d[u]>=0:continue
        d[u]=depth
        for v in reversed(adj[u]):
            if d[v]<0:st.append((v,depth+1))
    return b+d

if __name__=='__main__':
    import sys
    d=list(map(int,sys.stdin.read().split()))
    if d:
        n,m=d[:2];off=3;s=0 if off==2 else d[2]
        width=2;edges=[tuple(d[i:i+width]) for i in range(off,off+width*m,width)]
    else:
        n,s,edges=4,0,[(0, 1), (1, 2), (2, 3), (0, 3)]
    print(*solve(n,edges,s))

Chạy ví dụ nhận tám số: bốn số đầu 0 1 2 1 là khoảng cách BFS, bốn số sau 0 1 2 3 là độ sâu DFS. Dữ liệu nhập riêng có n, m, s rồi m cạnh vô hướng; n dương và nguồn s hợp lệ. Trên đỉnh không đi tới được, cả hai phần trả -1.

Phần DFS của tệp dùng stack chứa cặp đỉnh và độ sâu, đưa hàng xóm theo thứ tự ngược để khám phá theo thứ tự của mẫu đệ quy. Nó đánh dấu khi lấy phần tử ra, nên có thể có mục chờ trùng; mục đã xử lý bị bỏ qua. Đây là thiết kế phục vụ so sánh đường khám phá, khác bản đếm thành phần đánh dấu ngay khi đưa vào stack ở bài DFS riêng.

Đừng trộn hai thời điểm đánh dấu rồi sao chép kết luận về thứ tự từ phiên bản này sang phiên bản kia. Với BFS chuẩn tính khoảng cách, code vẫn gán d trước khi enqueue để giữ chứng minh lần phát hiện đầu tối ưu và tránh đưa trùng đỉnh.

Bảng chọn nhanh theo yêu cầu

Với cây, giữa hai đỉnh chỉ có một đường đơn. Vì thế DFS tính số cạnh trên đường từ gốc có thể cho khoảng cách đúng trên cây. Tính chất đặc biệt này không được mang nguyên sang đồ thị có nhiều đường vòng như phản ví dụ trên.

Cả hai O(n+m), vậy bộ nhớ khác ra sao?

Trên danh sách kề, mỗi phép duyệt xử lý một số bước tuyến tính theo đỉnh và các mục kề. BFS chuẩn giữ mỗi đỉnh trong hàng tối đa một lần, nên bộ nhớ trạng thái O(n). DFS đệ quy có ngăn xếp theo độ sâu nhánh, cũng có thể O(n). Không nên nói DFS luôn dùng ít bộ nhớ hơn BFS hoặc ngược lại cho mọi đồ thị.

Trong một cây rất rộng nhưng nông, hàng chờ BFS có thể lớn. Trong một cây dài như dây, đệ quy DFS có thể sâu. Phiên bản DFS so sánh đánh dấu khi pop còn có các mục chờ trùng, nên stack có cận O(n+m) trong trường hợp tổng quát; đừng áp cận số đỉnh chờ của một phiên bản khác mà không xét cách cài.

Ngoài hàng chờ hoặc stack, chính dữ liệu đồ thị O(n+m) và các mảng trạng thái cũng chiếm bộ nhớ. Tối ưu thứ tự duyệt không thay đổi được chi phí lưu một danh sách cạnh quá lớn nếu bạn vẫn giữ nó trong chương trình.

BFS và DFS trên lưới ô vuông

Mỗi ô hợp lệ là một đỉnh; hai ô kề nhau là cạnh nếu luật cho phép di chuyển. Nếu mỗi bước đi lên/xuống/trái/phải có cùng giá, BFS tìm ít bước nhất tới đích. Nếu chỉ đếm số vùng cùng màu, DFS hoặc BFS đều có thể loang hết mỗi vùng rồi tăng biến đếm.

Không nhất thiết phải dựng danh sách kề đầy đủ cho từng ô. Có thể sinh hàng xóm bằng mảng hướng và kiểm biên ngay khi duyệt. Cần chốt 4 hướng hay 8 hướng theo đề, vì hai quy tắc tạo đồ thị khác nhau và có thể cho số vùng hoặc khoảng cách khác nhau.

Kiểm thử không khóa vào một thứ tự duyệt

Khi tự kiểm tra trên đồ thị nhỏ, bạn có thể đối chiếu mảng khoảng cách của BFS với độ dài đường đi ngắn nhất tìm bằng vét cạn. Với DFS, hãy kiểm tra tập đỉnh đi tới được trùng khớp với BFS và độ sâu mỗi đỉnh nằm trong miền hợp lệ, thay vì ép mọi cách cài đặt phải cho cùng một thứ tự thăm duy nhất.

Khi tự làm, thử đảo thứ tự cạnh nhập vào. Khoảng cách BFS phải giữ nguyên; thứ tự thăm hoặc đường DFS có thể thay đổi. Nếu bài chỉ yêu cầu một đường bất kỳ, đừng viết test từ chối các đáp án hợp lệ khác chỉ vì khác mẫu ban đầu.

Luyện ngay trên Big-O Coding

Bài đường ngắn nhất luyện BFS; bài tô màu luyện khả năng đi tới; đường kính cây giúp hiểu trường hợp cây có đường đơn duy nhất giữa hai đỉnh. Mỗi bài dùng một tính chất khác của phép duyệt.

Câu hỏi thường gặp

Nguồn tham khảo

• cp-algorithms: BFS
• cp-algorithms: DFS
• Open Data Structures: Graph Traversal