Connected Components DFS/BFS đánh dấu cụm Đồ thị vô hướng

Thành phần liên thông trong đồ thị

Bài học này giúp em hiểu cách đếm số “cụm” đỉnh trong một đồ thị vô hướng. Mỗi cụm là một nhóm đỉnh có thể đi tới nhau bằng các cạnh. Ta sẽ dùng DFS hoặc BFS để tô màu từng cụm, giống như tìm các nhóm bạn quen biết nhau trong một mạng xã hội.

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

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

Hiểu component

Biết thành phần liên thông là một cụm đỉnh có thể đi tới nhau.

Đánh dấu visited

Biết dùng mảng vis để tránh duyệt lặp vô hạn.

Viết DFS/BFS

Đếm số thành phần liên thông bằng DFS hoặc BFS.

Tránh lỗi

Không nhầm với đồ thị có hướng, không chỉ duyệt từ đỉnh 1.

Ý tưởng cốt lõi

Khởi tạo tất cả đỉnh là chưa thăm. Duyệt lần lượt các đỉnh từ 1 đến n. Mỗi khi gặp một đỉnh chưa thăm, ta phát hiện một thành phần liên thông mới, tăng component thêm 1, rồi chạy DFS/BFS từ đỉnh đó để đánh dấu toàn bộ cụm.

Hình dung đời sống: Trong lớp học có nhiều nhóm bạn. Nếu em chọn một bạn chưa được xếp nhóm, sau đó tìm tất cả bạn có quan hệ trực tiếp/gián tiếp với bạn đó, ta thu được một nhóm. Lặp lại đến khi không còn bạn nào chưa xếp nhóm.
BướcViệc cần làmVì sao cần làm?
1Tạo danh sách kề adjLưu các đỉnh nối với nhau để DFS/BFS duyệt nhanh.
2Tạo mảng visBiết đỉnh nào đã thuộc một component.
3Duyệt tất cả đỉnh i = 1..nCó thể đồ thị không liên thông, nên không chỉ xuất phát từ đỉnh 1.
4Nếu vis[i] == false, tăng compMỗi lần gặp đỉnh chưa thăm là bắt đầu một cụm mới.
5Chạy DFS/BFS từ iĐánh dấu toàn bộ các đỉnh trong cùng cụm.

Mô phỏng trực quan: tô màu từng component

1 2 3 4 5 6 7 8

Đồ thị ví dụ có 8 đỉnh. Các cạnh: (1,2), (2,3), (1,3), (4,5), (6,7). Đỉnh 8 đứng một mình.

Trạng thái thuật toán

Component hiện tại: Chưa bắt đầu
Đã thăm:
Chưa có đỉnh nào.
Các nhóm đã tìm được:
Nhấn “Bước tiếp” để bắt đầu.
Sẵn sàng mô phỏng...

Code mẫu đếm số thành phần liên thông

Điểm dễ nhầm: Hàm DFS/BFS chỉ đánh dấu một cụm. Muốn đếm tất cả component, bắt buộc phải có vòng lặp ngoài for (i = 1..n). 
#include 
using namespace std;

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

void dfs(int u) {
    vis[u] = 1;
    for (int v : adj[u]) {
        if (!vis[v]) dfs(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); // đồ thị vô hướng
    }

    vis.assign(n + 1, 0);
    int comp = 0;

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

    cout << "So thanh phan lien thong: " << comp;
    return 0;
}
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)   # đồ thị vô hướng

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

vis = [False] * (n + 1)
comp = 0

for i in range(1, n + 1):
    if not vis[i]:
        comp += 1
        dfs(i, vis)

print("So thanh phan lien thong:", comp)

DFS hay BFS đều được

Với bài đếm thành phần liên thông, DFS và BFS đều có độ phức tạp O(n + m). Khác nhau chủ yếu ở cách duyệt: DFS đi sâu bằng đệ quy/ngăn xếp, còn BFS lan rộng bằng hàng đợi. 

int count_components_bfs(int n, vector>& adj) {
    vector vis(n + 1, 0);
    int comp = 0;

    for (int start = 1; start <= n; start++) {
        if (vis[start]) continue;

        comp++;
        queue q;
        q.push(start);
        vis[start] = 1;

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

            for (int v : adj[u]) {
                if (!vis[v]) {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }

    return comp;
}
from collections import deque

def count_components_bfs(n, adj):
    vis = [False] * (n + 1)
    comp = 0

    for start in range(1, n + 1):
        if vis[start]:
            continue

        comp += 1
        q = deque([start])
        vis[start] = True

        while q:
            u = q.popleft()

            for v in adj[u]:
                if not vis[v]:
                    vis[v] = True
                    q.append(v)

    return comp
Tiêu chíDFSBFS
Cấu trúc dữ liệuĐệ quy hoặc stackQueue
Khi nào tiện?Đếm component, tìm chu trình, duyệt câyKhoảng cách ngắn nhất trên đồ thị không trọng số
Lưu ýPython có thể lỗi độ sâu đệ quy nếu n lớnCần đánh dấu ngay khi đưa vào queue

Thực hành tương tác: nhập đồ thị và tìm component

Nhập số đỉnh và danh sách cạnh, sau đó nhấn Tìm component.
Input trong bài thi thường có dạng:
Dòng 1: n m
m dòng tiếp theo, mỗi dòng gồm hai đỉnh u v.

Mở rộng: in ra từng thành phần liên thông

Nếu đề bài yêu cầu không chỉ đếm số nhóm mà còn in các đỉnh trong từng nhóm, ta thêm một vector/list group để lưu các đỉnh được DFS duyệt trong component hiện tại. 

#include 
using namespace std;

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

void dfs(int u, vector& group) {
    vis[u] = 1;
    group.push_back(u);

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

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);
    }

    vis.assign(n + 1, 0);
    int comp = 0;

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            comp++;
            vector group;
            dfs(i, group);

            cout << "Nhom " << comp << ": ";
            for (int x : group) cout << x << " ";
            cout << "
";
        }
    }

    return 0;
}
def dfs(u, vis, group):
    vis[u] = True
    group.append(u)

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

vis = [False] * (n + 1)
comp = 0

for i in range(1, n + 1):
    if not vis[i]:
        comp += 1
        group = []
        dfs(i, vis, group)
        print("Nhom", comp, ":", *group)

Lỗi học sinh hay mắc

Chỉ gọi dfs(1)

Chỉ duyệt được component chứa đỉnh 1, bỏ sót các cụm khác.

Cách sửa

Luôn có vòng lặp ngoài: for i = 1..n, gặp đỉnh chưa thăm thì tăng comp và DFS/BFS.

Quên thêm cạnh ngược

Đề là đồ thị vô hướng nhưng chỉ viết adj[u].push_back(v).

Cách sửa

Với đồ thị vô hướng, phải thêm cả adj[u].push_back(v) và adj[v].push_back(u).

Nhầm liên thông mạnh

Thành phần liên thông mạnh chỉ dùng cho đồ thị có hướng và khó hơn.

Cách sửa

Bài này đang xét đồ thị vô hướng. Với đồ thị có hướng, cần học SCC như Kosaraju hoặc Tarjan.

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

Bài tập được chia theo mức độ để học sinh yếu, khá và giỏi đều có đường đi rõ ràng.

Cơ bản

  1. Nhập đồ thị vô hướng, in danh sách kề.
  2. Đếm bậc của từng đỉnh.
  3. Kiểm tra từ 1 có đi tới n không.

Trung bình

  1. Đếm số thành phần liên thông.
  2. In ra các đỉnh trong từng component.
  3. Tìm component có nhiều đỉnh nhất.

Nâng cao

  1. Đếm số cạnh cần thêm để đồ thị liên thông.
  2. Kiểm tra đồ thị có phải cây không.
  3. Đếm số component sau khi xóa một số cạnh.

HSG

  1. Liên thông trong lưới ô vuông.
  2. DSU đếm component động.
  3. So sánh DFS/BFS và DSU.
Công thức nhỏ: Nếu đồ thị vô hướng có comp thành phần liên thông, số cạnh ít nhất cần thêm để toàn bộ đồ thị liên thông là comp - 1.

Quiz kiểm tra nhanh

Câu 1

Vì sao phải duyệt tất cả đỉnh từ 1 đến n?

Câu 2

Đồ thị có 4 component. Cần thêm ít nhất bao nhiêu cạnh để liên thông?

➡ Tiếp theo: Đường đi ngắn nhất bằng BFS trên đồ thị không trọng số.

⬅️ Quay lại chương 9