例如：如果我有一个有 30 个子节点的根，每个子节点有 35 个子节点，如果我执行深度优先搜索，我总共会访问每个节点多少次（包括重复）？
我想确定每条可能的路径，并且根据我的问题陈述，我知道从根到叶总共有 30 * 35 条路径。但是，我想知道计算成本是多少。那么，给定深度优先搜索算法，您将访问一个节点多少次来计算路径总数？
即。想象一下
root -> b -> c 总共 1 条路径。访问了 3 个节点
root -> b -> d 总共有 2 条路径，访问了 5 个节点（因为它回溯到节点 b 并访问了 d）
如果将回溯到一个节点也算作一次访问，那么您只会访问叶子一次，但内部节点会被第一次访问，然后按照它们有子节点的次数进行访问。
由于根节点有 30 个子节点，因此将被访问 31 次。
由于根的 30 个子节点每个都有 35 个子节点，因此每个子节点都会被访问 36 次
添加对每个叶子的单次访问，即 30 * 35
总共给出：
31 + 30 * 36 + 30 * 35 = 2161 次访问
获得此数字的另一种方法是认识到每条边代表两次节点访问：连接的子节点的访问和连接的父节点的（重新）访问。根的初始访问必须添加到此。那么你只需计算边的数量，乘以 2 再加上 1：
1 + (30 + 30 * 35) * 2 = 2161
如果我们概括，根有 𝑛 子节点，每个子节点有 𝑚 子节点——它们是叶子，那么我们得到：
1 + 2(𝑛 + 𝑛𝑚) = 1 + 2𝑛(1+𝑚)