假设无向图用邻接表表示,试写一段c++代码,包含一个公开的成员函数,以深度优先遍历方式输出图中每个连通分量所含的顶点集合。 程序满足1、每个连通分量单独输出成一行; 2、函数返回值为图中连通分量个数。
时间: 2024-03-18 11:39:39 浏览: 13
好的,以下是我为您编写的代码:
```c++
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class Graph {
private:
int V; // 顶点数
vector<vector<int> > adj; // 邻接表
public:
Graph(int V) {
this->V = V;
adj.resize(V);
}
void addEdge(int v, int w) {
adj[v].push_back(w);
adj[w].push_back(v);
}
int DFSUtil(int v, vector<bool>& visited, vector<int>& comp) {
visited[v] = true;
comp.push_back(v);
for (auto i = adj[v].begin(); i != adj[v].end(); ++i) {
if (!visited[*i]) {
DFSUtil(*i, visited, comp);
}
}
return 0;
}
int DFS() {
vector<bool> visited(V, false);
int count = 0;
for (int i = 0; i < V; ++i) {
if (!visited[i]) {
vector<int> comp;
DFSUtil(i, visited, comp);
for (auto j = comp.begin(); j != comp.end(); ++j) {
cout << *j << " ";
}
cout << endl;
count++;
}
}
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.DFS();
cout << "There are " << count << " connected components in the graph." << endl;
return 0;
}
```
这段代码中,我们定义了一个名为`Graph`的类,该类包含一个私有变量`V`表示图中顶点数,一个邻接表`adj`表示图的关系。我们在类中定义了一个公开成员函数`DFS`,该函数以深度优先遍历方式输出图中每个连通分量所含的顶点集合,并返回连通分量的个数。在函数内部,我们定义了一个`visited`数组,记录每个顶点是否被访问过,以及一个`count`变量,记录连通分量的个数。接着,我们遍历每个未被访问过的顶点,并调用DFSUtil函数进行深度优先遍历,将遍历到的顶点加入到一个`comp`数组中,表示同属于一个连通分量。当遍历完一个连通分量后,我们将该连通分量的所有顶点输出到屏幕上,并将`count`加1。最后,我们将`count`作为函数返回值,表示连通分量的个数。
希望这段代码能够帮助您解决问题。