蓝桥杯C++DFS 与BFS

### 关于蓝桥杯中的DFS与BFS算法 #### 深度优先搜索 (DFS) 深度优先搜索是一种通过递归或者显式栈结构来遍历图或树的方法。它具有节省空间的特点，因为只需要保存当前路径上的节点信息[^1]。 以下是基于C++的一个典型DFS实现示例： ```cpp #include <iostream> #include <vector> using namespace std; // 定义方向数组，用于上下左右移动 const int dx[] = {-1, 1, 0, 0}; const int dy[] = {0, 0, -1, 1}; bool isValid(int x, int y, int n, int m, vector<string>& maze, vector<vector<bool>>& visited) { return x >= 0 && x < n && y >= 0 && y < m && !visited[x][y] && maze[x][y] != '#'; // 判断是否越界以及是否可走 } void dfs(int x, int y, vector<string>& maze, vector<vector<bool>>& visited, string& path) { if (maze[x][y] == 'E') { // 找到出口 cout << "Path found: " << path << endl; return; } for (int i = 0; i < 4; ++i) { int newX = x + dx[i]; int newY = y + dy[i]; if (isValid(newX, newY, maze.size(), maze[0].size(), maze, visited)) { visited[newX][newY] = true; char direction = ""; switch(i){ case 0: direction = 'U'; break; case 1: direction = 'D'; break; case 2: direction = 'L'; break; case 3: direction = 'R'; break; } path += direction; dfs(newX, newY, maze, visited, path); path.pop_back(); // 回溯 } } } ``` 上述代码展示了如何利用DFS在迷宫中寻找从起点到终点的路径。 --- #### 广度优先搜索 (BFS) 广度优先搜索则适合用来解决最短路径问题，在逐层扩展的过程中记录到达每个节点的距离[^2]。下面是一个典型的BFS实现例子： ```cpp #include <queue> #include <vector> #include <string> #include <iostream> using namespace std; struct Node { int x, y; string path; }; bool is_valid_move(int new_x, int new_y, const vector<string> &maze, const vector<vector<bool>> &visited) { return new_x >= 0 && new_x < maze.size() && new_y >= 0 && new_y < maze[0].size() && maze[new_x][new_y] != '#' && !visited[new_x][new_y]; // 验证新位置合法性和未访问状态 } string bfs(const vector<string> &maze, pair<int, int> start_pos) { queue<Node> q; vector<vector<bool>> visited(maze.size(), vector<bool>(maze[0].size(), false)); q.push(Node{start_pos.first, start_pos.second, ""}); visited[start_pos.first][start_pos.second] = true; while (!q.empty()) { Node current_node = q.front(); q.pop(); if (maze[current_node.x][current_node.y] == 'E') { return current_node.path; } static const int dir_x[] = {-1, 1, 0, 0}; // 上下左右偏移量 static const int dir_y[] = {0, 0, -1, 1}; static const char directions[] = {'U', 'D', 'L', 'R'}; for (int d = 0; d < 4; ++d) { int next_x = current_node.x + dir_x[d]; int next_y = current_node.y + dir_y[d]; if (is_valid_move(next_x, next_y, maze, visited)) { visited[next_x][next_y] = true; q.push(Node{next_x, next_y, current_node.path + directions[d]}); } } } return ""; // 如果找不到返回空字符串 } ``` 此段代码实现了使用BFS方法查找迷宫中最短路径的功能[^3]。 --- #### 总结对比 - **适用场景**: 当需要快速找到任意一条可行路径时，可以选择DFS；当目标是最优解（如最短距离），应考虑采用BFS。 - **性能考量**: 对于大规模数据集来说，由于内存占用的不同特性，可能需权衡两者之间的利弊再做决定.