Khóa học Python từ Cơ bản đến Nâng cao

Bài 12.5 - Đếm thành phần liên thông trong Python

Trong một đồ thị vô hướng, thành phần liên thông (connected component) là một nhóm các đỉnh mà bạn có thể đi từ bất kỳ đỉnh nào đến bất kỳ đỉnh nào khác trong nhóm đó, bằng cách đi qua các cạnh.

Trong bài này, chúng ta sẽ học cách đếm số thành phần liên thông trong đồ thị bằng Python.

Đồ thị ví dụ

Giả sử ta có một đồ thị được biểu diễn dưới dạng danh sách kề:

graph = {
    0: [1],
    1: [0, 2],
    2: [1],
    3: [4],
    4: [3],
    5: []
}

Trong đồ thị trên:

• Thành phần liên thông 1: {0, 1, 2}
• Thành phần liên thông 2: {3, 4}

• Thành phần liên thông 3: {5} (một đỉnh cô lập)

  Tổng cộng: 3 thành phần liên thông

Cách tiếp cận

Ta sẽ:

1. Duyệt qua từng đỉnh.
2. Nếu đỉnh đó chưa được thăm, ta sẽ chạy DFS/BFS để đánh dấu toàn bộ thành phần chứa nó.
3. Mỗi lần làm như vậy, ta tăng biến đếm số thành phần lên 1.

Cài đặt DFS đếm thành phần liên thông

def count_connected_components(graph):
    visited = set()
    count = 0

    def dfs(node):
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                dfs(neighbor)

    for node in graph:
        if node not in visited:
            dfs(node)
            count += 1

    return count

Giải thích:

• visited: tập hợp các đỉnh đã duyệt.
• dfs(node): duyệt tất cả các đỉnh trong thành phần liên thông chứa node.
• Mỗi lần gặp đỉnh chưa thăm → tức là bắt đầu một thành phần mới.

Ví dụ minh hoạ

graph = {
    0: [1],
    1: [0, 2],
    2: [1],
    3: [4],
    4: [3],
    5: []
}

print("Số thành phần liên thông:", count_connected_components(graph))

Kết quả:

Số thành phần liên thông: 3

Đúng như mong đợi: {0,1,2}, {3,4}, {5}

Cách khác: Sử dụng BFS

from collections import deque

def count_components_bfs(graph):
    visited = set()
    count = 0

    for node in graph:
        if node not in visited:
            queue = deque([node])
            visited.add(node)
            while queue:
                current = queue.popleft()
                for neighbor in graph.get(current, []):
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)
            count += 1

    return count

Cách dùng BFS cũng tương tự DFS, chỉ khác ở cách duyệt qua hàng đợi thay vì đệ quy.

Độ phức tạp

• V: số đỉnh
• E: số cạnh

Bài tập mở rộng

• Đếm số thành phần liên thông trong đồ thị có hướng
• In ra các thành phần liên thông thay vì chỉ đếm
• Áp dụng với ma trận kề thay vì danh sách kề
• Biểu diễn đồ thị từ tập cạnh

Tổng kết

• Bài toán đếm thành phần liên thông là một ứng dụng thực tế quan trọng của DFS/BFS.
• Giải pháp đơn giản nhưng mạnh mẽ, có thể mở rộng sang nhiều dạng bài khác.
• Hiểu kỹ bài toán này sẽ giúp bạn dễ dàng tiếp cận với các bài toán liên thông mạnh, tô màu đồ thị, tìm cụm kết nối trong mạng xã hội,...