Depth-limited DFS general/non-binary 树搜索？

Question

假设您要搜索一个无限大的 general/non-binary。因为树是无限大的，穷举 DFS 或 BFS 策略是不可行的。但是，非常需要使用参数 depth=n 的 DFS 搜索。

以此Q/A为灵感，可以执行DFS

list nodes_to_visit = {root};
while( nodes_to_visit isn't empty ) {
  currentnode = nodes_to_visit.take_first();
  nodes_to_visit.prepend( currentnode.children );
  //do something
}

关键的见解是使用堆栈，以便将需要访问的节点插入到列表的开头，并且重复此过程，直到没有更多 children 可以添加到堆栈。

考虑深度时的主要问题。我们可能会引入一个变量 d，它初始化为 0，并在每次 children 被添加到堆栈时递增它。然而，由于 children 的数量可变，堆栈没有机制知道何时应该减少 d（当访问了某个深度的所有 children 时。）

深度受限的DFS应该如何实现？（伪代码或 python 首选。）

Answer 1

您可以通过将节点 堆叠在一起 及其深度来处理最大深度。

不是你的问题，但在大多数语言中，在最后而不是开始时增加堆栈更自然（也更有效）。

这里有一些 Python 代码可以完成这项工作：

def dfs(node, maxdepth):
    stack = [(node, 0)]
    visited = set()
    while stack:
        node, nodedepth = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        # Any other processing for this node comes here
        # ...
        if nodedepth < maxdepth:
            for child in reversed(node.children):
                stack.append((child, nodedepth + 1))

Depth-limited DFS general/non-binary 树搜索？

Depth-limited DFS general/non-binary tree search?

tree

depth-first-search