每次都尝试访问同一层的节点。 如果同一层都访问完了，再访问下一层。
这样做的结果是，BFS 算法找到的路径是从起点开始的 最短 合法路径。换言之，这条路所包含的边数最小。
在 BFS 结束时，每个节点都是通过从起点到该点的最短路径访问的。
// 计算从起点 start 到终点 target 的最近距离 int BFS(Node start, Node target) { Queue<Node> q; // 核心数据结构 Set<Node> visited; // 避免走回头路 q.offer(start); // 将起点加入队列 visited.add(start); int step = 0; // 记录扩散的步数 while (q not empty) { int sz = q.size(); /* 将当前队列中的所有节点向四周扩散 */ for (int i = 0; i < sz; i++) { Node cur = q.poll(); /* 划重点：这里判断是否到达终点 */ if (cur is target) return step; /* 将 cur 的相邻节点加入队列 */ for (Node x : cur.adj()) if (x not in visited) { q.offer(x); visited.add(x); } } /* 划重点：更新步数在这里 */ step++; } }队列 就不说了，BFS 的核心数据结构；cur.adj() 泛指 cur 相邻的节点，比如说二维数组中，cur 上下左右四面的位置就是相邻节点；visited 的主要作用是防止走回头路，大部分时候都是必须的，但是像一般的二叉树结构，没有子节点到父节点的指针，不会走回头路就不需要 visited。
给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明:叶子节点是指没有子节点的节点。
直接套用框架，修改循环的终点和添加步数
int minDepth(TreeNode root) { if (root == null) return 0; Queue<TreeNode> q = new LinkedList<>(); q.offer(root); // root 本身就是一层，depth 初始化为 1 int depth = 1; while (!q.isEmpty()) { int sz = q.size(); /* 将当前队列中的所有节点向四周扩散 */ for (int i = 0; i < sz; i++) { TreeNode cur = q.poll(); /* 判断是否到达终点 */ if (cur.left == null && cur.right == null) return depth; /* 将 cur 的相邻节点加入队列 */ if (cur.left != null) q.offer(cur.left); if (cur.right != null) q.offer(cur.right); } /* 这里增加步数 */ depth++; } return depth; }你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有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 解释： 无法旋转到目标数字且不被锁定。示例 4:
输入: deadends = ["0000"], target = "8888" 输出：-1提示：
死亡列表 deadends 的长度范围为 [1, 500]。 目标数字 target 不会在 deadends 之中。 每个 deadends 和 target 中的字符串的数字会在 10,000 个可能的情况 '0000' 到 '9999' 中产生第一步，我们不管所有的限制条件，不管 deadends 和 target 的限制，就思考一个问题：如果让你设计一个算法，穷举所有可能的密码组合，你怎么做？
穷举呗，再简单一点，如果你只转一下锁，有几种可能？总共有 4 个位置，每个位置可以向上转，也可以向下转，也就是有 8 种可能对吧。
比如说从 "0000" 开始，转一次，可以穷举出 "1000", "9000", "0100", "0900"... 共 8 种密码。然后，再以这 8 种密码作为基础，对每个密码再转一下，穷举出所有可能…
仔细想想，这就可以抽象成一幅图，每个节点有 8 个相邻的节点，又让你求最短距离，这不就是典型的 BFS 嘛，框架就可以派上用场了，先写出一个「简陋」的 BFS 框架
// 将 s[j] 向上拨动一次 String plusOne(String s, int j) { char[] ch = s.toCharArray(); if (ch[j] == '9') ch[j] = '0'; else ch[j] += 1; return new String(ch); } // 将 s[i] 向下拨动一次 String minusOne(String s, int j) { char[] ch = s.toCharArray(); if (ch[j] == '0') ch[j] = '9'; else ch[j] -= 1; return new String(ch); } // BFS 框架，打印出所有可能的密码 void BFS(String target) { Queue<String> q = new LinkedList<>(); q.offer("0000"); while (!q.isEmpty()) { int sz = q.size(); /* 将当前队列中的所有节点向周围扩散 */ for (int i = 0; i < sz; i++) { String cur = q.poll(); /* 判断是否到达终点 */ System.out.println(cur); /* 将一个节点的相邻节点加入队列 */ for (int j = 0; j < 4; j++) { String up = plusOne(cur, j); String down = minusOne(cur, j); q.offer(up); q.offer(down); } } /* 在这里增加步数 */ } return; }解决问题
1、会走回头路。比如说我们从 "0000" 拨到 "1000"，但是等从队列拿出 "1000" 时，还会拨出一个 "0000"，这样的话会产生死循环。2、没有终止条件，按照题目要求，我们找到 target 就应该结束并返回拨动的次数。3、没有对 deadends 的处理，按道理这些「死亡密码」是不能出现的，也就是说你遇到这些密码的时候需要跳过。 int openLock(String[] deadends, String target) { // 记录需要跳过的死亡密码 Set<String> deads = new HashSet<>(); for (String s : deadends) deads.add(s); // 记录已经穷举过的密码，防止走回头路 Set<String> visited = new HashSet<>(); Queue<String> q = new LinkedList<>(); // 从起点开始启动广度优先搜索 int step = 0; q.offer("0000"); visited.add("0000"); while (!q.isEmpty()) { int sz = q.size(); /* 将当前队列中的所有节点向周围扩散 */ for (int i = 0; i < sz; i++) { String cur = q.poll(); /* 判断是否到达终点 */ if (deads.contains(cur)) continue; if (cur.equals(target)) return step; /* 将一个节点的未遍历相邻节点加入队列 */ for (int j = 0; j < 4; j++) { String up = plusOne(cur, j); if (!visited.contains(up)) { q.offer(up); visited.add(up); } String down = minusOne(cur, j); if (!visited.contains(down)) { q.offer(down); visited.add(down); } } } /* 在这里增加步数 */ step++; } // 如果穷举完都没找到目标密码，那就是找不到了 return -1; }实现 BFS 的时候，我们把未被访问过的节点放在一个称为 open 的容器中，而把已经访问过了的节点放在 closed 容器中。
如果原图不连通，只能访问到从起点出发能够到达的点。
BFS 序列通常也不唯一。
类似的我们也可以定义 BFS 树：在 BFS 过程中，通过记录每个节点从哪个点访问而来，可以建立一个树结构，即为 BFS 树。
传统的 BFS 框架就是从起点开始向四周扩散，遇到终点时停止；而双向 BFS 则是从起点和终点同时开始扩散，当两边有交集的时候停止。
边权值为可能有，也可能没有（由于 BFS 适用于权值为 1 的图，所以一般是 0 or 1），或者能够转化为这种边权值的最短路问题。
例如在走迷宫问题中，你可以花 1 个金币走 5 步，也可以不花金币走 1 步，这就可以用 0-1 BFS 解决。
一般情况下，我们把没有权值的边扩展到的点放到队首，有权值的边扩展到的点放到队尾。这样即可保证在整个队列中，像普通 BFS 一样，越靠近队首，权值越小，且权值零一之间有分隔。
下面是伪代码：
while (队列不为空) { int u = 队首; 弹出队首; for (枚举 u 的邻居) { 更新数据 if (...) 添加到队首; else 添加到队尾; } } 将开始结点和目标结点加入队列 q 标记开始结点为 1 标记目标结点为 2 while (队列 q 不为空) { 从 q.front() 扩展出新的 s 个结点 如果 新扩展出的结点已经被其他数字标记过 那么 表示搜索的两端碰撞 那么 循环结束 如果 新的 s 个结点是从开始结点扩展来的 那么 将这个 s 个结点标记为 1 并且入队 q 如果 新的 s 个结点是从目标结点扩展来的 那么 将这个 s 个结点标记为 2 并且入队 q }不过，双向 BFS 也有局限，因为你必须知道终点在哪里。比如我们刚才讨论的二叉树最小高度的问题，你一开始根本就不知道终点在哪里，也就无法使用双向 BFS；但是第二个密码锁的问题，是可以使用双向 BFS 算法来提高效率的，代码稍加修改即可：
int openLock(String[] deadends, String target) { Set<String> deads = new HashSet<>(); for (String s : deadends) deads.add(s); // 用集合不用队列，可以快速判断元素是否存在 Set<String> q1 = new HashSet<>(); Set<String> q2 = new HashSet<>(); Set<String> visited = new HashSet<>(); int step = 0; q1.add("0000"); q2.add(target); while (!q1.isEmpty() && !q2.isEmpty()) { // 哈希集合在遍历的过程中不能修改，用 temp 存储扩散结果 Set<String> temp = new HashSet<>(); /* 将 q1 中的所有节点向周围扩散 */ for (String cur : q1) { /* 判断是否到达终点 */ if (deads.contains(cur)) continue; if (q2.contains(cur)) return step; visited.add(cur); /* 将一个节点的未遍历相邻节点加入集合 */ for (int j = 0; j < 4; j++) { String up = plusOne(cur, j); if (!visited.contains(up)) temp.add(up); String down = minusOne(cur, j); if (!visited.contains(down)) temp.add(down); } } /* 在这里增加步数 */ step++; // temp 相当于 q1 // 这里交换 q1 q2，下一轮 while 就是扩散 q2 q1 = q2; q2 = temp; } return -1; }双向 BFS 还是遵循 BFS 算法框架的，只是不再使用队列，而是使用 HashSet 方便快速判断两个集合是否有交集。
另外的一个技巧点就是 while 循环的最后交换 q1 和 q2 的内容，所以只要默认扩散 q1 就相当于轮流扩散 q1 和 q2。
其实双向 BFS 还有一个优化，就是在 while 循环开始时做一个判断：
// ... while (!q1.isEmpty() && !q2.isEmpty()) { if (q1.size() > q2.size()) { // 交换 q1 和 q2 temp = q1; q1 = q2; q2 = temp; } // ...为按照 BFS 的逻辑，队列（集合）中的元素越多，扩散之后新的队列（集合）中的元素就越多；在双向 BFS 算法中，如果我们每次都选择一个较小的集合进行扩散，那么占用的空间增长速度就会慢一些，效率就会高一些。
不过话说回来，无论传统 BFS 还是双向 BFS，无论做不做优化，从 Big O 衡量标准来看，时间复杂度都是一样的，只能说双向 BFS 是一种 trick，算法运行的速度会相对快一点，
一个n x m 的图，现在有一束激光从左上角往右边射出，每遇到 ‘#’，你可以选择光线往四个方向射出，或者什么都不做，问最少需要多少个 ‘#’ 往四个方向射出才能使光线在第 行往右边射出。
此题目正解不是 0-1 BFS 但是适用 0-1 BFS 可以不需要思考过程，赛时许多大佬都是这么做的。
做法很简单，一个方向射出不需要花费（0），而往四个方向射出需要花费（1），然后直接来就可以了。
#include <bits/stdc++.h> using namespace std; #define INF (1 << 29) int n, m; char grid[1001][1001]; int dist[1001][1001][4]; int fx[] = {1, -1, 0, 0}; int fy[] = {0, 0, 1, -1}; deque<int> q; void add_front(int x, int y, int dir, int d) { if (d < dist[x][y][dir]) { dist[x][y][dir] = d; q.push_front(dir); q.push_front(y); q.push_front(x); } } void add_back(int x, int y, int dir, int d) { if (d < dist[x][y][dir]) { dist[x][y][dir] = d; q.push_back(x); q.push_back(y); q.push_back(dir); } } int main() { cin >> n >> m; for (int i = 0; i < n; i++) cin >> grid[i]; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) for (int k = 0; k < 4; k++) dist[i][j][k] = INF; add_front(n - 1, m - 1, 3, 0); while (!q.empty()) { int x = q[0], y = q[1], dir = q[2]; q.pop_front(); q.pop_front(); q.pop_front(); int d = dist[x][y][dir]; int nx = x + fx[dir], ny = y + fy[dir]; if (nx >= 0 && nx < n && ny >= 0 && ny < m) add_front(nx, ny, dir, d); if (grid[x][y] == '#') for (int i = 0; i < 4; i++) if (i != dir) add_back(x, y, i, d + 1); } if (dist[0][0][3] == INF) cout << -1 << endl; else cout << dist[0][0][3] << endl; return 0; }优先队列，相当于一个二叉堆，STL 中提供了 std::priority_queue (java的PriorityQueue)，可以方便我们使用优先队列。
在基于优先队列的 BFS 中，我们每次从队首取出代价最小的结点进行进一步搜索。容易证明这个贪心思想是正确的，因为从这个结点开始扩展的搜索，一定不会更新原来那些代价更高的结点。换句话说，其余那些代价更高的结点，我们不回去考虑更新它。
当然，每个结点可能会被入队多次，只是每次入队的代价不同。当该结点第一次从优先队列中取出，以后便无需再在该结点进行搜索，直接忽略即可。所以，优先队列的 BFS 当中，每个结点只会被处理一次。
相对于普通队列的 BFS，时间复杂度多了一个log ，毕竟要维护这个优先队列嘛。不过普通 BFS 有可能每个结点入队、出队多次，时间复杂度会达到 n^2，不是n 。所以优先队列 BFS 通常还是快的。
