c++基于深度优先搜索,统计邻接表存储图中的连通分量
时间: 2024-03-12 08:48:58 浏览: 18
可以使用深度优先搜索算法来统计邻接表存储图中的连通分量,具体实现步骤如下:
1. 定义一个数组visited用于记录每个节点是否被访问过,初始值为false。
2. 从第一个节点开始进行深度优先搜索,将其标记为已访问(visited[i] = true)。
3. 对于当前节点i的所有相邻节点j,如果j未被访问过,则递归访问j,并将其标记为已访问。
4. 当所有与当前节点i相邻的节点都被访问过后,回溯到上一个节点继续进行深度优先搜索,直到所有节点都被访问过。
5. 统计连通分量的数量,即深度优先搜索的次数。
以下是C++代码示例:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1005;
vector<int> graph[MAXN]; // 邻接表存储图
bool visited[MAXN]; // 记录每个节点是否被访问过
void dfs(int u) {
visited[u] = true;
for (int i = 0; i < graph[u].size(); i++) {
int v = graph[u][i];
if (!visited[v])
dfs(v);
}
}
int countComponents(int n) {
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
cnt++;
dfs(i);
}
}
return cnt;
}
int main() {
int n, m;
cin >> n >> m; // n为节点数,m为边数
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
int ans = countComponents(n);
cout << "There are " << ans << " connected components." << endl;
return 0;
}
```
注意,此处为无向图,如果是有向图,则只需将邻接表中加边的操作修改即可。