BFS 与 DFS 图形空间复杂性

Question

当宽度第一次搜索包含队列时，深度优先搜索和广度优先搜索在具有边和顶点的图形中需要多少内存？

Answer 1

递归 DFS 占用内存最多，因为它需要当前处理的每个节点的函数调用和堆栈帧。使用显式堆栈和队列数据结构，消耗的内存没有太大差异。通常，这取决于图形的形状以及当前堆栈或队列中的节点数。先前处理或尚未访问的节点不会影响算法消耗的内存。然而，在某些极端情况下（如星形图），您可能会在整个图表中阅读。但这再次取决于图形的结构。