Skip to main content

BFS

David LiuLess than 1 minute

BFS

BFS基础

队列搜索

等待队列:队列里面的是已经结束,等待扩展的

入队:节点进入等待

出队:节点开始运行

BFS步骤

  1. 出队

  2. 捕捉:全局变量捕捉target值

    出队的时候进行目标点的捕捉,如果是目标点就返回,不再继续扩展

  3. 扩展

  4. 入队

BFS拓展

  • 递推公式:即这个边的语义,只需要改变递推公式就可以改变边的语义

    如求和、求Max、求Min等

  • 判断环路:拓扑排序

  • 队列类型

    • 普通队列:先进先出
    • 优先队列:可以根据优先级插队
    • 双端队列