假设无向图用邻接表表示,试写一段c++代码,包含一个公开的成员函数,以深度优先遍历方式输出图中每个连通分量所含的顶点集合。 程序满足1、每个连通分量单独输出成一行; 2、函数返回值为图中连通分量个数。
时间: 2023-06-03 07:04:07 浏览: 106
数据结构(visualc++)用邻接矩阵表示给定无向图并进行深度遍历借鉴.pdf
以下是代码实现:
```c
#include <iostream>
#include <vector>
using namespace std;
class Graph {
private:
int V; // 顶点个数
vector<int> *adj; // 邻接表
void DFSUtil(int v, bool visited[]);
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 DFS();
};
void Graph::DFSUtil(int v, bool visited[]) {
visited[v] = true;
cout << v << " ";
for(auto i = adj[v].begin(); i != adj[v].end(); ++i) {
if(!visited[*i]) {
DFSUtil(*i, visited);
}
}
}
int Graph::DFS() {
int count = 0;
bool *visited = new bool[V];
for(int i = 0; i < V; ++i) {
visited[i] = false;
}
for(int i = 0; i < V; ++i) {
if(!visited[i]) {
count++;
cout << "连通分量 " << count << ": ";
DFSUtil(i, visited);
cout << endl;
}
}
delete[] visited;
return count;
}
int main() {
Graph g(5);
g.addEdge(1, 0);
g.addEdge(2, 3);
g.addEdge(3, 4);
cout << "连通分量个数: " << g.DFS() << endl;
return 0;
}
```
输出结果为:
```
连通分量 1: 0 1
连通分量 2: 2 3 4
连通分量个数: 2
```
阅读全文