BFS 核心思想不难理解，就是把一些问题抽象成图，从一个点开始，向四周开始扩散。一般来说，我们写 BFS 算法都是用队列这种数据结构，每次将一个节点周围的所有节点加入队列。
BFS 相对 DFS 的最主要区别是：

  • BFS 找到的路径一定是最短的，但代价就是空间复杂度比 DFS 大很多。

BFS 两道经典的题目：

  1. 二叉树的最小高度
  2. 打开密码锁的最小步数

框架：

  1. // 计算从起点 start 到终点 target 的最近距离
  2. int BFS(Node start, Node target) {
  3.     Queue<Node> q; // 核心数据结构
  4.     Set<Node> visited; // 避免走回头路
  6.     q.offer(start); // 将起点加入队列
  7.     visited.add(start);
  8.     int step = 0; // 记录扩散的步数
  10.     while (q not empty) {
  11.         int sz = q.size();
  12.         /* 将当前队列中的所有节点向四周扩散 */
  13.         for (int i = 0; i < sz; i++) {
  14.             Node cur = q.poll();
  16.             /* 划重点：这里判断是否到达终点 */
  17.             if (cur is target)
  18.                 return step;
  20.             /* 将 cur 的相邻节点加入队列 */
  21.             for (Node x : cur.adj())
  22.                 if (x not in visited) {
  23.                     q.offer(x);
  24.                     visited.add(x);
  25.                 }
  26.         }
  27.         /* 划重点：更新步数在这里 */
  28.         step++;
  29.     }
  30. }

cur.adj() 泛指 cur 相邻的节点，比如说二维数组中，cur 上下左右四面的位置就是相邻节点。
visited 的主要作用是防止走回头路。
既然 BFS 那么好，为啥 DFS 还存在呢?

  1. 找最短距离，使用 DFS 空间复杂度相对 BFS 较高。但对 DFS 算法来说，空间复杂度无非就是递归堆栈，最坏情况就是树的高度，也就是 BFS 算法框架套路详解 - 图1。
  2. BFS 则不一样，第次都会存储二叉树一层的节点，这样最坏的情况下空间复杂度是树的最底层节点数量，即 BFS 算法框架套路详解 - 图2，即 BFS 算法框架套路详解 - 图3。

双向 BFS 优化

传统的 BFS 框架就是从起点开始向扩散，遇到终点时停止。
双向 BFS 则是从起点和终点同时开始扩散，当两边交集时停止。不过，双向 BFS 也有局限，因为你必须知道终点在哪里。