假设无向图用邻接表表示,试写一个公开的成员函数,以深度优先遍历方式输出图中每个连通分量所含的顶点集合。
时间: 2023-06-04 19:09:00 浏览: 91
数据结构(visualc++)用邻接矩阵表示给定无向图并进行深度遍历.doc
好的,这是一个关于编程算法的问题,可以回答。以下是一个示例代码:
```c++
class Graph {
private:
// 图数据结构
vector<vector<int>> adjList;
public:
// 构造函数
Graph(vector<vector<int>> edges) : adjList(edges) {}
// 深度优先遍历函数
void DFSUtil(int v, vector<bool>& visited, vector<int>& component) {
visited[v] = true;
component.push_back(v);
for (int i = 0; i < adjList[v].size(); i++) {
int adjVertex = adjList[v][i];
if (!visited[adjVertex]) {
DFSUtil(adjVertex, visited, component);
}
}
}
// 输出连通分量函数
void printConnectedComponents() {
vector<bool> visited(adjList.size(), false);
// 遍历每个顶点
for (int v = 0; v < adjList.size(); v++) {
if (!visited[v]) {
vector<int> component;
DFSUtil(v, visited, component);
// 输出当前连通分量的顶点集合
cout << "Connected component:";
for (int i = 0; i < component.size(); i++) {
cout << " " << component[i];
}
cout << endl;
}
}
}
};
```
这个类中的 `DFSUtil` 函数用于执行深度优先遍历, `printConnectedComponents` 函数则用于输出每个连通分量的顶点集合。
阅读全文