BFS 进阶 - 变形

David_Mercury · 2023-07-18 22:00:43 · 个人记录

基础知识见：BFS 总结

这里介绍了 BFS 的若干种变形。虽然它们基于的队列种类不同，本质上，它们都是在努力维护 队列中的 单调性 以达到对 最短路 的求解。

一、普通 BFS

一般广搜队列中的节点满足以下两个特点：

1. 两段性：在队列中仅有阶段 i 与阶段 i+1 的节点。

2. 单调性：队列中，阶段 i 永远在阶段 i+1 之前。

BFS 大多被用来解决 走地图最短步数 问题。这种问题实际上可看作 “在边权为 1 的图上求最短路”，时间复杂度为 O(n)。以下是几道例题。

• P3869 [TJOI2009] 宝藏

• T132499 0x25-广度优先搜索-Bloxorz

典型的走地图问题。

这些题思维上都不怎么难，但是对码力要求还是有的。

• P1332 血色先锋队

  “给定一个 \texttt{01} 矩阵和一个起点，每步可以向上下左右四个方向之一的 \texttt{0} 移动 1 单位距离，求能到达哪些位置，以及到达此处的最少步数。”这种问题被称为 \texttt{flood-fill} 问题，一般使用 BFS 来解决。

  本题就是有多个起点的 \texttt{flood-fill} 问题，插入多个起点即可。

• T132509 0x26-广度变形-Nightmare

  本题是 双向 BFS。与双向 DFS 十分相似。两边轮流进行，每次扩展一层即可。

• T307162 0x27-IDA*-Booksort

  本题不是走地图，但是也是典型的双向 BFS 应用。

二、双端队列 BFS

双端队列 BFS 可以被用来求解 “在边权为 \texttt{0, 1} 的图上求最短路” 问题。

具体做法，就是每次取队首的节点；在拓展时，若遇到边权 \texttt{0}，插入队首；若遇到边权 \texttt{1}，插入队尾。时间复杂度也可以达到 O(n)。

双端队列的效率之所以这么高，是因为它也具备方才所提到的 “两段性”。因为只有边权 \texttt{0, 1}，刚才的做法让它内部也只有两段。

• T132507 0x26-广度变形-电路维修

• P1948 [USACO08JAN] Telephone Lines S

三、优先队列 BFS

如果边权任意，那么显然就无法满足刚才所提的“两段性”了。那么解决方案是什么呢？

这个问题实际上等价于 一般的最短路问题。

如果将 “每个节点只能出队一次” 的限制去掉，让它不断迭代直到队列为空，这就是 \text{SPFA} 算法，时间复杂度最差 O(n^2)；

如果将队列改为 优先队列，这就是 \text{dijkstra} 算法，时间复杂度为 O(n \log n)。

详情请见上方最短路问题的链接。