用C++将完整的代码展示出来
时间: 2024-03-10 07:45:18 浏览: 13
好的,以下是C++实现的深度优先遍历算法、广度优先遍历算法以及邻接表的创建方法的完整代码:
```c++
#include <iostream>
#include <list>
#include <queue>
#include <unordered_set>
using namespace std;
// 定义图的邻接表结构
class Graph {
public:
int V; // 顶点个数
list<int>* adj; // 邻接表指针
Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
// 添加边
void addEdge(int v, int w) {
adj[v].push_back(w);
}
};
// 深度优先遍历算法
void DFS(Graph& g, int start, unordered_set<int>& visited) {
visited.insert(start);
cout << start << " ";
for (int v : g.adj[start]) {
if (visited.find(v) == visited.end()) {
DFS(g, v, visited);
}
}
}
// 广度优先遍历算法
void BFS(Graph& g, int start) {
unordered_set<int> visited; // 记录已访问的顶点
queue<int> q; // 辅助队列
visited.insert(start);
q.push(start);
while (!q.empty()) {
int v = q.front();
q.pop();
cout << v << " ";
for (int w : g.adj[v]) {
if (visited.find(w) == visited.end()) {
visited.insert(w);
q.push(w);
}
}
}
}
int main() {
// 创建一个包含 4 个顶点的无向图
Graph g(4);
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(3, 0);
// 深度优先遍历
unordered_set<int> visited;
cout << "深度优先遍历: ";
DFS(g, 0, visited);
cout << endl;
// 广度优先遍历
cout << "广度优先遍历: ";
BFS(g, 0);
cout << endl;
return 0;
}
```
在这个示例代码中,我们使用了 STL 中的 list 和 unordered_set 容器来实现邻接表和记录已访问的顶点。同时,我们也使用了 STL 中的 queue 容器来实现广度优先遍历算法中的辅助队列。
希望这段代码能够对您有所帮助。