算法及数据结构系列 - BFS算法

框架思路

BFS 的核心思想应该不难理解的，就是把一些问题抽象成图，从一个点开始，向四周开始扩散。一般来说，我们写 BFS 算法都是用队列 这种数据结构，每次将一个节点周围的所有节点加入队列。 BFS 相对 DFS 的最主要的区别是：BFS 找到的路径一定是最短的，但代价就是空间复杂度比 DFS 大很多，至于为什么，我们后面介绍了框架就很容易看出来了。 问题的本质就是让你在一幅「图」中找到从起点 start 到终点 target 的最近距离。 // 计算从起点 start 到终点 target 的最近距离 int BFS(Node start, Node target) { Queue q; // 核心数据结构 Set 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++; } }

经典题型

111 二叉树的最小深度

给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 class Solution { public int minDepth(TreeNode root) { if(root == null){ return 0; } Queue q = new LinkedList(); q.offer(root); int height = 1; while(!q.isEmpty()){ int size = q.size(); for(int i = 0; i< size; i++){ TreeNode node = q.poll(); if(node.left == null && node.right == null){ return height; } if(node.left != null){ q.offer(node.left); } if(node.right != null){ q.offer(node.right); } } height++; } return height; } } 常见问题：

1. 为什么 BFS 可以找到最短距离，DFS 不行吗？ 首先，你看 BFS 的逻辑，depth 每增加一次，队列中的所有节点都向前迈一步，这保证了第一次到达终点的时候，走的步数是最少的。 DFS 不能找最短路径吗？其实也是可以的，但是时间复杂度相对高很多。你想啊，DFS 实际上是靠递归的堆栈记录走过的路径，你要找到最短路径，肯定得把二叉树中所有树杈都探索完才能对比出最短的路径有多长对不对？而 BFS 借助队列做到一次一步「齐头并进」，是可以在不遍历完整棵树的条件下找到最短距离的。 形象点说，DFS 是线，BFS 是面；DFS 是单打独斗，BFS 是集体行动。这个应该比较容易理解吧。
2. 既然 BFS 那么好，为啥 DFS 还要存在？ BFS 可以找到最短距离，但是空间复杂度高，而 DFS 的空间复杂度较低。 还是拿刚才我们处理二叉树问题的例子，假设给你的这个二叉树是满二叉树，节点数为 N，对于 DFS 算法来说，空间复杂度无非就是递归堆栈，最坏情况下顶多就是树的高度，也就是 O(logN)。 但是你想想 BFS 算法，队列中每次都会储存着二叉树一层的节点，这样的话最坏情况下空间复杂度应该是树的最底层节点的数量，也就是 N/2，用 Big O 表示的话也就是 O(N)。 由此观之，BFS 还是有代价的，一般来说在找最短路径的时候使用 BFS，其他时候还是 DFS 使用得多一些（主要是递归代码好写）。

752 打开转盘锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，‘0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。 锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。 列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。 字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。 class Solution { public int openLock(String[] deadends, String target) { Set visited = new HashSet(); Set deadendSet = new HashSet(); for(String dead: deadends){ deadendSet.add(dead); } Queue q = new LinkedList(); q.offer(“0000”); visited.add(“0000”); int height = 0; while(!q.isEmpty()){ int size = q.size(); for(int i = 0; i < size; i++){ String tmp = q.poll(); if(deadendSet.contains(tmp)){ continue; } if(tmp.equals(target)){ return height; } List childs = getNextStates(tmp); for(String child: childs){ if(!visited.contains(child)){ q.offer(child); visited.add(child); } } } height++; } return -1; } public List getNextStates(String s){ List res = new ArrayList(8); for(int i = 0; i < 4; i++){ StringBuilder tmp = new StringBuilder(s); char c = s.charAt(i); char r; if (c == ‘0’){ r = ‘9’; }else{ r = (char)(c - 1); } tmp.replace(i, i + 1, r + “”); res.add(tmp.toString()); } for(int i = 0; i < 4; i++){ StringBuilder tmp = new StringBuilder(s); char c = s.charAt(i); char r; if (c == ‘9’){ r = ‘0’; }else{ r = (char)(c + 1); } tmp.replace(i, i + 1, r + “”); res.add(tmp.toString()); } return res; } }