DFS和BFS是图遍历的基础算法，DFS用递归深入访问，BFS用队列实现层级遍历，均需标记已访问节点避免重复。
在C++中，深度优先搜索（DFS）和广度优先搜索（BFS）是图或树遍历的两种基础算法。它们常用于解决连通性、路径查找、拓扑排序等问题。下面分别给出基于邻接表存储的无向图的DFS和BFS实现代码。
1. 深度优先搜索（DFS）
DFS使用递归或栈来实现，优先深入访问未访问的邻接节点。
以下是一个用递归实现的DFS示例：
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
class Graph {
int n;
vector<vector<int>> 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<int> visited;
dfsHelper(start, visited);
}
private:
void dfsHelper(int u, unordered_set<int>& 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 <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
class Graph {
int n;
vector<vector<int>> 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<int> visited;
queue<int> 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<vector<int>> 存储邻接表，适合稀疏图。
- DFS用递归实现更简洁，注意标记已访问节点避免重复。
- BFS必须使用队列，确保按层次访问。
- 使用 unordered_set 记录访问状态，效率较高。
