我正在寻找一个非二叉树的非递归深度优先搜索算法。任何帮助都非常感激。
当前回答
假设您希望在访问图中的每个节点时执行通知。简单的递归实现是:
void DFSRecursive(Node n, Set<Node> visited) {
visited.add(n);
for (Node x : neighbors_of(n)) { // iterate over all neighbors
if (!visited.contains(x)) {
DFSRecursive(x, visited);
}
}
OnVisit(n); // callback to say node is finally visited, after all its non-visited neighbors
}
好的,现在你需要一个基于堆栈的实现,因为你的例子不起作用。例如,复杂的图形可能会导致程序的堆栈崩溃,您需要实现一个非递归版本。最大的问题是知道何时发出通知。
下面的伪代码可以工作(为了可读性,Java和c++混合使用):
void DFS(Node root) {
Set<Node> visited;
Set<Node> toNotify; // nodes we want to notify
Stack<Node> stack;
stack.add(root);
toNotify.add(root); // we won't pop nodes from this until DFS is done
while (!stack.empty()) {
Node current = stack.pop();
visited.add(current);
for (Node x : neighbors_of(current)) {
if (!visited.contains(x)) {
stack.add(x);
toNotify.add(x);
}
}
}
// Now issue notifications. toNotifyStack might contain duplicates (will never
// happen in a tree but easily happens in a graph)
Set<Node> notified;
while (!toNotify.empty()) {
Node n = toNotify.pop();
if (!toNotify.contains(n)) {
OnVisit(n); // issue callback
toNotify.add(n);
}
}
它看起来很复杂,但发出通知所需的额外逻辑存在,因为您需要以相反的访问顺序通知- DFS从根开始,但在最后通知它,不像BFS实现非常简单。
看看下面的图表: 节点是s t v w。 有向边为: S ->t, S ->v, t->w, v->w, v->t。 运行你自己的DFS实现,访问节点的顺序必须是: W t v s 一个笨拙的DFS实现可能会首先通知t,这表明存在错误。DFS的递归实现总是最后到达w。
其他回答
伪代码基于@biziclop的答案:
只使用基本结构:变量、数组、if、while和for 函数getNode(id)和getChildren(id) 假设已知节点数N
注意:我从1开始使用数组索引,而不是0。
广度优先
S = Array(N)
S[1] = 1; // root id
cur = 1;
last = 1
while cur <= last
id = S[cur]
node = getNode(id)
children = getChildren(id)
n = length(children)
for i = 1..n
S[ last+i ] = children[i]
end
last = last+n
cur = cur+1
visit(node)
end
深度优先
S = Array(N)
S[1] = 1; // root id
cur = 1;
while cur > 0
id = S[cur]
node = getNode(id)
children = getChildren(id)
n = length(children)
for i = 1..n
// assuming children are given left-to-right
S[ cur+i-1 ] = children[ n-i+1 ]
// otherwise
// S[ cur+i-1 ] = children[i]
end
cur = cur+n-1
visit(node)
end
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中的所有节点。
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()
}
如果你有指向父节点的指针,你可以在没有额外内存的情况下完成。
def dfs(root):
node = root
while True:
visit(node)
if node.first_child:
node = node.first_child # walk down
else:
while not node.next_sibling:
if node is root:
return
node = node.parent # walk up ...
node = node.next_sibling # ... and right
注意,如果子节点存储为数组而不是通过兄弟指针,那么下一个兄弟节点可以通过以下方式找到:
def next_sibling(node):
try:
i = node.parent.child_nodes.index(node)
return node.parent.child_nodes[i+1]
except (IndexError, AttributeError):
return None
Java中的DFS迭代:
//DFS: Iterative
private Boolean DFSIterative(Node root, int target) {
if (root == null)
return false;
Stack<Node> _stack = new Stack<Node>();
_stack.push(root);
while (_stack.size() > 0) {
Node temp = _stack.peek();
if (temp.data == target)
return true;
if (temp.left != null)
_stack.push(temp.left);
else if (temp.right != null)
_stack.push(temp.right);
else
_stack.pop();
}
return false;
}