algorithm - 深度优先搜索的空间复杂度

Question

可能之前有人问过这个问题，但是我不确定如何计算 DFS 的空间复杂度。例如在这种情况下，分支因子 (b) 为 3，深度 (d) 为 5，每个节点需要 10 个字节的内存来表示。如何计算空间复杂度？

Answer 1

这取决于您执行深度优先搜索 (DFS) 的结构类型:

• over a tree:你不需要检查你之前是否访问过一个状态并且必须只存储当前轨迹(在堆栈中)，它变成最大深度 $d$。对于轨迹上的每个状态，您需要存储您已经遍历的传出转换，它最大程度地成为每个状态的最大分支因子 $b$。因此你需要 $O(d * b)$ 空间。
• 通过图:您需要通过存储所有已访问过的状态来额外检查您之前是否访问过某个状态，例如在哈希表中。因此，您需要 $O(d * b + |V|)$ 空间，其中 V 是顶点集。在互联网上，您通常会读到空间复杂度为 $O(|V|)$；通常状态的数量是主要因素，但是如果你的状态空间有很大的$b$，不要忽略这部分空间需求!