在非递归广度优先搜索中跟踪深度

Question

我有以下算法用于广度优先搜索:

q := []
q.append(root node of tree)
while q:
    n := q.pop(0)
    yield n
        if n has children:
            c := children of node
            for i in c:
                q.append(i)

1)如何延长它以便跟踪当前深度？2)此扩展是否适用于深度优先搜索的类似算法,队列q被堆栈替换？

Answer 1

只需存储节点的深度,并在每次生成节点的子节点时将其递增.

q := [(root, 0)]
while q:
    n, depth := q.pop()
    yield n, depth
    if n has children:
        c := children of n
        for i in c:
            q.append(i, depth + 1)

这个想法延伸到DFS和启发式引导搜索.