BFS 算法解题套路框架 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：BFS 算法解题套路框架

评论礼仪 见这里，违者直接拉黑。

[tinyhare]

我觉得用先进先出的队列存储要遍历的节点，就是BFS；用先进后出的栈来存储即将遍历的节点就是DFS；

BFS可以用集合，需要在遍历当前层级的节点时，把下层节点存储到临时集合变量中，保证先处理当前层节点，队列本身就能做到，所以不用临时变量。

回溯法是DFS，是因为它用函数递归的方法，相当于是用函数栈存储的节点信息，转换成迭代法就是自己用个栈结构存储节点就行了；

双向BFS不只要知道目标在哪里，是不是还必须有逆向路径，比如用链表实现二叉树，知道目标是那个节点，想知道从根到它的路径，如果是双向链表，就可以从目标往根找，否则只能从根往目标找。

不知理解的对不对。

非常感谢作者，你把特殊的算法个例进行了一般化，变成了各种框架，和编程中把特例需求一般化，解决了一般化的问题就解决了所有的特列是一个道理。我能有兴趣研究算法真是多亏了你。

[labuladong]

@tinyhare 很高兴能帮到你，你理解的很透彻，BFS 和 DFS（回溯）本质上都是暴力穷举算法，就是实现形式上的不同导致特点不同。很多算法本质都类似，所以只要能够掌握框架，算法并没有多难的，加油~

[lidongxin112]

感谢作者大大！

[yzw-Joey]

我有一个问题，既然已经记录在visited中的字符串不会再次被记录在 q1 or q2 中，那么q1和q2怎么会有交集呢？

[IRuoGu]

你会发现visited的更新是滞后于temp的更新的。这也是为何visited的位置相较于原始BFS算法不同的原因。

[shiboys]

对的，如果 visited 数组不滞后于 s1 和 s2 的更新，那么 visited 数组会阻止 s1 和 s2 的相交，导致无法返回正确的结果

[Clarence-G]

Python版本的双向bfs，ac100%

class Solution(object):
    def openLock(self, deadends, target):
        """
        :type deadends: List[str]
        :type target: str
        :rtype: int
        """
        visited = set(deadends)
        if '0000' in visited:
            return -1
        q1 = set(['0000'])
        q2 = set([target])
        step = 0
        while q1 and q2:
            tmp = set()
            for curr in q1:
                if curr in q2:
                    return step
                if curr in visited:
                    continue
                visited.add(curr)
                for i in range(4):
                    for d in (-1, 1):
                        next = curr[:i] + str((int(curr[i]) + d) % 10) + curr[i + 1:]
                        tmp.add(next)
            step += 1
            q1 = q2
            q2 = tmp
        return -1

[LeonG7]

@yzw-Joey 代码中temp保存的是下一轮的所有节点，visited只保存了当前轮的所有节点，所以temp转为q2，q2里面的节点并没有存入visited中，判断q1和q2是否有交集是可行的。

[shiboys]

加入了，s1=s2, 遍历的 就是是 s2 集合的节点，然后在遍历过程中 visited.add(cur) 就将 s2 里面的节点加入 visited

[Goolloo]

@yzw-Joey
之前的案例是在stack.push(object) 的时候加入visited里，所以任何已经访问过和即将被访问的元素都在里面。
Double BFS的代码里是在stack.pop(object)的时候才加入visited里，只有已经访问过的元素在里面。而q1和q2里面的元素都属于即将被访问。
这两个加入visited的不同时机并不影响结果，算是博主代码风格的不统一吧。

[Feyl]

可以不需要 dead 这个哈希集合，可以直接将这些元素初始化到 visited 集合中，效果是一样的，可能更加优雅一些。

合并后的代码如下：

class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> visited = new HashSet<>();
        for(String s:deadends) visited.add(s);
        Queue<String> q = new LinkedList<>();
        int res = 0;
        q.offer("0000");

        while(!q.isEmpty()){
            int sz = q.size();

            for(int i=0; i<sz; i++){
                String cur = q.poll();
                if(visited.contains(cur)){
                     continue;
                }else{
                    visited.add(cur);
                }
                if(target.equals(cur)) return res;
                for(int j=0; j<4; j++){
                    String up = plusOne(cur,j);
                    if(!visited.contains(up)) q.offer(up);
                    String down = minusOne(cur,j);
                    if(!visited.contains(down)) q.offer(down);
                }
            }
            res++;
        }
        return -1;
    }

    private String plusOne(String s, int i){
        char[] c  = s.toCharArray();
        if(c[i]=='9') c[i] = '0';
        else c[i]++;
        return new String(c);
    }

    private String minusOne(String s, int i){
        char[] c  = s.toCharArray();
        if(c[i]=='0') c[i] = '9';
        else c[i]--;
        return new String(c);
    }
}

[gaosh96]

初始化可以直接这么写

Set<String> visited = new HashSet<>(Arrays.asList(deadends));

[YANLING-H]

请问对于从queue里移除元素的q.poll(), q.remove()和在queue里加元素的q.offer(), q.add()的选择对于BFS来说有什么讲究吗。我看模版里用的是q.poll()和q.offer(),是另一个组用法有什么地方不好吗，还是两种用法在BFS的题里没有区别。谢谢了 :D

[labuladong]

@YANLING-H 没啥区别，Java 的队列 API 罢了，你查下语言相关的知识就知道了。

[Goolloo]

@YANLING-H 对于面试没区别，工业上会有应用。.add()来自Collection<E>，而offer来自Queue<E>。

.add()

Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.

.offer()

Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions. When using a capacity-restricted queue, this method is generally preferable to add(E), which can fail to insert an element only by throwing an exception.

[jswxwxf]

js 版二叉树最小高度

function minDepth(root) {
  if (root == null) return 0;
  const q = [];
  q.push(root);
  // root 本身就是一层，depth 初始化为 1
  let depth = 1;

  while (q.length) {
    const len = q.length;
    /* 将当前队列中的所有节点向四周扩散 */
    for (let i = 0; i < len; i++) {
      const cur = q.shift();
      /* 判断是否到达终点 */
      if (cur.left == null && cur.right == null) return depth;
      /* 将 cur 的相邻节点加入队列 */
      if (cur.left !== null) q.push(cur.left);
      if (cur.right !== null) q.push(cur.right);
    }
    /* 这里增加步数 */
    depth++;
  }
  return depth;
}

[jswxwxf]

js 版开锁次数

var openLock = function(deadends, target) {
  // 将 s[j] 向上拨动一次
  function plusOne(s, j) {
    let replacement = s[j] === "9" ? 0 : parseInt(s[j]) + 1;
    return s.substr(0, j) + replacement + s.substr(j + 1);
  }
  // 将 s[j] 向下拨动一次
  function minusOne(s, j) {
    let replacement = s[j] === "0" ? 9 : parseInt(s[j]) - 1;
    return s.substr(0, j) + replacement + s.substr(j + 1);
  }

  // BFS 框架，打印出所有可能的密码
  function BFS() {
    // 记录已经穷举过的密码，防止走回头路
    const visited = {
      "0000": true,
    };

    // 从起点开始启动广度优先搜索
    const q = ["0000"];
    let step = 0;

    while (q.length) {
      const len = q.length;
      /* 将当前队列中的所有节点向周围扩散 */
      for (i = 0; i < len; i++) {
        const cur = q.shift();

        /* 判断死亡数字 */
        if (deadends.includes(cur)) continue;

        /* 判断是否到达终点 */
        if (cur === target) return step;

        /* 将一个节点的相邻节点加入队列 */
        for (j = 0; j < 4; j++) {
          up = plusOne(cur, j);
          if (visited[up] === undefined) {
            q.push(up);
            visited[up] = true;
          }
          down = minusOne(cur, j);
          if (visited[down] === undefined) {
            q.push(down);
            visited[down] = true;
          }
        }
      }
      /* 在这里增加步数 */
      step++;
    }
    return -1;
  }

  return BFS();
};

[quanzhidou]

使用PHP解题时遇到的坑：判断当前节点是否存在于visited和deadends时一开始使用的是in_array函数，这样会拖慢速度，后来看到大佬的题解，将visited和deadends存成map，然后判断当前节点作为map的键是否存在相应的值

[skywalkerlw]

东哥，开锁的那个case请教一个问题： BFS只能获取到要走多少步步，有没有办法获取到具体是走了哪几步到目的地的？ 多谢

[labuladong]

可以的，新建一个包装类 Record，Record 不仅记录当前走到的密码 String，还记录走到当前密码的过程。队列改为维护 Queue<Record> 就可以了。

[masterX89]

js 版本的开锁次数

var openLock = function (deadends, target) {
  const visited = new Set(deadends) // 合并 deadends 至 visited
  let step = 0
  const q = []

  const changePwd = (pwd, pos, offset) => {
    const arr = pwd.split('').map((val) => parseInt(val))
    arr[pos] = (arr[pos] + offset + 10) % 10 // +1 和 -1 的拨动方向
    return arr.join('')
  }
  const pushQueue = (pwd) => {
    if (!visited.has(pwd)) {
      q.push(pwd)
      visited.add(pwd)
    }
  }

  pushQueue('0000')
  while (q.length !== 0) {
    const len = q.length
    for (let i = 0; i < len; i++) {
      const pwd = q.shift()
      if (pwd === target) return step
      for (let j = 0; j < 4; j++) {
        for (let offset of [-1, 1]) {
          const newPwd = changePwd(pwd, j, offset)
          pushQueue(newPwd)
        }
      }
    }
    step++
  }
  return -1
}

[exoreray]

我的理解dfs和bfs还有个很大的区别就是dfs有能力从下层往上层带回来信息，而bfs就不可能。所以遇到需要叶节点信息的遍历的题就不能用bfs，只能用dfs。

[labuladong]

你的这个理解是对的，可以看看 二叉树纲领篇 中的总结。

[yangzerenmiku]

2022.10.29 打卡

[LittleWhite-Carry]

第一个二叉树的最小深度，可以使用前面讲二叉树章节的技巧，在root前面加一个节点，以省去边界条件的判断

[Edwin-Xu]

#2022-11-13 done

[yywill]

minDepth 这道题错了，还要return 还要再+1

return level+1;

[Guwei1013]

第二例题解开密码锁的最少次数，作者最后一段结论有问题，或者说这段结论容易让人产生误解。

有一个比较小的优化：可以不需要 deads 这个哈希集合，可以直接将这些元素初始化到 visited 集合中，效果是一样的，可能更加优雅一些。
你可以把 dead 中的元素放入 visited 集合，但并不意味你不需要 dead 这个集合。为什么呢?
如果按照上述不需要 dead 这个集合，那么原文的这行代码是不是应该做如下修改

- if (deads.has(cur))   continue;
+ if (visited.has(cur))   continue;

这样做会导致程序 bug 的产生，为什么？
当你执行完上下波动，添加上新元素组合进入 visited，下一轮执行碰到上面修改那一行的逻辑，就会 continue 掉。导致程序出现 bug。因此正确的说法是： deads 中的元素可以放入 visited 集合进行代码优化，但仍然需要 deads 集合，保证if (deads.has(cur)) continue 代码逻辑的正确性。
如果直接去掉这行代码则会产生另一个 bug，就是当 deads 中存在 '0000' 元素的时候。因此要么在最上面加一个特别的判断这种情况，里面的 if (deads.has(cur)) continue 就可以去掉。要么就保留着这行代码不变。

[labuladong]

这个 diff 的显示不错👍🏼

[zhuifeng-Q]

回头路没理解，为啥会回去啊，先进先出，不是一层一层的嘛

[labuladong]

二叉树不会回头，但图，或者二维数组，你上下左右遍历，这个格子的右边，是不是就是右边那个格子的左边，这就要不免回头。

[forexgg]

Leetcode 111 二叉树最小深度 最后一句 return depth 应该可以省略了

    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        
        queue = deque([root])
        depth = 1

        while queue:
            # for loop to pop all nodes at the same level
            for i in range(len(queue)):
                node = queue.popleft()
                if node.left is None and node.right is None:
                    return depth
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            depth += 1

[forexgg]

752 题 密码锁
0,9 上下拨的时候，如果不用分支判断0或者9，也可以用 循环取模 来实现

    char_plus_one = str((int(password) + 1) % 10)
    char_minus_one = str((int(password) - 1) % 10)

[Valor-H]

C++代码

int openLock(vector<string>& deads, string target) {
	return BFS(deads, target);
}

int BFS(vector<string>& deads, string target) { 
	unordered_set<string> visited(deads.begin(), deads.end());
	if (visited.count("0000")) return -1;
	queue<string> que;
	que.push("0000");
	visited.insert("0000");
	int step = 0;
	while (!que.empty()) {
		int size = que.size();
		for (int i = 0; i < size; ++i) {
			string cur = que.front(); que.pop();
			if (cur == target) return step;
			for (int j = 0; j < 4; ++j) {
				string up = upOne(cur, j);
				if (!visited.count(up)) {
					que.push(up);
					visited.insert(up);
				}
				string down = downOne(cur, j);
				if (!visited.count(down)) {
					que.push(down);
					visited.insert(down);
				}
			}
		}
		++step;
	}
	return -1;
}

string upOne(string s, int n) {
	s[n] == '9' ? s[n] = '0' : ++s[n];
	return s;
}

string downOne(string s, int n) {
	s[n] == '0' ? s[n] = '9' : --s[n];
	return s;
}

[codepileman]

猜密码那题用JavaScript写，如果visited和dead不用set，只用array，会超时。不知道为什么，理论上set和array查找都是logn

[lemonzeng]

这一篇文章也写得特别好，逻辑清晰，读完之后，醍醐灌顶

[CZT0]

752. 打开转盘锁 的golang解法，去掉了deads数组，另外无需检查是否访问过，因为这在加入队列时已经做了

// openLock 尝试解开一个由四个滚动数字组成的锁。deadends 是无法访问的密码组合，target 是目标密码。
// 函数返回到达目标密码所需的最少步数，如果无法到达，则返回 -1。
func openLock(deadends []string, target string) int {
    // visit 存储已访问过的密码以及死亡密码
    visit := make(map[string]bool)

    // 初始化 deadends 到 visit 集合中
    for _, str := range deadends {
        visit[str] = true
    }

    // 如果起始密码 "0000" 已在 deadends 中，无法开始，直接返回 -1
    if visit["0000"] {
        return -1
    }

    // 初始化队列，并将起始密码 "0000" 加入队列和 visit 集合
    queue := []string{"0000"}
    visit["0000"] = true
    count := 0

    // 使用广度优先搜索解锁过程
    for len(queue) != 0 {
        length := len(queue)

        // 遍历当前队列中的所有密码
        for i := 0; i < length; i++ {
            cur := queue[0]
            queue = queue[1:]

            // 检查当前密码是否为目标密码
            if cur == target {
                return count
            }

            // 尝试每个轮盘的每个方向
            for j := 0; j < 4; j++ {
                up := plusOne(cur, j)
                // 如果新密码未被访问过，则加入队列
                if _, ok := visit[up]; !ok {
                    queue = append(queue, up)
                    visit[up] = true
                }

                down := minusOne(cur, j)
                // 同样检查下拨情况
                if _, ok := visit[down]; !ok {
                    queue = append(queue, down)
                    visit[down] = true
                }
            }
        }
        // 每完成一层，步数增加
        count++
    }
    // 如果无法到达目标，返回 -1
    return -1
}

// plusOne 模拟在指定位置将数字加一，如果是9则回到0
func plusOne(str string, i int) string {
    arr := []byte(str)
    if arr[i] == '9' {
        arr[i] = '0'
    } else {
        arr[i]++
    }
    return string(arr)
}

// minusOne 模拟在指定位置将数字减一，如果是0则跳到9
func minusOne(str string, i int) string {
    arr := []byte(str)
    if arr[i] == '0' {
        arr[i] = '9'
    } else {
        arr[i]--
    }
    return string(arr)
}