数据结构：采用队列

应用场景：在图中查找最短距离

BFS算法框架

# 计算start到target的最短距离
def BFS(start,target):
    q = collections.deque() # 队列
    visited = set() # 已经走过的节点

    q.append(start)
    visited.add(start)
    step = 0

    while len(q):
        # 队列中的所有节点向四周扩散
        for i in range(len(q)): # 对当前的队列进行遍历
            cur = q.popleft() # 取出队列头
            if cur == target:
                return step
            for x in cur.adj(): # cur的相邻节点
                if x not in visited:
                    q.append(x)
                    visited.add(x)
        step+=1

双向BFS

使用双向BFS必须知道终点

传统的 BFS 框架就是从起点开始向四周扩散，遇到终点时停止；而双向 BFS 则是从起点和终点同时开始扩散，当两边有交集的时候停止。

1.不再使用队列，使用set判断集合是否有交集

2.while循环的最后交换q1和q2的内容，所以只要默认扩散 q1 就相当于轮流扩散q1和q2

3.whie循环开始的时候，交换q1与q2，使q1为其中短的（比2优化）

4.时间复杂度都一样

相关问题

111. 二叉树的最小深度

752. 打开转盘锁