深度限制的DFS通用/非二进制树搜索？

发布于 2025-01-20 22:41:12 字数 622 浏览 2 评论 0原文

假设您有一个无限大的通用/非二进制要搜索。由于树无限大，详尽的 DFS 或 BFS 策略是不可行的。然而，非常需要参数深度=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
}

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

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

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

原文

Suppose you had an infinitely large general/non-binary to search. Because the tree is infinitely large, an exhaustive DFS or BFS strategy is not feasible. However, a DFS search with parameter, depth=n, is highly desirable.

Taking this Q/A for inspiration, DFS can be executed

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
}

The key insight is that a stack is used such that nodes that need visiting are inserted at the start of the list and this process repeats until there are no more children to prepend to the stack.

The major problem when considering depth. We might introduce a variable, d, which is initialized at 0 and increment it each time that children are added to the stack. However, with a variable number of children, the stack has no of mechanism to know when d should be decremented (when all the children at a certain depth have been visited.)

How should a depth limited DFS be implemented? (Pseudo code or python preferred.)

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

浅浅淡淡 2025-01-27 22:41:12

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

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

下面是一些可以完成这项工作的 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))

You could deal with the maximum depth by stacking the node together with its depth.

Not your question, but in most languages it is more natural (and efficient) to grow a stack at the end, not at the start.

Here is some Python code that would do the job:

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))

回复收藏 0 原文

~没有更多了~