Breadth-first Search

Method

用一个queue记录当前层的元素, 和一个visited set记录所有访问过的元素. 有时不只是简单的visited来标记访问过的, 还常用distance来记录到某点最短的路径. 不断更新到某点的最短距离, 如果到该点的距离比最短距离远, 则终止该path往下的搜索, 因为从该点往后的搜索和之前造访该点的搜索过程会一样, 却path总路径更长.

Application

1. 按层遍历图 (Minesweeper). 找从一些点S1到另一些点S2的最短距离. 有时从S2反过来搜S1效果更好. (01 Matrix)

2. 是否存在path. 起点位置不定 (避免雷区)

3. 每次能修改/删除一个, 能否到达目标string, 要求返回所有可能的结果 (remove invalid parentheses). 或者路径 (word-ladder-ii). 能和DFS配合, 用于标记可达的distance. 在DFS时遇到不满足distance的则停止该path.