图连通分量个数求解
时间: 2023-06-22 20:30:35 浏览: 76
图的连通分量个数可以通过深度优先搜索(DFS)或广度优先搜索(BFS)实现。
以DFS为例,可以从任意一个未被访问的节点开始,遍历其所有未被访问的邻居节点,并标记已访问。如果遍历完所有与该节点连通的节点后,还有未被访问的节点,就从其中一个未被访问的节点开始新的遍历,并增加连通分量计数器。
具体实现时,可以使用一个visited数组记录每个节点是否被访问过,以及一个count变量记录连通分量的个数。每次遍历一个新的连通分量时,count加1。
下面是一个基于DFS的连通分量求解的代码实现(假设使用邻接表表示图):
```
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);
}
}
}
int countConnectedComponents(vector<vector<int>>& graph) {
int n = graph.size();
vector<bool> visited(n, false);
int count = 0;
for (int u = 0; u < n; ++u) {
if (!visited[u]) {
dfs(graph, visited, u);
++count;
}
}
return count;
}
```
该算法的时间复杂度为O(V+E),其中V为节点数,E为边数。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)