DFS & BFSthầy Phúc

So sánh: DFS và BFS cạnh nhau

Cùng một đồ thị, cùng một đỉnh xuất phát, cùng một khung duyệt. Chỉ khác cấu trúc cất tạm. Hãy xem hai thuật toán chạy đồng thời.

1. Chạy song song

Bấm Bước tiếp để cả hai bên cùng tiến một phép toán. Hãy để ý: bên DFS hàng chờ ngắn và sâu, bên BFS hàng chờ dài và phẳng.

Cùng một đồ thị, cùng xuất phát từ đỉnh 1

DFS — Ngăn xếp (stack)

12345678

Ngăn xếp (stack)

1
đáyđỉnh (lấy ra & đưa vào) ←

Đã thăm (0)

chưa có đỉnh nào

Thứ tự thăm

chưa thăm đỉnh nào
khởi tạo

Bắt đầu: đưa đỉnh 1 vào ngăn xếp.

BFS — Hàng đợi (queue)

1d=02345678

Hàng đợi (queue)

1
← đầu (lấy ra)đuôi (đưa vào) ←

Đã thăm (1)

1

Thứ tự thăm

chưa thăm đỉnh nào
khởi tạo

Bắt đầu: đưa đỉnh 1 vào hàng đợi và đánh dấu đã thăm. Khoảng cách d = 0.

2. Kết quả trên đồ thị mẫu

1122364355677488
DFS: 1 → 2 → 4 → 7 → 5 → 3 → 6 → 8
tầng 0tầng 1tầng 2tầng 31122334455667788
BFS: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8

Cạnh tô đậm là cây duyệt (DFS tree / BFS tree): với mỗi đỉnh, đó là cạnh mà thuật toán đã dùng để lần đầu chạm tới đỉnh đó. Hai cây khác nhau rõ rệt: cây DFS dài và mảnh, cây BFS thấp và xoè.

Điểm then chốt: cây BFS có tính chất mà cây DFS không có — đường từ gốc tới mỗi đỉnh trong cây BFS là đường đi ngắn nhất trong đồ thị gốc.

3. Bảng so sánh

DFS BFS
Tên đầy đủ Depth-First Search Breadth-First Search
Cấu trúc cất tạm ngăn xếp (stack) hàng đợi (queue)
Lấy ra đỉnh nào đỉnh mới nhất vừa đưa vào đỉnh cũ nhất trong hàng
Đánh dấu đã thăm khi lấy ra khi đưa vào
Cách lan cắm sâu một nhánh tới cùng phủ hết từng tầng
Viết đệ quy được không Có, và thường viết như vậy Không tự nhiên, hầu như luôn dùng vòng lặp
Thời gian O(V + E) O(V + E)
Bộ nhớ thực tế bằng độ sâu đường đi bằng tầng rộng nhất — thường lớn hơn
Cho đường đi ngắn nhất Không Có, trên đồ thị không trọng số
Có khái niệm tầng Không Có
Nguy cơ tràn ngăn xếp Có, nếu dùng đệ quy trên đồ thị sâu Không
Một đỉnh vào hàng chờ mấy lần có thể nhiều lần đúng một lần

4. Hai đoạn code cạnh nhau

Đặt cạnh nhau để thấy chỗ khác

// DFS                                    // BFS
stack<int> s;                             queue<int> q;
s.push(1);                                q.push(1);
                                          daTham[1] = true;   // đánh dấu khi ĐƯA VÀO
while (!s.empty()) {                      while (!q.empty()) {
    int u = s.top(); s.pop();                 int u = q.front(); q.pop();
    if (daTham[u]) continue;
    daTham[u] = true;   // khi LẤY RA
    for (int v : ke[u])                       for (int v : ke[u])
        if (!daTham[v]) s.push(v);                if (!daTham[v]) {
}                                                     daTham[v] = true;
                                                      q.push(v);
                                                  }
                                          }
# DFS                                     # BFS
s = [1]                                   q = deque([1])
                                          daTham[1] = True    # đánh dấu khi ĐƯA VÀO
while s:                                  while q:
    u = s.pop()                               u = q.popleft()
    if daTham[u]:
        continue
    daTham[u] = True   # khi LẤY RA
    for v in ke[u]:                           for v in ke[u]:
        if not daTham[v]:                         if not daTham[v]:
            s.append(v)                               daTham[v] = True
                                                      q.append(v)

Bốn chỗ khác nhau, và chỉ bốn:

  1. stack ↔ queue.
  2. Lấy từ cuối ↔ lấy từ đầu.
  3. Đánh dấu lúc lấy ra ↔ đánh dấu lúc đưa vào.
  4. Vì vậy DFS cần thêm if (daTham[u]) continue; còn BFS thì không.

5. Chọn cái nào cho bài của mình

Dạng bài Nên dùng Vì sao
Đếm thành phần liên thông (đếm đảo, đếm tỉnh, đếm nhóm) DFS Chỉ cần biết “đi được tới đâu”, không cần khoảng cách. Đệ quy ngắn hơn.
Kiểm tra hai đỉnh có nối được với nhau Cả hai Cùng độ phức tạp. Chọn cái nào viết nhanh hơn.
Đường đi ngắn nhất, số bước ít nhất BFS Tính chất tầng. DFS không đảm bảo gì.
Lan truyền theo thời gian (cam thối, cháy rừng, nhiễm bệnh) BFS Một tầng = một đơn vị thời gian.
Xử lý theo tầng (in cây theo tầng, nhìn cây từ bên phải) BFS Chỉ BFS có khái niệm tầng.
Phát hiện chu trình trên đồ thị có hướng DFS Cần biết “đỉnh nào đang nằm trên đường đi hiện tại” — đó là ngăn xếp đệ quy, ba màu.
Sắp xếp tô-pô DFS (hoặc BFS kiểu Kahn) Thứ tự đi ra khỏi đỉnh trong DFS cho ngay thứ tự tô-pô đảo.
Tìm mọi đường đi, mọi cách sắp xếp (quay lui) DFS Quay lui vốn là DFS trên cây trạng thái.
Đồ thị rất sâu, n tới 10⁵ và Python DFS bằng ngăn xếp, hoặc BFS Đệ quy sẽ tràn ngăn xếp.
Đồ thị rất rộng, mỗi tầng cực nhiều đỉnh cân nhắc DFS Hàng đợi BFS có thể ngốn hết bộ nhớ.

6. Ba hiểu nhầm cần bỏ

7. Tờ ghi nhớ

← Học lại DFSHọc lại BFS →