我正在寻找一个非二叉树的非递归深度优先搜索算法。任何帮助都非常感激。
当前回答
假设您希望在访问图中的每个节点时执行通知。简单的递归实现是:
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。
其他回答
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()删除并返回列表中的第一个元素。
你可以使用一个堆栈来保存尚未访问的节点:
stack.push(root)
while !stack.isEmpty() do
node = stack.pop()
for each node.childNodes do
stack.push(stack)
endfor
// …
endwhile
Stack<Node> stack = new Stack<>();
stack.add(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
System.out.print(node.getData() + " ");
Node right = node.getRight();
if (right != null) {
stack.push(right);
}
Node left = node.getLeft();
if (left != null) {
stack.push(left);
}
}
假设您希望在访问图中的每个节点时执行通知。简单的递归实现是:
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。
这是一个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);
}
}
}
}
}
这里是完整的源代码。
