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

Question

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

score 1 · Accepted Answer · answered Apr 12 '22 at 17:49

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

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

1 Answers1