图的bfs遍历
1.bfs 遍历是一种图的遍历方法, bfs 图上遍历的过程是, 从一个节点开始向四周开始扩散这种模式. bfs 需要借助队列进行实现, 首先将当前节点加入到队列中, 然后遍历队列, 拿到当前队列的邻居节点, 加入到队列中, 然后将当前节点删除
2.bfs 解决问题时, 通常需要关注的是遍历过程中是否已经到达的 target 终点
(i). 在遍历的过程中考虑到不走回头路, 需要用 visited 数组标记已经访问过
(ii). bfs 通常需要我们去找到最短的到达路径, 因此我们需要维护一个 step 变量标志我们扩散了几步
3.什么时候用 bfs 什么时候用 dfs? 首先 bfs 引入的队列带来额外的空间复杂度, 一般来说在寻找层次最短路径的时候用 bfs, 其他的时候用 dfs, 不考虑复杂度的情况下 bfs 写起来还是略微慢一些; 以下代码总结了bfs遍历给定问题的一般框架
int bfs(Node* start, Node* target) {
queue<Node*> q;
set<Node*> visited;
q.push_back(start);
visited.insert(start);
int step = 0;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; ++i) {
Node* cur = q.front();
if (cur == target) {
return step;
}
vector<Node*> neighbors = cur->neighbors;
for (Node* neighbor : neighbors) {
if (visited.find(neighbor) != visited.end()) {
q.push_back(neighbor);
visited.insert(neighbor);
}
}
q.pop_front();
++step;
}
}
return step;
}
111.二叉树的最小深度
给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明：叶子节点是指没有子节点的节点。
示例 1：输入：root = [3,9,20,null,null,15,7] 输出：2
示例 2：输入：root = [2,null,3,null,4,null,5,null,6] 输出：5
分析:
1.需要给出二叉树最小的深度, 所以我们根据根节点进行一个逐层的bfs可以满足要求, 最小深度对应的条件是当前节点左右孩子指针都为空.
2.这道题还可以用递归的方法来做, 代码非常简洁
class Solution {
public:
int minDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int depth = 1;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; ++i) {
TreeNode* cur = q.front();
q.pop();
if (cur->left == nullptr && cur->right == nullptr) {
return depth;
}
if (cur->left != nullptr)
q.push(cur->left);
if (cur->right != nullptr)
q.push(cur->right);
}
++depth;
}
return depth;
}
};
752.打开转盘锁
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，’0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。示例 1:输入：deadends = [“0201”,”0101”,”0102”,”1212”,”2002”], target = “0202” 输出：6
解释：
可能的移动序列为 “0000” -> “1000” -> “1100” -> “1200” -> “1201” -> “1202” -> “0202”。
注意 “0000” -> “0001” -> “0002” -> “0102” -> “0202” 这样的序列是不能解锁的，
因为当拨动到 “0102” 时这个锁就会被锁定。示例 2: 输入: deadends = [“8888”], target = “0009” 输出：1 解释：把最后一位反向旋转一次即可 “0000” -> “0009”。
示例 3: 输入: deadends = [“8887”,”8889”,”8878”,”8898”,”8788”,”8988”,”7888”,”9888”], target = “8888” 输出：-1
解释：无法旋转到目标数字且不被锁定。
分析:
1.这个题目的搜索空间为每位数字可以变为相邻的 2 个数字, 总共有 4 位数字, 那么从某个状态出发它的相邻节点就有 8 个邻居, 我们拿到初始的状态, 然后就可以对 8 个邻居节点进行搜索
2.因为要给出最小的旋转次数, 所以用 bfs 进行搜索
3.有一些边界条件是没有办法取到的, 比如命中deadends; 另外就是要防止某些状态已经被访问过了, 所以要记录 visited
class Solution {
public:
vector<string> getCandidates(string s) {
vector<string> ret;
for (int i = 0; i < 4; ++i) {
string up = s;
string down = s;
if (up[i] == '9') {
up[i] = '1';
} else {
up[i] = up[i] + 1;
}
if (down[i] == '0') {
down[i] = '9';
} else {
down[i] = down[i] - 1;
}
ret.push_back(up);
ret.push_back(down);
}
return ret;
}
int openLock(vector<string>& deadends, string target) {
queue<string> q;
unordered_set<string> visited;
unordered_set<string> deadendHash;
for (string deadend: deadends) {
deadendHash.insert(deadend);
}
q.push("0000");
visited.insert("0000");
int step = 0;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; ++i) {
string s = q.front();
q.pop();
if (s == target) {
return step;
}
if (deadendHash.find(s) != deadendHash.end()) {
continue;
}
vector<string> candidates = getCandidates(s);
for (string candi : candidates) {
if (visited.find(candi) == visited.end()) {
q.push(candi);
visited.insert(candi);
}
}
}
++step;
}
return -1;
}
};
773.滑动谜题
在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示。一次 移动 定义为选择 0 与一个相邻的数字（上下左右）进行交换.
最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
给出一个谜板的初始状态 board ，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。示例 1：输入：board = [[1,2,3],[4,0,5]] 输出：1 解释：交换 0 和 5 ，1 步完成
示例 2:输入：board = [[1,2,3],[5,4,0]] 输出：-1 解释：没有办法完成谜板
示例 3: 输入：board = [[4,1,2],[5,0,3]] 输出：5 解释：最少完成谜板的最少移动次数是 5 ，
一种移动路径:
尚未移动: [[4,1,2],[5,0,3]]
移动 1 次: [[4,1,2],[0,5,3]]
移动 2 次: [[0,1,2],[4,5,3]]
移动 3 次: [[1,0,2],[4,5,3]]
移动 4 次: [[1,2,0],[4,5,3]]
移动 5 次: [[1,2,3],[4,5,0]]
分析:
1.发生变化的状态是和0所在的位置进行交换, 因需要找到的是最少的移动次数, 所以需要用bfs
2.二维数组的交换空间是需要编码的, 这种编码起来比较复杂, 而且检查起来也很复杂, 一种简单的方式是将二维的数组转化为一维, 例如
[
[2,4,1],
[5,0,3]
]
我们把二维变换成一维
[2,4,1,5,0,3]
我们找 0 的交换邻居拿到 index
[1,3,5]
同理可以枚举 0 的其余5个位置, 得到可能的交换位置
vector<int> neighbors{{1,3}, {0,2,4}, {1,5}, {0,4}, {1,3,5}, {4,2}};
class Solution {
public:
string swapEle(string s, int zeroIdx, int neighborIdx) {
string ret = s;
swap(ret[zeroIdx], ret[neighborIdx]);
return ret;
}
int slidingPuzzle(vector<vector<int>>& board) {
string s = "";
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 3; ++j) {
s += to_string(board[i][j]);
}
}
vector<vector<int>> neighbors{{1,3}, {0,2,4}, {1,5}, {0,4}, {1,3,5}, {4,2}};
queue<string> q;
unordered_set<string> visited;
q.push(s);
visited.insert(s);
int step = 0;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; ++i) {
string cur = q.front();
q.pop();
if (cur == "123450") {
return step;
}
int zeroIdx = 0;
while (cur[zeroIdx] != '0') {
++zeroIdx;
}
for (int neighborIdx : neighbors[zeroIdx]) {
string newBoard = swapEle(cur, zeroIdx, neighborIdx);
if (visited.find(newBoard) == visited.end()) {
q.push(newBoard);
visited.insert(newBoard);
}
}
}
++step;
}
return -1;
}
};
994.腐烂的橘子
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；值 1 代表新鲜橘子；值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。示例 1：输入：grid =
[
[2,1,1],
[1,1,0],
[0,1,1]
] 输出：4示例 2：输入：grid =
[
[2,1,1],
[0,1,1],
[1,0,1]
]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。示例 3：输入：grid =
[
[0,2]
] 输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
分析:
1.模拟腐烂的过程, 对腐烂的橘子做广度优先搜索, 每一层数量分钟数增加1, 然后模拟新鲜的橘子变成了腐烂的橘子
2.在模拟腐烂进行 BFS 的过程中, 持续判断新鲜的橘子 > 0的, 如果新鲜橘子数量 == 0 了, 那么就停下来模拟, 返回结果
3.一开始遍历一下计数有多少个新鲜的橘子, 并将腐烂的橘子入队
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int rows = grid.size();
int cols = grid[0].size();
typedef pair<int, int> pii;
queue<pii> q;
const vector<vector<int>> dirs = {{-1,0},{1,0},{0,-1},{0,1}};
int freshCnt = 0;
// 维护新鲜橘子的个数
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (grid[i][j] == 1) {
++freshCnt;
} else if (grid[i][j] == 2) {
q.push(make_pair(i, j));
}
}
}
int minute = 0;
// 模拟腐烂的过程, bfs 实现
while (freshCnt > 0 && !q.empty()) {
++minute;
int len = q.size();
while (len > 0) {
pii cur = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
int nx = cur.first + dirs[k][0];
int ny = cur.second + dirs[k][1];
// 如果是个新鲜的橘子, 腐烂掉
if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == 1) {
grid[nx][ny] = 2;
--freshCnt;
q.push(make_pair(nx, ny));
}
}
--len;
}
}
if (freshCnt > 0) {
return -1;
} else {
return minute;
}
}
};
转载请注明来源, from goldandrabbit.github.io
