用C++语言给出dfs和bfs算法模版,并且逐行注释
时间: 2024-09-28 20:17:23 浏览: 44
在C++中,深度优先搜索(Depth-First Search, DFS)和广度优先搜索(Breadth-First Search, BFS)是非常常见的图遍历算法。以下是它们的基本模板以及详细的注释:
```cpp
#include <iostream>
#include <vector> // 使用vector存储邻接表
// 定义一个边的数据结构,包含起点和终点
struct Edge {
int src, dest;
};
// 深度优先搜索模板函数,采用递归实现
void dfs(int node, std::vector<int>& visited, std::vector<Edge>& graph) {
// 标记当前节点已访问
visited[node] = true;
// 打印当前节点
std::cout << "Visiting node: " << node << "\n";
// 遍历邻居,如果未访问则继续DFS
for (Edge edge : graph[node]) {
if (!visited[edge.dest]) { // 如果邻居未访问
dfs(edge.dest, visited, graph); // 调用自身递归
}
}
}
// 广度优先搜索模板函数,采用队列实现
void bfs(int start, std::vector<int>& visited, std::vector<Edge>& graph) {
std::queue<int> q; // 创建一个队列用于存储待处理的节点
// 初始化队列和访问数组
visited[start] = true;
q.push(start);
while (!q.empty()) { // 当队列不为空
int curr_node = q.front(); // 取出队首节点
q.pop();
// 打印节点
std::cout << "Visiting node: " << curr_node << "\n";
// 将相邻未访问过的节点加入队列
for (Edge edge : graph[curr_node]) {
if (!visited[edge.dest]) {
visited[edge.dest] = true; // 更新访问状态
q.push(edge.dest); // 加入队列
}
}
}
}
阅读全文