图中DFS与BFS的空间复杂度疑问及严谨边界咨询

嘿，我来帮你把BFS和DFS的空间复杂度理得明明白白，先从你已经了解的BFS开始确认，再重点拆解DFS的情况：

你的判断基本是对的，我再补充细节让它更严谨：

• 邻接矩阵实现：邻接矩阵本身的空间就是O(v²)，而BFS的队列最多会存储O(v)个节点（比如完全二叉树的最后一层节点数），这部分是低阶项，所以整体空间复杂度主导项是O(v²)，忽略低阶后确实是这个结果。
• 邻接表实现：平均情况空间是O(v+e)（e为边数），稀疏图里e远小于v²，所以平均空间远低于O(v²)；但最坏情况是完全图，此时e≈v²，邻接表的空间趋近于O(v²)，加上队列的O(v)开销，整体还是O(v²)——这部分你的理解完全正确。

你提到的栈帧（递归栈或者手动实现的栈）是必须计入空间复杂度的，因为这是DFS运行时的核心开销之一。下面分存储结构拆解：

1. 邻接矩阵实现的DFS #

• 邻接矩阵本身的固定存储开销是O(v²)，这是无法避免的。
• 运行时栈的开销：最坏情况是链式图（比如每个节点只连接下一个节点，像链表），此时递归深度会达到v，栈帧数量是O(v)；哪怕是完全图，递归深度最多也只会是v（从一个节点遍历所有未访问节点，每次递归深入一个新节点）。这部分O(v)的栈开销和O(v²)的邻接矩阵比是低阶项，所以整体空间复杂度是O(v²)。

2. 邻接表实现的DFS #

• 邻接表本身的空间是O(v+e)：稀疏图中e≈v，所以邻接表空间是O(v)；稠密图（比如完全图）中e≈v²，邻接表空间就是O(v²)。
• 运行时栈的开销：最坏情况还是链式图，递归深度O(v)，栈开销O(v)。所以整体空间复杂度：
  • 稀疏图：O(v+e) + O(v) = O(v)（因为e≈v，低阶项忽略）
  • 稠密图：O(v²) + O(v) = O(v²)
• 这里要注意：如果是用迭代方式实现DFS（手动维护栈代替递归），栈的空间开销和递归栈完全一致，所以复杂度结果也相同。

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