非递归深度优先搜索算法【已关闭】

Question

17 浏览2023年5月21日

匿名的 2022年8月3日

0 Comments

已关闭。这个问题需要更加专注。它目前不接受回答。

想改进这个问题？通过编辑这个帖子使其专注于一个问题。

社区评估了是否重新开放这个问题11个月之前并将其关闭：

原来的关闭原因没有得到解决

改进这个问题

我正在寻找一种用于非二叉树的非递归深度优先搜索算法。非常感谢任何帮助。

admin 更改状态以发布 2023年5月21日

0

2 答案

匿名的 · Answer 1 · 2022-08-03T20:57:58+00:00

你可以使用一个栈来保存尚未访问的节点：

stack.push(root)
while !stack.isEmpty() do
    node = stack.pop()
    for each node.childNodes do
        stack.push(stack)
    endfor
    // …
endwhile

。该栈通常被称为“未访问栈”，可以帮助在深度优先搜索算法中追踪所需的信息。具体而言，如果遇到一个新的节点，请将其添加到未访问栈中，而不是立即访问它。如此，程序将能够确保在搜索到当前最深的节点之前访问所有离根节点更远的节点。

匿名的 · Answer 2 · 2022-08-03T20:57:58+00:00

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
}

BFS：

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

这两者的对称性非常酷。

更新:如指出的那样，take_first()从列表中移除并返回第一个元素。