Breadth First Search

应用

如果是Binary Tree或者无向图的BFS应用，题目会非常直接。但是有些题目本质上并不是Tree or Graph，而是需要你自己去联想到并构造出来，核心就是抓住BFS最明显的应用：求最短路径。比如说你要去从一个单词通过改变字符变成另一个单词，求最短变化路径。或者说从一个invalid parentheses通过remove变化到一个valid parentheses，求最少removal。

BFS另一大应用就是求connected componets，和DFS作用差不多，但是注意BFS和DFS只能求无向图的connected components，并且无向图最好还是static的。如果无向图是一直变化（merge）的，那么我们要使用Union-Find。还有如果是有向图求弱联通量，我们也需要使用Union-Find。

题目

• Leetcode 361. Bomb Enemy (用到了BFS的思想，但是two-pass的实现）

找最短路径

• Leetcode 301. Remove Invalid Parentheses

Surrounded Regions类型搜索问题（这种类型的问题需要换个思路思考搜索的起点，通常可以降低时间复杂度）

• Leetcode 417. Pacific Atlantic Water Flow (比如这道题，我们搜索的起点可以是每座山，也可以是每片海，而妙就妙在，如果以每座山作为起点，那么我们需要搜索O(mn)次，而以每片海作为搜索起点，那么我们只需要搜索O(m + n)次)
• Leetcode 130. Surrounded Regions (比如这道题，我们搜索的起点可以是中间的O，也可以是四边的O，如果以中间的O作为搜索的起点，那么需要搜索O(mn)次，如果以边上的O作为起点，那么只需要搜索O(m + n)次）
• Leetcode 286. Walls and Gates
• Leetcode 317. Shortest Distance from All Buildings