用c++语言写一个程序完成图的深度优先遍历算法和广度优先遍历并给每行代码添加注释
时间: 2024-03-10 16:47:34 浏览: 92
好的,以下是深度优先遍历算法和广度优先遍历算法的示例代码(使用C++语言实现,并给每行代码添加了注释):
```c++
#include<iostream>
#include<queue> // 包含队列头文件
#include<stack> // 包含栈头文件
#include<unordered_map> // 包含无序哈希表头文件
#include<unordered_set> // 包含无序集合头文件
#include<vector> // 包含向量头文件
using namespace std;
// 图的表示方式:邻接表
unordered_map<int, unordered_set<int>> graph;
// 深度优先遍历算法
void dfs(int start, unordered_set<int>& visited) {
stack<int> st; // 用栈来实现深度优先遍历
st.push(start);
while (!st.empty()) {
int node = st.top(); // 取出栈顶元素
st.pop(); // 弹出栈顶元素
if (visited.find(node) == visited.end()) { // 如果该节点未被访问过
visited.insert(node); // 将该节点标记为已访问
for (const int& neighbor : graph[node]) { // 遍历该节点的邻居节点
st.push(neighbor); // 将邻居节点入栈
}
}
}
}
// 广度优先遍历算法
void bfs(int start, unordered_set<int>& visited) {
queue<int> q; // 用队列来实现广度优先遍历
q.push(start);
while (!q.empty()) {
int node = q.front(); // 取出队列头部元素
q.pop(); // 弹出队列头部元素
if (visited.find(node) == visited.end()) { // 如果该节点未被访问过
visited.insert(node); // 将该节点标记为已访问
for (const int& neighbor : graph[node]) { // 遍历该节点的邻居节点
q.push(neighbor); // 将邻居节点入队
}
}
}
}
int main() {
// 构建一个简单的图
graph[1] = {2, 3};
graph[2] = {1, 4, 5};
graph[3] = {1, 6};
graph[4] = {2};
graph[5] = {2, 6};
graph[6] = {3, 5};
unordered_set<int> visited; // 用无序集合记录已经访问过的节点
// 深度优先遍历
dfs(1, visited);
cout<<"深度优先遍历结果:";
for (const int& node : visited) {
cout<<node<<" ";
}
cout<<endl;
visited.clear(); // 清空visited
// 广度优先遍历
bfs(1, visited);
cout<<"广度优先遍历结果:";
for (const int& node : visited) {
cout<<node<<" ";
}
cout<<endl;
return 0;
}
```
该示例代码中,我们使用了邻接表来表示图,深度优先遍历算法使用栈实现,广度优先遍历算法使用队列实现。在测试代码中,我们构建了一个简单的图,并对其进行了深度优先遍历和广度优先遍历,输出了遍历结果。同时,我们将每行代码都添加了注释,以方便理解。
阅读全文