Đếm thành phần liên thông

 Thuật toán đếm thành phần liên thông là một vấn đề quan trọng trong lĩnh vực đồ thị. Trong một đồ thị, một thành phần liên thông là một tập hợp các đỉnh sao cho từ mỗi đỉnh có thể đến được mọi đỉnh khác thông qua các cạnh của đồ thị đó. Để đếm số lượng thành phần liên thông trong một đồ thị, bạn có thể sử dụng một trong hai phương pháp chính: duyệt theo chiều rộng (Breadth-First Search - BFS) hoặc duyệt theo chiều sâu (Depth-First Search - DFS).

Dưới đây là mô tả thuật toán sử dụng DFS để đếm số thành phần liên thông trong một đồ thị không hướng:

Khởi tạo:

Tạo một mảng visited để đánh dấu các đỉnh đã được thăm. Ban đầu, tất cả các đỉnh đều chưa được thăm (visited[i] = false).
Xác định thành phần liên thông:

Khởi tạo biến count để đếm số thành phần liên thông. Ban đầu count = 0.
Lặp qua từng đỉnh của đồ thị. Với mỗi đỉnh, nếu đỉnh đó chưa được thăm:
Tăng count lên 1 (bắt đầu một thành phần liên thông mới).
Gọi hàm DFS từ đỉnh đó để thăm tất cả các đỉnh có thể đến được từ đỉnh đó và đánh dấu chúng trong mảng visited.
Thực hiện DFS:

Định nghĩa hàm DFS(v) với v là đỉnh hiện tại:
Đánh dấu đỉnh v là đã thăm (visited[v] = true).
Lặp qua tất cả các đỉnh kề với v. Với mỗi đỉnh kề u, nếu u chưa được thăm, gọi đệ quy DFS(u).
Kết quả:

Sau khi lặp qua tất cả các đỉnh, biến count sẽ chứa số thành phần liên thông của đồ thị.
Đây là một thuật toán cơ bản và hiệu quả để tìm kiếm các thành phần liên thông trong đồ thị, phù hợp cho cả đồ thị lớn do độ phức tạp thời gian là
𝑂
(
𝑉
+
𝐸
)
O(V+E), trong đó
𝑉
V là số đỉnh và
𝐸
E là số cạnh của đồ thị.

code giai thuat python c++
ChatGPT
Dưới đây là mã nguồn cho thuật toán đếm thành phần liên thông sử dụng DFS trên Python và C++:

Python
python
Sao chép mã
def dfs(v, visited, adj):
visited[v] = True
for u in adj[v]:
if not visited[u]:
dfs(u, visited, adj)

def count_components(n, adj):
visited = [False] * n
count = 0
for i in range(n):
if not visited[i]:
dfs(i, visited, adj)
count += 1
return count

# Ví dụ sử dụng
adj_list = [
[1, 2], # Đỉnh 0 kết nối với đỉnh 1 và 2
[0], # Đỉnh 1 kết nối với đỉnh 0
[0], # Đỉnh 2 kết nối với đỉnh 0
[4], # Đỉnh 3 kết nối với đỉnh 4
[3] # Đỉnh 4 kết nối với đỉnh 3
]

print("Số thành phần liên thông:", count_components(5, adj_list))
C++
cpp
Sao chép mã
#include <iostream>
#include <vector>
using namespace std;

void dfs(int v, vector<bool>& visited, vector<vector<int>>& adj) {
visited[v] = true;
for (int u : adj[v]) {
if (!visited[u]) {
dfs(u, visited, adj);
}
}
}

int count_components(int n, vector<vector<int>>& adj) {
vector<bool> visited(n, false);
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i, visited, adj);
count++;
}
}
return count;
}

int main() {
vector<vector<int>> adj_list = {
{1, 2}, // Đỉnh 0 kết nối với đỉnh 1 và 2
{0}, // Đỉnh 1 kết nối với đỉnh 0
{0}, // Đỉnh 2 kết nối với đỉnh 0
{4}, // Đỉnh 3 kết nối với đỉnh 4
{3} // Đỉnh 4 kết nối với đỉnh 3
};

cout << "Số thành phần liên thông: " << count_components(5, adj_list) << endl;
return 0;
}
Ở đây, chúng ta định nghĩa một hàm dfs để duyệt các đỉnh và một hàm count_components để tính toán số thành phần liên thông trong đồ thị. Ví dụ sử dụng cho cả Python và C++ đều được cung cấp để bạn có thể thấy cách chúng hoạt động với một đồ thị đơn giản.