用c++写一个完整程序设计一个图并分别进行深度遍历和广度遍历,然后逐行注释
时间: 2024-03-18 21:38:52 浏览: 59
基于C++进行图的深度优先遍历(高级语言程序设计实验)
下面是一个C++完整程序,实现了创建一个有向图,然后进行深度优先遍历和广度优先遍历。程序中有详细的注释,方便理解。
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
// 定义一个有向图类
class DirectedGraph {
public:
DirectedGraph(int n) {
// 初始化节点数
this->n = n;
// 初始化邻接表
adj.resize(n);
// 初始化visited数组
visited.resize(n);
}
// 添加一条有向边
void addEdge(int from, int to) {
adj[from].push_back(to);
}
// 深度优先遍历
void DFS(int node) {
// 初始化visited数组
fill(visited.begin(), visited.end(), false);
// 使用栈来实现DFS
stack<int> s;
s.push(node);
while (!s.empty()) {
int cur = s.top();
s.pop();
if (!visited[cur]) {
// 标记当前节点已经访问过
visited[cur] = true;
// 输出当前节点
cout << cur << " ";
// 将当前节点的所有邻居节点入栈
for (int i = adj[cur].size() - 1; i >= 0; i--) {
int neighbor = adj[cur][i];
if (!visited[neighbor]) {
s.push(neighbor);
}
}
}
}
cout << endl;
}
// 广度优先遍历
void BFS(int node) {
// 初始化visited数组
fill(visited.begin(), visited.end(), false);
// 使用队列来实现BFS
queue<int> q;
q.push(node);
while (!q.empty()) {
int cur = q.front();
q.pop();
if (!visited[cur]) {
// 标记当前节点已经访问过
visited[cur] = true;
// 输出当前节点
cout << cur << " ";
// 将当前节点的所有邻居节点入队
for (int neighbor : adj[cur]) {
if (!visited[neighbor]) {
q.push(neighbor);
}
}
}
}
cout << endl;
}
private:
int n; // 节点数
vector<vector<int>> adj; // 邻接表
vector<bool> visited; // 记录节点是否已经访问过
};
int main() {
// 创建一个有向图
DirectedGraph graph(6);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 3);
graph.addEdge(2, 4);
graph.addEdge(3, 5);
graph.addEdge(4, 5);
// 深度优先遍历
cout << "DFS: ";
graph.DFS(0);
// 广度优先遍历
cout << "BFS: ";
graph.BFS(0);
return 0;
}
```
这个程序创建了一个包含6个节点的有向图,然后进行了深度优先遍历和广度优先遍历,输出结果为:
```
DFS: 0 2 4 5 3 1
BFS: 0 1 2 3 4 5
```
可以看到,深度优先遍历和广度优先遍历得到的结果是不同的。
阅读全文