Graph Traversal BFS theo tầng DFS đi sâu

Duyệt đồ thị bằng DFS và BFS

Bài học này giúp em hiểu cách “đi thăm” các đỉnh trong đồ thị. DFS giống như đi sâu vào một con đường trước, còn BFS giống như lan truyền từng lớp từ điểm xuất phát. Đây là nền tảng để giải các bài: tìm đường đi, đếm thành phần liên thông, khoảng cách ngắn nhất trên đồ thị không trọng số.

Tiến độ bài học 0%

Mục tiêu bài học

Duyệt toàn bộ đồ thị

Biết cách dùng DFS và BFS để đi qua các đỉnh bắt đầu từ một đỉnh cho trước.

Cài đặt bằng code

Nắm được mẫu code C++ và Python với danh sách kề adj.

Phân biệt DFS / BFS

Không nhầm ngăn xếp/đệ quy của DFS với hàng đợi của BFS.

Ứng dụng đúng

Biết khi nào dùng BFS để tính khoảng cách ngắn nhất, khi nào dùng DFS để loang thành phần.

Lý thuyết cần nhớ

Giả sử đồ thị được lưu bằng danh sách kề adj. Mỗi adj[u] chứa các đỉnh kề với đỉnh u.

DFS – Depth First Search

DFS là duyệt sâu: đi sâu vào nhánh đầu tiên trước, sau đó quay lui.

  • Dùng đệ quy hoặc stack.
  • Phù hợp để: đếm thành phần liên thông, kiểm tra chu trình, duyệt cây.
  • Không đảm bảo đường đi ngắn nhất trên đồ thị không trọng số.

BFS – Breadth First Search

BFS là duyệt rộng: duyệt lần lượt từng lớp khoảng cách.

  • Dùng queue – hàng đợi.
  • Phù hợp để: tìm khoảng cách ngắn nhất khi mỗi cạnh có trọng số 1.
  • Thường dùng trong bài mê cung, lan truyền, mỗi bước đi 4 hướng.

Bảng phân biệt nhanh

Tiêu chíDFSBFS
Ý tưởngĐi sâu hết một nhánh rồi quay lại.Đi theo từng tầng quanh đỉnh xuất phát.
Cấu trúc dữ liệuĐệ quy hoặc stack.Queue.
Thứ tự trên ví dụ1 → 2 → 4 → 5 → 3 → 61 → 2 → 3 → 4 → 5 → 6
Dùng khiDuyệt thành phần, chu trình, cây, topo.Khoảng cách ngắn nhất không trọng số, lan truyền theo bước.
Lỗi hay gặpQuên đánh dấu visited trước khi đi tiếp.Đánh dấu visited quá muộn làm một đỉnh bị đưa vào queue nhiều lần.

Mô phỏng trực quan DFS / BFS

Đồ thị ví dụ có các cạnh: (1,2), (1,3), (2,4), (2,5), (3,6). Hãy bấm từng bước để thấy khác biệt.

1 2 3 4 5 6
Thuật toán đang chọn: BFS

Cấu trúc đang chờ xử lý

Đã thăm

Nhật ký

Ghi nhớ: Với cùng một đồ thị, thứ tự DFS/BFS có thể thay đổi nếu thứ tự trong danh sách kề thay đổi. Nếu đề yêu cầu duyệt theo đỉnh nhỏ trước, cần sort(adj[u].begin(), adj[u].end()) trong C++ hoặc adj[u].sort() trong Python.

Code mẫu đầy đủ

Hai chương trình dưới đây giữ đúng tinh thần bài gốc: đọc đồ thị vô hướng, duyệt DFS từ đỉnh 1, sau đó reset visited và duyệt BFS từ đỉnh 1.

#include 
using namespace std;

int n, m;
vector> adj;
vector visited;

void dfs(int u) {
    visited[u] = 1;
    cout << u << " ";

    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

void bfs(int start) {
    queue q;
    q.push(start);
    visited[start] = 1;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";

        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = 1;  // đánh dấu ngay khi đưa vào queue
                q.push(v);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    adj.assign(n + 1, {});

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u); // vì đồ thị vô hướng
    }

    visited.assign(n + 1, 0);
    cout << "DFS: ";
    dfs(1);

    cout << "
BFS: ";
    visited.assign(n + 1, 0); // rất quan trọng: reset trước khi BFS
    bfs(1);

    return 0;
}
from collections import deque

n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]

for _ in range(m):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)   # vì đồ thị vô hướng

def dfs(u, visited):
    visited[u] = True
    print(u, end=' ')

    for v in adj[u]:
        if not visited[v]:
            dfs(v, visited)

def bfs(start):
    visited = [False] * (n + 1)
    q = deque([start])
    visited[start] = True

    while q:
        u = q.popleft()
        print(u, end=' ')

        for v in adj[u]:
            if not visited[v]:
                visited[v] = True  # đánh dấu ngay khi đưa vào queue
                q.append(v)

visited = [False] * (n + 1)
print("DFS:", end=' ')
dfs(1, visited)

print("
BFS:", end=' ')
bfs(1)
Vì sao phải có visited? Nếu đồ thị có cạnh hai chiều, từ 1 đi sang 2 rồi từ 2 lại quay về 1. Không có visited, chương trình có thể lặp vô hạn hoặc gọi đệ quy không dừng.

BFS tính khoảng cách ngắn nhất

BFS rất quan trọng vì khi đồ thị không trọng số, BFS cho ta số cạnh ít nhất từ đỉnh bắt đầu đến mỗi đỉnh.

vector dist(n + 1, -1);
queue q;

int start = 1;
dist[start] = 0;
q.push(start);

while (!q.empty()) {
    int u = q.front();
    q.pop();

    for (int v : adj[u]) {
        if (dist[v] == -1) {
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
}

for (int i = 1; i <= n; i++) {
    cout << "dist[" << i << "] = " << dist[i] << "
";
}
from collections import deque

dist = [-1] * (n + 1)
start = 1
q = deque([start])
dist[start] = 0

while q:
    u = q.popleft()

    for v in adj[u]:
        if dist[v] == -1:
            dist[v] = dist[u] + 1
            q.append(v)

for i in range(1, n + 1):
    print(f"dist[{i}] = {dist[i]}")
Không nhầm: BFS chỉ cho đường đi ngắn nhất khi mỗi cạnh có cùng chi phí, thường là 1. Nếu cạnh có trọng số khác nhau, cần học Dijkstra hoặc thuật toán khác.

Thực hành nhanh: tự nhập đồ thị

Nhập số đỉnh, danh sách cạnh, chọn BFS hoặc DFS để xem thứ tự duyệt. Công cụ này giúp học sinh kiểm tra nhanh cách thuật toán hoạt động.

Thứ tự duyệt:
Chưa chạy.
Ghi chú:
BFS dùng queue, DFS dùng đệ quy trong mô phỏng.

Lỗi học sinh hay nhầm

Nhầm BFS với DFS

Thấy đều duyệt đồ thị nên dùng lẫn lộn, dẫn đến sai ở bài cần khoảng cách ngắn nhất.

Cách nhớ

BFS có chữ Breadth: duyệt rộng theo tầng, dùng queue. DFS có chữ Depth: đi sâu, dùng đệ quy/stack.

Quên reset visited

Chạy DFS xong rồi BFS ngay, nhưng các đỉnh vẫn đang bị đánh dấu đã thăm.

Cách sửa

Trước mỗi lần duyệt mới, dùng visited.assign(n + 1, 0) trong C++ hoặc tạo lại list trong Python.

Tưởng duyệt từ 1 là duyệt hết đồ thị

Nếu đồ thị không liên thông, bắt đầu từ 1 chỉ đi được trong thành phần chứa đỉnh 1.

Cách sửa

Muốn duyệt toàn bộ đồ thị, cần vòng lặp for i = 1..n, nếu chưa thăm thì gọi DFS/BFS từ i.

Bài tập luyện tập phân loại rõ

Bài tập được chia thành nhiều nhóm để học sinh luyện đúng kỹ năng, tránh học thuộc code nhưng không biết dùng vào dạng bài nào.

Mức 1: Duyệt cơ bản

  1. Duyệt DFS từ đỉnh 1, in thứ tự duyệt.
  2. Duyệt BFS từ đỉnh 1, in thứ tự duyệt.
  3. In các đỉnh chưa được thăm sau khi duyệt từ 1.

Mức 2: BFS khoảng cách

  1. Tính khoảng cách từ 1 đến mọi đỉnh.
  2. Tìm số cạnh ít nhất từ s đến t.
  3. In -1 nếu không đi được từ s đến t.

Mức 3: DFS thành phần

  1. Đếm số thành phần liên thông.
  2. In kích thước từng thành phần.
  3. Kiểm tra đồ thị có liên thông không.

Mức 4: So sánh

  1. Chạy DFS và BFS trên cùng đồ thị.
  2. Giải thích vì sao thứ tự khác nhau.
  3. Sắp xếp danh sách kề rồi so sánh lại.

int components = 0;
visited.assign(n + 1, 0);

for (int i = 1; i <= n; i++) {
    if (!visited[i]) {
        components++;
        dfs(i);
    }
}

cout << components;

from collections import deque

dist = [-1] * (n + 1)
dist[1] = 0
q = deque([1])

while q:
    u = q.popleft()
    for v in adj[u]:
        if dist[v] == -1:
            dist[v] = dist[u] + 1
            q.append(v)

print(dist[1:])

Quiz kiểm tra nhanh

Câu 1

Bài yêu cầu “số cạnh ít nhất từ s đến t” trên đồ thị không trọng số. Nên dùng gì?

Câu 2

Chạy DFS xong muốn chạy BFS lại trên cùng đồ thị, thao tác nào rất quan trọng?

Tổng kết

  • DFS: đi sâu, dùng đệ quy/stack, mạnh trong bài thành phần liên thông, chu trình, cây.
  • BFS: đi rộng theo tầng, dùng queue, mạnh trong bài khoảng cách ngắn nhất không trọng số.
  • visited là bắt buộc để tránh duyệt lặp.
  • Muốn duyệt hết đồ thị không liên thông, phải thử từ mọi đỉnh chưa được thăm.

➡ Tiếp theo: Thành phần liên thông và đường đi trong đồ thị.

⬅️ Quay lại chương 9