DFS和BFS是图遍历的基础算法，DFS用递归深入访问，BFS用队列实现层级遍历，均需标记已访问节点避免重复。
在C++中，深度优先搜索（DFS）和广度优先搜索（BFS）是图或树遍历的两种基础算法。它们常用于解决连通性、路径查找、拓扑排序等问题。下面分别给出基于邻接表存储的无向图的DFS和BFS实现代码。
1. 深度优先搜索（DFS）
DFS使用递归或栈来实现，优先深入访问未访问的邻接节点。
以下是一个用递归实现的DFS示例：
#include #include #include using namespace std;class Graph { int n; vector<vector> adj;public: Graph(int n) : n(n), adj(n) {} void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); // 无向图 } void dfs(int start) { unordered_set visited; dfsHelper(start, visited); }private: void dfsHelper(int u, unordered_set& visited) { visited.insert(u); cout << u << " "; for (int v : adj[u]) { if (!visited.count(v)) { dfsHelper(v, visited); } } }};// 使用示例int main() { Graph g(5); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(2, 4); cout << "DFS traversal: "; g.dfs(0); cout << endl; return 0;}
2. 广度优先搜索（BFS）
BFS使用队列实现，逐层访问相邻节点，适合求最短路径。
立即学习“C++免费学习笔记（深入）”；
#include #include #include #include using namespace std;class Graph { int n; vector<vector> adj;public: Graph(int n) : n(n), adj(n) {} void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } void bfs(int start) { unordered_set visited; queue q; visited.insert(start); q.push(start); while (!q.empty()) { int u = q.front(); q.pop(); cout << u << " "; for (int v : adj[u]) { if (!visited.count(v)) { visited.insert(v); q.push(v); } } } }};// 使用示例int main() { Graph g(5); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(2, 4); cout << "BFS traversal: "; g.bfs(0); cout << endl; return 0;}
关键点说明：图使用 vector> 存储邻接表，适合稀疏图。DFS用递归实现更简洁，注意标记已访问节点避免重复。BFS必须使用队列，确保按层次访问。使用 unordered_set 记录访问状态，效率较高。基本上就这些。掌握这两种基本写法后，可扩展用于迷宫求解、岛屿数量、二叉树层序遍历等场景。
以上就是c++++ dfs和bfs代码 c++深度广度优先搜索算法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1487190.html
微信扫一扫 
支付宝扫一扫 
