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)

优先队列


请多多指教。

文章标题:Breadth First Search Summary

本文作者:顺强

发布时间:2019-09-18, 23:59:00

原始链接:http://shunqiang.ml/leetcode-bfs-summary/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏