常规BFS
- 每次把周围未访问的点加进队列
- 在append时检查visit标记和设置visit标记
- 只能解决长度为1的问题
也可以在queue pop时再check 是否visit和标记visit，时间复杂度加边数。
题目：
- 求最少转弯的路径 每次转弯时加1
- 126. 单词接龙 II 输入所有bfs路径，层次遍历 + dfs回溯pre.
从外向内扩展
- 407. 接雨水 II 从外向内dijkstra。
- 417. 太平洋大西洋水流问题 从外向内bfs/dfs。
双向BFS
常规bds可能会搜索空间爆炸， 假如同时从两个方向开始搜索，一旦搜索到相同的值，意味着找到了一条联通起点和终点的最短路径。
双向 BFS」的基本实现思路如下：
- 创建「两个队列」分别用于两个方向的搜索；
- 创建「两个哈希表」用于「解决相同节点重复搜索」和「记录转换次数」；
- 为了尽可能让两个搜索方向“平均”，每次从队列中取值进行扩展时，先判断哪个队列容量较少；
- 如果在搜索过程中「搜索到对方搜索过的节点」，说明找到了最短路径。
d1、d2 为两个方向的队列
m1、m2 为两个方向的哈希表，记录每个节点距离起点的
// 只有两个队列都不空，才有必要继续往下搜索
// 如果其中一个队列空了，说明从某个方向搜到底都搜不到该方向的目标节点
while(!d1.isEmpty() && !d2.isEmpty()) {
if (d1.size() < d2.size()) {
update(d1, m1, m2);
} else {
update(d2, m2, m1);
}
}
// update 为将当前队列 d 中包含的元素取出，进行「一次完整扩展」的逻辑（按层拓展）
void update(Deque d, Map cur, Map other) {}
# 单词接龙： https://leetcode.cn/problems/word-ladder/
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
word_set = set(wordList)
word_set.add(beginWord)
import collections
graph = collections.defaultdict(list)
for w in word_set:
wl = list(w)
for i in range(len(wl)):
old = w[i]
for k in range(ord('a'), ord('z') + 1, 1):
c = chr(k)
if c == old: continue
wl[i] = c
nxt = "".join(wl)
if nxt in word_set:
graph[w].append(nxt)
wl[i] = old
# print(graph)
import collections
ans = float("inf")
ma, mb = {}, {}
ma[beginWord] = 0
mb[endWord] = 0
q1 = collections.deque()
q1.append(beginWord)
q2 = collections.deque()
q2.append(endWord)
def update(q: collections.deque, cur: map, other: map):
for _ in range(len(q)):
pop = q.popleft()
for nxt in graph[pop]:
if nxt in cur: continue
cur[nxt] = cur[pop] + 1
q.append(nxt)
if nxt in other:
nonlocal ans
ans = min(ans, cur[nxt] + other[nxt])
while q1 and q2:
if len(q1) < len(q2):
update(q1, ma, mb)
else:
update(q2, mb, ma)
return ans + 1 if ans < float('inf') else 0
题目：
优先队列BFS
题目：
0-1 广度优先搜索
为了可以处理权值为0的边，使用双端队列，当遇到是0的边，就加入到队首。
保证广度优先搜索正确性的基础在于：对于源点 ss 以及任意两个节点 uu 和 vv，如果 \textit{dist}(s, u) < \textit{dist}(s, v)dist(s,u)<dist(s,v)（其中 \textit{dist}(x, y)dist(x,y) 表示从节点 xx 到节点 yy 的最短路长度），那么节点 uu 一定会比节点 vv 先被取出队列。在常规的广度优先搜索中，我们使用队列作为维护节点的数据结构，就保证了从队列中取出的节点，它们与源点之间的距离是单调递增的。
0-1 广度优先搜索的实现其实与 Dijkstra 算法非常相似。在 Dijkstra 算法中，我们用优先队列保证了距离的单调递增性。而在 0-1 广度优先搜索中，实际上任意时刻队列中的节点与源点的距离均为 dd 或 d + 1d+1（其中 dd 为某一非负整数），并且所有与源点距离为 dd 的节点都出现在队首附近，所有与源点距离为 d + 1d+1 的节点都出现在队尾附近。因此，我们只要使用双端队列，对于边权为 00 和 11 的两种情况分别将对应节点添加至队首和队尾，就保证了距离的单调递增性。
实现：
- 为了可以处理权值为0的边，使用双端队列，当遇到是0的边，就加入到队首。
- 每次pop时检查是否visit，如果是visit就continue跳过，否则接着处理，并设置visit为true，这个和dijstra类似，和常规bfs(append时检查visit和设置visit)有区别
- 只能解决0/1的长度问题。
class Solution:
def minimumObstacles(self, grid: List[List[int]]) -> int:
'''
dijstra, pop时已经是最短成本了，以成本作为优先策略
:param grid:
:return:
'''
m, n = len(grid), len(grid[0])
if m == 1 and n == 1:
return 0
q = collections.deque()
if grid[0][0] == 1:
q.append((1, (0, 0)))
else:
q.append((0, (0, 0)))
dist = {}
while q:
cost, u = q.popleft()
if u in dist: continue
dist[u] = cost
x, y = u
if x == m - 1 and y == n - 1:
return cost
for dx, dy in Directions.dirs:
nx, ny = x + dx, y + dy
if nx < 0 or nx >= m or ny < 0 or ny >= n:
continue
v = (nx, ny)
if v in dist:
continue
if grid[nx][ny] == 1:
q.append((cost + 1, v))
else:
q.appendleft((cost, v))
return -1
题目列表：