写一段c++代码,假设无向图用邻接表表示,试写一个公开的成员函数,以深度优先遍历方式输出图中每个连通分量所含的顶点集合。 程序满足1、每个连通分量单独输出成一行; 2、函数返回值为图中连通分量个数。
时间: 2023-06-03 17:03:51 浏览: 123
很高兴为您提供代码解决方案,以下是C++代码:
```c++
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class Graph {
int V; // 顶点个数
vector<int> *adj; // 邻接表
public:
Graph(int V) {
this->V = V;
adj = new vector<int>[V];
}
void addEdge(int v, int w) {
adj[v].push_back(w);
adj[w].push_back(v);
}
int DFSUtil(int v, bool visited[], vector<int> &comp) {
visited[v] = true;
comp.push_back(v);
vector<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited, comp);
return comp.size();
}
int connectedComponents() {
bool *visited = new bool[V];
for (int v = 0; v < V; v++)
visited[v] = false;
int count = 0; // 连通分量个数
for (int v = 0; v < V; v++) {
if (!visited[v]) {
vector<int> comp;
int size = DFSUtil(v, visited, comp);
count++;
for (int i = 0; i < comp.size(); i++)
cout << comp[i] << " ";
cout << endl;
}
}
return count;
}
};
// 测试程序
int main() {
Graph g(5);
g.addEdge(1, 0);
g.addEdge(2, 3);
g.addEdge(3, 4);
cout << "Following are connected components" << endl;
int count = g.connectedComponents();
cout << "Number of connected components: " << count << endl;
return 0;
}
```
输出结果:
```
Following are connected components
0 1
2 3 4
Number of connected components: 2
```
当然,您可以将无向图的邻接表表示替换为您的实现。
希望能对您有所帮助!
阅读全文