C++ BFS算法题全集：螺旋矩阵解析

"C++之bfs算法题汇总" 在C++编程中，广度优先搜索（BFS，Breadth-First Search）是一种用于遍历或搜索树或图的算法，它按照节点的层次顺序进行搜索。在这个C++的BFS算法题目汇总中，主要涉及了LeetCode平台上的原题，涵盖了多种类型的问题，通过代码实现来帮助理解BFS的应用。 首先，虽然标题提及的是BFS，但在描述中提到了DFS（深度优先搜索）。DFS与BFS都是图论和算法中的基本概念，但它们的搜索策略不同。DFS会尽可能深地探索树的分支，而BFS则优先访问距离起点近的节点。 在给定的部分内容中，提到了一道题目——"54.螺旋矩阵"，这道题虽然不是直接使用BFS解决，但展示了类似BFS的顺时针遍历策略。问题要求按照顺时针螺旋顺序返回矩阵中的所有元素。可以使用BFS的思想，模拟矩阵中的移动方向，即上、右、下、左四个方向，并在到达边界或已经访问过的位置时改变移动方向，实现螺旋式遍历。 ```cpp class Solution { public: vector<vector<int>> dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; vector<int> spiralOrder(vector<vector<int>>& matrix) { int m = matrix.size(); if (m == 0) return {}; int n = matrix[0].size(); vector<int> ans; vector<vector<bool>> used(m, vector<bool>(n, 0)); int index = 0; int row = 0, col = 0; for (int i = 0; i < m * n; i++) { ans.push_back(matrix[row][col]); // 判断是否撞墙或者撞到之前走过的 // 撞到的话就顺时针转向 int tempRow = row + dir[index % 4][0]; int tempCol = col + dir[index % 4][1]; if (tempRow >= m || tempRow < 0 || tempCol >= n || tempCol < 0 || used[tempRow][tempCol]) { index++; tempRow = row + dir[index % 4][0]; tempCol = col + dir[index % 4][1]; } row = tempRow; col = tempCol; used[row][col] = true; } return ans; } }; ``` 这个解决方案中，`dir`数组存储了四个可能的移动方向，`used`矩阵记录了哪些位置已经被访问过。在循环中，每次将当前位置的元素添加到结果数组`ans`中，然后尝试向下一个方向移动。如果遇到边界或者已访问的位置，就更新移动方向并继续前进。 除了“螺旋矩阵”问题，BFS在许多其他问题中也非常有用，例如在图的最短路径问题中寻找最短距离，如“两城之间的最短路径”；在树的层次遍历中，如“二叉树的层次遍历”；以及在有向图中寻找最短回路，如“拓扑排序”。 在面试和秋招中，熟练掌握BFS算法对于解决各种数据结构和算法问题至关重要。通过LeetCode等在线平台练习，可以不断提升自己的算法水平和编程能力。在C++中，BFS通常使用队列（queue）来实现，通过逐层扩展节点来保证遍历的顺序。理解和熟练运用BFS算法，不仅能够帮助解决实际问题，也是提升编程技能的有效途径。