Breadth First Search Summary

树的 BFS 是层序遍历
二叉树上的 BFS in Binary Tree
图上的 BFS in Gragh

• 拓扑排序 Topological Sorting
• 选取任意结点为根节点即起点
  棋盘上的 BFS

什么时候应该使用 BFS？
图的遍历 Travelsal in Gragh

• 层级遍历 Level Order Traversal
• 由点及面 Connected Component （连通）
• 拓扑排序 Topological Sorting
  最短路径 Shortest Path in Simple Graph
• 仅限简单图求最短路径
• 即，图中每条边长度都是 1，且没有方向

如果是最短路径，还可以用动态规划 DP 解题

队列的先进先出：

• 初始化队列 Q
• 起点标记已访问
• while (Q 非空){

  取 Q 队首元素 u,    u 出队；
  if (u == 目标状态){...};
  所有与 u 相邻且未被访问的点进入队列；
  标记 u 为已访问；
  

  }

dict 表示邻接矩阵 (没有顺序)
list 表示队列

def BFS(gragh,  s):
    queue = []
    queue.append(s)
    seen = set()
    seen.add(s)
    while (len(queue) > 0):
        vertex = queue.pop(0)
        nodes = graph[vertex]
        for w in nodes:
            if w is not in seen:
              queue.append(w)
              seen.add(w)
        print(vertex)

parent 点

def BFS2(gragh,  s):
    queue = []
    queue.append(s)
    seen = set()
    seen.add(s)
    parent = {s:None}
    while (len(queue) > 0):
        vertex = queue.pop(0)
        nodes = graph[vertex]
        for w in nodes:
            if w is not in seen:
              queue.append(w)
              seen.add(w)
        print(vertex)

优先队列