递归实现的图遍历是否为有效BFS？为何BFS多用队列？

1. 这段代码是否是正确的BFS实现？ #

是的，这段代码本质上是正确的BFS实现，因为它严格遵循了BFS的核心逻辑：按层遍历图的节点。

具体来看：

• 初始调用传入的[start_node]是第一层节点，{start_node}是已访问集合。
• 每次递归处理当前batch中的所有节点（同一层的全部节点），逐个输出。
• 收集当前层所有节点的未访问邻居，组成new_batch作为下一层节点。
• 递归调用时传递新的已访问集合（seen.union(new_batch)），确保不会重复访问节点。

唯一需要注意的前提是：neighbours(node)函数能正确返回节点的所有邻居，且start_node是合法的图节点。

2. 为何多数BFS算法采用队列而非递归方式？ #

虽然你的递归实现是正确的，但工业界和教材中更常用队列的迭代实现，主要有以下几个原因：

- 递归深度限制问题 #

递归调用依赖编程语言的系统调用栈，而大多数语言（包括Python）对栈的深度有默认限制（Python默认递归深度约为1000）。如果图的层数极深（比如一个链式结构有10000个节点），递归版本会直接触发RecursionError，而队列的迭代实现完全不受此限制——它用自己管理的队列存储节点，不占用系统栈。

- 空间效率更高 #

你的递归实现中，每次调用都会生成一个新的seen集合（seen.union(new_batch)），这会产生额外的内存开销。而队列的迭代实现可以复用同一个seen集合，直接在原集合中添加节点，节省内存。此外，递归调用本身的栈帧也会占用额外空间，层数越多开销越大。

- 可读性与通用性 #

队列是BFS的标准实现方式，几乎所有算法教材和技术文档都采用这种写法，开发者更容易理解和维护。递归的BFS写法非常少见，容易被误判为DFS（因为DFS通常用递归实现），增加了代码的理解成本。

- 灵活性更强 #

迭代式的队列实现更容易扩展额外逻辑：比如记录每个节点的遍历深度、中途提前终止遍历、处理带权重的图等。而递归版本需要传递更多参数或修改递归逻辑，实现起来更繁琐。

举个标准的队列式BFS实现对比：

from collections import deque

def bfs(start_node):
    seen = {start_node}
    queue = deque([start_node])
    while queue:
        node = queue.popleft()
        print(node)
        for n in neighbours(node):
            if n not in seen:
                seen.add(n)
                queue.append(n)

bfs(start_node)

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