深度优先搜索的空间复杂性

Question

也许这个问题之前就有人问过，但是，我不知道如何计算DFS的空间复杂性。例如，在这种情况下，分支因子(B)为3，深度(D)为5，每个节点需要10字节的内存来表示。如何计算空间复杂度？

Answer 1

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

• 在树上:您不需要检查以前是否访问过状态，并且必须只存储当前跟踪(在堆栈中)，这将成为最大深度的$d$。对于跟踪上的每个状态，您需要存储已经遍历的传出转换，这将成为每个状态的最大分支因子$b$。因此，您需要$O(d * b)$ space。
• 在图上:您需要通过存储已经访问过的所有状态(例如，在哈希表中)来另外检查是否在访问之前访问了状态。因此，您需要$O(d *b+ set )$ space，而V是顶点的集合。在网际网路上，你通常会看到空间复杂度是$O( not )$；通常状态数是主要因素，但是如果你的状态空间有一个很大的$b$，不要忽略空间需求的这一部分！