假设无向图用邻接表表示,试写一段c++代码,包含一个公开的成员函数,以深度优先遍历方式输出图中每个连通分量所含的顶点集合。 程序满足1、每个连通分量单独输出成一行; 2、函数返回值为图中连通分量个数。
时间: 2024-03-18 21:40:08 浏览: 15
好的,以下是满足要求的C++代码:
```c++
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class Graph {
private:
int V; // 顶点数
vector<int>* adj; // 邻接表
void DFSUtil(int v, bool visited[]); // 深度优先遍历函数
public:
Graph(int V); // 构造函数
void addEdge(int v, int w); // 添加边
int DFS(); // 深度优先遍历函数,返回连通分量个数
};
Graph::Graph(int V) {
this->V = V;
adj = new vector<int>[V];
}
void Graph::addEdge(int v, int w) {
adj[v].push_back(w);
adj[w].push_back(v);
}
void Graph::DFSUtil(int v, bool visited[]) {
visited[v] = true;
cout << v << " ";
vector<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i) {
if (!visited[*i]) {
DFSUtil(*i, visited);
}
}
}
int Graph::DFS() {
bool* visited = new bool[V];
int count = 0;
for (int i = 0; i < V; i++) {
visited[i] = false;
}
for (int i = 0; i < V; i++) {
if (!visited[i]) {
count++;
cout << "Component " << count << ": ";
DFSUtil(i, visited);
cout << endl;
}
}
return count;
}
int main() {
Graph g(5);
g.addEdge(1, 0);
g.addEdge(2, 3);
g.addEdge(3, 4);
cout << "Number of connected components: " << g.DFS() << endl;
return 0;
}
```
在这段代码中,我们定义了一个Graph类来表示图,并在其中实现了一个深度优先遍历函数DFSUtil和一个返回连通分量个数的函数DFS。首先,我们在构造函数中初始化了邻接表,然后在addEdge函数中添加边。DFSUtil函数使用递归实现深度优先遍历,并打印每个连通分量所含的顶点。DFS函数使用一个bool类型的visited数组来记录每个顶点是否被访问过,并在遍历过程中调用DFSUtil函数。最后,我们在主函数中构造了一个5个顶点的无向图,并输出了它的连通分量个数。