洪水填充（Floodfill）：栈（Stack）与队列（Queue）的性能对比分析

嘿，这个问题问到点子上了——用栈实现的深度优先搜索（DFS）和队列实现的广度优先搜索（BFS），在洪水填充里各有适配的场景，性能优劣完全取决于你要解决的具体问题：

栈（DFS）更优的场景 #

• 内存受限的环境：当连通区域是狭长型（比如像一条蜿蜒的管道、迷宫里的长通道），DFS的栈只会存储当前路径上的节点，内存占用远低于BFS的队列（BFS需要存储整层的节点）。这种情况下，栈能更高效地利用有限的内存资源。
• 需要快速定位深层目标：如果你的填充任务是找到某个深层的特定节点（比如填充到某个边界就停止），DFS会沿着一条路径直接钻到底，可能在遍历更少节点的情况下就命中目标，比BFS逐层铺开的方式更快。
• 递归实现更直观的场景：虽然递归版DFS本质也是用系统栈，但对于一些简单的填充需求，递归写法更简洁易读（当然要注意递归深度过大导致栈溢出的问题，迭代版栈就没这个顾虑）。

队列（BFS）更优的场景 #

• 需要均匀扩散/平滑填充：在图像处理这类场景中，BFS从起点向外逐层扩散，填充出来的区域边缘更平滑均匀，不会像DFS那样先“钻”到某个角落再回头处理其他区域，视觉效果和填充逻辑更符合“洪水漫延”的直觉。
• 最短路径/最近邻需求：如果洪水填充同时需要找到从起点到某节点的最短路径（无权重场景），BFS第一次访问到目标节点时，就是最短路径，这时候不需要像DFS那样可能走很多弯路再回溯，效率更高。
• 超大/极深连通区域：当连通区域特别大、深度极深时，DFS的栈会累积大量节点，甚至触发栈溢出（尤其是递归实现）；而BFS的队列按层存储，内存峰值更可控，不会出现极端内存占用的情况。

补充：时间复杂度的共性 #

不管用栈还是队列，洪水填充的时间复杂度都是O(n)（n为连通区域的节点总数），因为每个节点只会被访问一次。两者的性能差异主要体现在内存占用和访问顺序适配的业务需求上，而非核心遍历效率。

内容的提问来源于stack exchange，提问作者Slanted Salamander