我正在寻找一个非二叉树的非递归深度优先搜索算法。任何帮助都非常感激。
当前回答
你可以使用一个堆栈来保存尚未访问的节点:
stack.push(root)
while !stack.isEmpty() do
node = stack.pop()
for each node.childNodes do
stack.push(stack)
endfor
// …
endwhile
其他回答
PreOrderTraversal is same as DFS in binary tree. You can do the same recursion
taking care of Stack as below.
public void IterativePreOrder(Tree root)
{
if (root == null)
return;
Stack s<Tree> = new Stack<Tree>();
s.Push(root);
while (s.Count != 0)
{
Tree b = s.Pop();
Console.Write(b.Data + " ");
if (b.Right != null)
s.Push(b.Right);
if (b.Left != null)
s.Push(b.Left);
}
}
一般的逻辑是,将一个节点(从根开始)推入Stack, Pop()它和Print()值。然后,如果它有子节点(左和右),将它们推入堆栈-先推右,这样你就会先访问左子节点(在访问节点本身之后)。当stack为空()时,您将访问Pre-Order中的所有节点。
使用ES6生成器的非递归DFS
class Node {
constructor(name, childNodes) {
this.name = name;
this.childNodes = childNodes;
this.visited = false;
}
}
function *dfs(s) {
let stack = [];
stack.push(s);
stackLoop: while (stack.length) {
let u = stack[stack.length - 1]; // peek
if (!u.visited) {
u.visited = true; // grey - visited
yield u;
}
for (let v of u.childNodes) {
if (!v.visited) {
stack.push(v);
continue stackLoop;
}
}
stack.pop(); // black - all reachable descendants were processed
}
}
它与典型的非递归DFS不同,可以很容易地检测给定节点的所有可达后代何时被处理,并维护列表/堆栈中的当前路径。
http://www.youtube.com/watch?v=zLZhSSXAwxI
刚刚看了这个视频,并提出了实施方案。这对我来说似乎很容易理解。请评论一下。
visited_node={root}
stack.push(root)
while(!stack.empty){
unvisited_node = get_unvisited_adj_nodes(stack.top());
If (unvisited_node!=null){
stack.push(unvisited_node);
visited_node+=unvisited_node;
}
else
stack.pop()
}
只是想把我的python实现添加到长长的解决方案列表中。这种非递归算法具有发现和完成事件。
worklist = [root_node]
visited = set()
while worklist:
node = worklist[-1]
if node in visited:
# Node is finished
worklist.pop()
else:
# Node is discovered
visited.add(node)
for child in node.children:
worklist.append(child)
这是一个java程序的链接,显示DFS同时遵循递归和非递归方法,还计算发现和完成时间,但没有边对齐。
public void DFSIterative() {
Reset();
Stack<Vertex> s = new Stack<>();
for (Vertex v : vertices.values()) {
if (!v.visited) {
v.d = ++time;
v.visited = true;
s.push(v);
while (!s.isEmpty()) {
Vertex u = s.peek();
s.pop();
boolean bFinished = true;
for (Vertex w : u.adj) {
if (!w.visited) {
w.visited = true;
w.d = ++time;
w.p = u;
s.push(w);
bFinished = false;
break;
}
}
if (bFinished) {
u.f = ++time;
if (u.p != null)
s.push(u.p);
}
}
}
}
}
这里是完整的源代码。