Chủ đề nền tảng HSG BFS / DFS / Đường đi Có mô phỏng tương tác

🕸️ ĐỒ THỊ – GRAPH
từ trực quan đến thuật toán

Đồ thị xuất hiện trong mạng xã hội, bản đồ đường đi, robot di chuyển, lịch thi, cây thư mục và rất nhiều bài lập trình thi đấu. Bài học này giúp học sinh hiểu chắc khái niệm đỉnh, cạnh, cách lưu đồ thị, BFS, DFS và cách nhận biết dạng bài.

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

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

Hiểu khái niệm

Đỉnh, cạnh, đồ thị có hướng, đồ thị vô hướng.

Biết cách lưu trữ

Danh sách cạnh, ma trận kề, danh sách kề.

Duyệt đồ thị

Nắm ý tưởng BFS, DFS và biết khi nào dùng.

Tránh lỗi phổ biến

Không nhầm hướng cạnh, chỉ số, visited, queue/stack.

Nhận diện bài

Lan truyền, đường đi ngắn nhất, phụ thuộc, chu trình.

Luyện tập phân tầng

Cơ bản → Trung bình → Nâng cao → HSG.

I. Đồ thị là gì?

Một đồ thị G gồm hai thành phần chính:

Đỉnh – Vertex

Là các đối tượng cần biểu diễn. Ví dụ: thành phố, học sinh, ô trên bàn cờ, tài khoản mạng xã hội.

Cạnh – Edge

Là mối liên hệ giữa hai đỉnh. Ví dụ: đường nối hai thành phố, quan hệ bạn bè, đường đi giữa hai ô.

Ví dụ đời sống: Nếu mỗi đỉnh là một thành phố, thì mỗi cạnh là một con đường nối giữa hai thành phố. Bài toán tìm đường đi chính là bài toán trên đồ thị.
1 2 3 4
Đồ thị ví dụ

Tập đỉnh: V = {1, 2, 3, 4}

Tập cạnh: E = {(1,2), (1,3), (2,4), (3,4)}

Điểm cần nhớ: Đồ thị không nhất thiết phải vẽ đẹp hay có hình dạng cố định. Quan trọng là biết đỉnh nào nối với đỉnh nào.

II. Đồ thị có hướng và vô hướng

Đồ thị vô hướng

Nếu có cạnh giữa u và v, ta có thể đi cả hai chiều: u → v và v → u.

adj[u].push_back(v);
adj[v].push_back(u); // thêm chiều ngược lại

Đồ thị có hướng

Nếu có cung u → v, chỉ đi được từ u sang v, không tự động đi ngược lại.

adj[u].push_back(v); // chỉ thêm một chiều
Lỗi rất hay gặp: Đề bài nói “đường hai chiều” nhưng chỉ viết adj[u].push_back(v). Khi đó chương trình thiếu cạnh ngược và kết quả BFS/DFS có thể sai.

III. Ba cách biểu diễn đồ thị

Với đồ thị ví dụ V = {1,2,3,4}, E = {(1,2), (1,3), (2,4), (3,4)}, ta có ba cách biểu diễn thường gặp.

Danh sách cạnh lưu trực tiếp từng cạnh. Dễ nhập dữ liệu, nhưng khi cần duyệt các đỉnh kề của một đỉnh thì chưa tối ưu.

(1, 2)
(1, 3)
(2, 4)
(3, 4)

Danh sách kề là cách dùng nhiều nhất trong lập trình thi đấu vì tiết kiệm bộ nhớ và duyệt cạnh nhanh.

123
214
314
423

Ma trận kề kiểm tra có cạnh hay không rất nhanh O(1), nhưng tốn bộ nhớ O(n²).

1234
10110
21001
31001
40110
Nên dùng danh sách kề khi: n lớn, m không quá dày, cần BFS/DFS, connected components, đường đi.
Nên dùng ma trận kề khi: n nhỏ và cần kiểm tra cạnh u-v rất nhiều lần.

IV. Code tạo danh sách kề

Đây là đoạn code nền tảng. Học sinh cần hiểu rõ từng dòng, đặc biệt là phần thêm cạnh hai chiều trong đồ thị vô hướng.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(n + 1);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;

        // Nếu đồ thị vô hướng: thêm cả hai chiều
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int i = 1; i <= n; i++) {
        cout << "Dinh " << i << ": ";
        for (int v : adj[i]) {
            cout << v << " ";
        }
        cout << "\n";
    }

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

for _ in range(m):
    u, v = map(int, input().split())

    # Nếu đồ thị vô hướng: thêm cả hai chiều
    adj[u].append(v)
    adj[v].append(u)

for i in range(1, n + 1):
    print("Dinh", i, ":", *adj[i])
Không nhầm: Nếu đề đánh số đỉnh từ 1 đến n thì nên tạo adj(n + 1). Nếu dùng adj(n) thì đỉnh n có thể gây lỗi truy cập ngoài mảng.

V. Duyệt đồ thị: BFS và DFS

Duyệt đồ thị nghĩa là đi qua các đỉnh có thể đến được từ một đỉnh bắt đầu. Hai thuật toán nền tảng là BFS và DFS.

BFS – duyệt theo tầng

Giống lan truyền từ nguồn ra xung quanh. Dùng queue. Rất quan trọng cho đường đi ngắn nhất trên đồ thị không trọng số.

DFS – duyệt theo chiều sâu

Đi sâu nhất có thể rồi quay lui. Dùng đệ quy hoặc stack. Hay dùng để tìm thành phần liên thông, chu trình, topo sort.

1 2 3 4

Mô phỏng BFS từ đỉnh 1

Nhấn “Bước tiếp” để thấy cách thuật toán lấy đỉnh ra và thêm các đỉnh chưa thăm.

Queue hiện tại
Đỉnh đã thăm
Nhật ký 
vector<int> vis(n + 1, 0);
queue<int> q;

q.push(1);
vis[1] = 1;

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

    for (int v : adj[u]) {
        if (!vis[v]) {
            vis[v] = 1;
            q.push(v);
        }
    }
}
vector<int> vis(n + 1, 0);

void dfs(int u) {
    vis[u] = 1;

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

VI. Những lỗi học sinh rất dễ nhầm

Nhầm 1-index và 0-index

Đề có đỉnh 1..n nhưng tạo mảng chỉ có n phần tử.

Dùng adj(n+1)
Quên cạnh ngược

Đồ thị vô hướng cần thêm cả u→v và v→u.

Viết đủ 2 dòng push
Không đánh dấu visited

Có thể lặp vô hạn khi đồ thị có chu trình.

Đánh dấu ngay khi đưa vào queue
Dùng BFS sai bài

BFS chỉ cho ngắn nhất khi mọi cạnh có trọng số bằng 1.

Có trọng số → học Dijkstra

VII. Nhận biết bài dùng đồ thị

Có “lan truyền”, “lây nhiễm”, “mỗi bước đi 4 hướng”
BFS
Đường đi ngắn nhất, mỗi cạnh có chi phí bằng 1
BFS khoảng cách
Kiểm tra có đi được từ s đến t không
BFS/DFS
Đếm số nhóm tách rời, đảo, vùng, thành phần
Connected Components
Có quan hệ phụ thuộc, thứ tự học môn, thứ tự công việc
Topo Sort
Cần phát hiện chu trình, vòng lặp phụ thuộc
DFS cycle

VIII. Các dạng bài quan trọng

Dạng 1

Connected Components

Đếm số thành phần liên thông. Duyệt từng đỉnh chưa thăm, mỗi lần gọi BFS/DFS là thêm một thành phần.

Dạng 2

Đường đi ngắn nhất BFS

Trên đồ thị không trọng số, BFS từ s để tính khoảng cách nhỏ nhất đến các đỉnh khác.

Dạng 3

Cycle Detection

Phát hiện chu trình trong đồ thị vô hướng hoặc có hướng. Cách kiểm tra hai loại này khác nhau.

Dạng 4

Topo Sort

Sắp xếp các đỉnh theo thứ tự phụ thuộc trong đồ thị có hướng không chu trình.

Dạng 5

SCC

Thành phần liên thông mạnh trong đồ thị có hướng, thường dùng Kosaraju hoặc Tarjan.

Dạng 6

Tree DP

Khi đồ thị là cây, có thể quy hoạch động trên cây: subtree size, đường kính, chọn đỉnh tối ưu.

IX. Kiểm tra nhanh

Câu 1. Đồ thị vô hướng có cạnh (u, v), cần thêm cạnh vào danh sách kề như thế nào?

Câu 2. BFS thường dùng cấu trúc dữ liệu nào?

Câu 3. Khi n rất lớn và m không quá dày, nên lưu đồ thị bằng cách nào?

Câu 4. BFS đảm bảo đường đi ngắn nhất trong trường hợp nào?

X. Bài tập luyện tập phân tầng

Bài tập được phân loại để học sinh không nhầm mục tiêu: phần đầu luyện cách lưu đồ thị, phần sau mới dùng BFS/DFS và các kỹ thuật nâng cao.

📘 Cơ bản Lưu đồ thị

  1. Nhập n, m và m cạnh. In danh sách kề của từng đỉnh.
  2. Đếm bậc của từng đỉnh trong đồ thị vô hướng.
  3. Đếm số cạnh đi ra của từng đỉnh trong đồ thị có hướng.
  4. Kiểm tra hai đỉnh u, v có cạnh nối trực tiếp hay không với n nhỏ.
Gợi ý tránh nhầm

Đồ thị vô hướng: bậc của đỉnh là adj[i].size(). Đồ thị có hướng: cần phân biệt bậc ra và bậc vào.

📗 Trung bình BFS / DFS

  1. Kiểm tra có đường đi từ s đến t hay không.
  2. Tìm số thành phần liên thông của đồ thị vô hướng.
  3. Tính khoảng cách ngắn nhất từ s đến mọi đỉnh trên đồ thị không trọng số.
  4. Kiểm tra đồ thị vô hướng có phải là cây hay không.
Gợi ý tránh nhầm

Cây vô hướng có n đỉnh cần liên thông và có đúng n - 1 cạnh.

📙 Nâng cao Chu trình / Topo

  1. Phát hiện chu trình trong đồ thị vô hướng.
  2. Phát hiện chu trình trong đồ thị có hướng.
  3. Sắp xếp topo các công việc có phụ thuộc.
  4. Tìm thứ tự học các môn học sao cho thỏa mãn điều kiện tiên quyết.
Gợi ý tránh nhầm

Chu trình vô hướng cần kiểm tra đỉnh cha. Chu trình có hướng thường dùng trạng thái 0/1/2 hoặc topo sort.

🐉 HSG Chuyên sâu

  1. Kosaraju tìm thành phần liên thông mạnh SCC.
  2. Tarjan tìm cầu và khớp trong đồ thị vô hướng.
  3. DP trên cây: kích thước cây con, chiều cao, đường kính.
  4. Multi-source BFS: nhiều nguồn lan truyền cùng lúc.
Gợi ý định hướng

Chỉ học phần này sau khi đã viết chắc DFS/BFS và hiểu danh sách kề.

XI. Mẫu lời giải: đếm thành phần liên thông

Đây là bài rất quan trọng. Ý tưởng: duyệt tất cả các đỉnh, nếu đỉnh đó chưa thăm thì bắt đầu một lần DFS/BFS mới và tăng số thành phần.

#include <bits/stdc++.h>
using namespace std;

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

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

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

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

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

    cout << components;
    return 0;
}
import sys
sys.setrecursionlimit(10**7)

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

for _ in range(m):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)

def dfs(u):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            dfs(v)

components = 0
for i in range(1, n + 1):
    if not visited[i]:
        components += 1
        dfs(i)

print(components)

Tổng kết

Nắm chắc đỉnh – cạnh – danh sách kề – BFS – DFS – visited là chìa khóa để giải phần lớn bài đồ thị cơ bản.

➡ Tiếp theo: Luyện bài BFS/DFS theo từng dạng để hình thành phản xạ nhận diện đề.

⬅️ Quay lại chương 9