2026 年 3 月 15 日刷题

今天的题目是有关 BFS 广度优先搜索的。BFS 可以理解是从树的顶端一层一层往下逐层遍历。维护一个队列，在遍历过程中不断加入符合要求的元素，最后当队列为空时返回。

207 课程表

这道题目是拓扑排序，就是将一张有向无环图按照层次来遍历，用 BFS。下面是代码实现。

class Solution { public: bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { vector<int> indegrees(numCourses,0); vector<vector<int>> adj(numCourses); for (auto element: prerequisites) { int ai = element[0]; int bi = element[1];//要学ai必须先学bi indegrees[ai]++; adj[bi].push_back(ai); } queue<int> que; //下面将入度为 0 的元素加入队列 for (int i = 0; i < numCourses; i++) { if (indegrees[i] == 0) { que.push(i); } } int completed = 0; while (!que.empty()) { int temp = que.front(); que.pop(); completed ++; for (int next : adj[temp]) { indegrees[next]--; if (indegrees[next] == 0) { que.push(next); } } } if (completed == numCourses) { return true; } return false; } };

200 岛屿数量

这道题目也是 BFS，直接上代码。

class Solution { public: int numIslands(vector<vector<char>>& grid) { if (grid.size() == 0 || grid[0].size() == 0) { return 0; } int rows = grid.size(); int columns = grid[0].size(); int count = 0; // 方向数组：上下左右四个方向 vector<pair<int, int>> dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}}; for (int i = 0; i < rows; i++) { for (int j = 0; j < columns; j++) { if (grid[i][j] == '1') { count++; queue<pair<int, int>> que; que.push({i,j}); grid[i][j] = '0'; while (!que.empty()) { pair<int, int> xy = que.front(); que.pop(); int x = xy.first; int y = xy.second; for (auto dir: dirs) { int dx = dir.first; int dy = dir.second; int nx = dx + x; int ny = dy + y; if (nx >= 0 && nx < rows && ny >= 0 && ny < columns && grid[nx][ny] == '1') { que.push({nx,ny}); grid[nx][ny] = '0'; } } } } } } return count; } };

C++ 中 queue 和 unordered_map

queue<T> que; que.push(A);//队尾入队 que.pop();//删除队头元素 que.front();//返回队头元素 que.back();//返回队尾元素 que.empty();//判断队列是否为空

unordered_map<T,N> map; map.insert(P);//插入键值对 map.count(key);//查看是否有这个 key map.erase(key);//删除键值 map.find(key);//查找这个键值是否存在，不存在返回 map.end()