无向图采用邻接表作为存储结构,设计一个算法,求解该图的连通分量个数并输出各连通分量的顶点集。
时间: 2024-05-07 15:18:33 浏览: 95
可以使用深度优先搜索(DFS)或广度优先搜索(BFS)遍历整个图,通过遍历过程中访问到的节点,来确定连通分量的个数以及各连通分量包含的节点。
以下是使用DFS实现的伪代码:
```
void DFS(int cur, vector<vector<int>>& adjList, vector<bool>& visited, vector<int>& component) {
visited[cur] = true;
component.push_back(cur);
for (int i = 0; i < adjList[cur].size(); i++) {
int next = adjList[cur][i];
if (!visited[next]) {
DFS(next, adjList, visited, component);
}
}
}
void getConnectedComponents(vector<vector<int>>& adjList) {
int n = adjList.size();
vector<bool> visited(n, false);
for (int i = 0; i < n; i++) {
if (!visited[i]) {
vector<int> component;
DFS(i, adjList, visited, component);
// 输出当前连通分量的顶点集
for (int j = 0; j < component.size(); j++) {
cout << component[j] << " ";
}
cout << endl;
}
}
}
```
在主函数中,可以先读入图的边集表示,然后构建邻接表,并调用`getConnectedComponents`函数进行连通分量的求解和输出。
阅读全文