如何求一个无向图的连通分量的数
时间: 2023-10-20 11:06:49 浏览: 137
可以使用深度优先搜索或广度优先搜索遍历整个图,每次遍历一个未被访问的节点,就可以得到一个新的连通分量。最后,遍历完整个图后,连通分量的数就是访问过的次数。
具体实现可以使用一个数组记录每个节点是否被访问过,然后遍历所有未被访问过的节点,每当遍历到一个未被访问过的节点时,就从这个节点开始进行深度或广度优先搜索,访问所有与之相连的节点,直到遍历完所有与该节点相连的节点。这样,就得到了一个连通分量。重复这个过程,直到所有节点都被访问过为止。
以下是一个使用深度优先搜索求无向图连通分量数的示例代码:
```
int countComponents(vector<vector<int>>& graph) {
int n = graph.size();
vector<bool> visited(n, false);
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
count++;
dfs(graph, visited, i);
}
}
return count;
}
void dfs(vector<vector<int>>& graph, vector<bool>& visited, int u) {
visited[u] = true;
for (int v : graph[u]) {
if (!visited[v]) {
dfs(graph, visited, v);
}
}
}
```