非递归深度优先搜索算法。

I am looking for a non-recursive depth first search algorithm for a non-binary tree. Any help is very much appreciated.

我正在寻找一个非递归深度优先搜索算法的非二叉树。非常感谢您的帮助。

14 个解决方案

#1

DFS:

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
}

The symmetry of the two is quite cool.

这两者的对称性很酷。

Update: As pointed out, take_first() removes and returns the first element in the list.

更新:如前所述，take_first()删除并返回列表中的第一个元素。

#2

You would use a stack that holds the nodes that were not visited yet:

您将使用一个栈来保存尚未访问的节点:

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

#3

If you have pointers to parent nodes, you can do it without additional memory.

如果您有指向父节点的指针，那么您可以在不增加内存的情况下完成它。

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

Note that if the child nodes are stored as an array rather than through sibling pointers, the next sibling can be found as:

注意，如果子节点以数组的形式存储，而不是通过兄弟指针，则可以找到下一个兄弟节点:

def next_sibling(node):
    try:
        i =    node.parent.child_nodes.index(node)
        return node.parent.child_nodes[i+1]
    except (IndexError, AttributeError):
        return None

#4

Use a stack to track your nodes

使用堆栈跟踪节点。

Stack<Node> s;

s.prepend(tree.head);

while(!s.empty) {
    Node n = s.poll_front // gets first node

    // do something with q?

    for each child of n: s.prepend(child)

}

#5

An ES6 implementation based on biziclops great answer:

基于biziclop的ES6实现很好的答案:

root = {
  text: "root",
  children: [{
    text: "c1",
    children: [{
      text: "c11"
    }, {
      text: "c12"
    }]
  }, {
    text: "c2",
    children: [{
      text: "c21"
    }, {
      text: "c22"
    }]
  }, ]
}

console.log("DFS:")
DFS(root, node => node.children, node => console.log(node.text));

console.log("BFS:")
BFS(root, node => node.children, node => console.log(node.text));

function BFS(root, getChildren, visit) {
  let nodesToVisit = [root];
  while (nodesToVisit.length > 0) {
    const currentNode = nodesToVisit.shift();
    nodesToVisit = [
      ...nodesToVisit,
      ...(getChildren(currentNode) || []),
    ];
    visit(currentNode);
  }
}

function DFS(root, getChildren, visit) {
  let nodesToVisit = [root];
  while (nodesToVisit.length > 0) {
    const currentNode = nodesToVisit.shift();
    nodesToVisit = [
      ...(getChildren(currentNode) || []),
      ...nodesToVisit,
    ];
    visit(currentNode);
  }
}

#6

While "use a stack" might work as the answer to contrived interview question, in reality, it's just doing explicitly what a recursive program does behind the scenes.

虽然“使用堆栈”可以作为设计面试问题的答案，但在现实中，它只是明确地做了一个递归程序在幕后做什么。

Recursion uses the programs built-in stack. When you call a function, it pushes the arguments to the function onto the stack and when the function returns it does so by popping the program stack.

递归使用程序内置的堆栈。当你调用一个函数时，它将参数推到堆栈上，当函数返回时，它会弹出程序堆栈。

#7

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);

                }
            }

The general logic is, push a node(starting from root) into the Stack, Pop() it and Print() value. Then if it has children( left and right) push them into the stack - push Right first so that you will visit Left child first(after visiting node itself). When stack is empty() you will have visited all nodes in Pre-Order.

一般的逻辑是，将节点(从根开始)推入堆栈、Pop()和Print()值。然后，如果它有孩子(左和右)将它们推入堆栈——先右推，这样您就会先访问左子(访问节点本身之后)。当堆栈为空()时，您将访问所有的节点。

#8

Suppose you want to execute a notification when each node in a graph is visited. The simple recursive implementation is:

假设您希望在访问图中的每个节点时执行通知。简单的递归实现是:

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
}

Ok, now you want a stack-based implementation because your example doesn't work. Complex graphs might for instance cause this to blow the stack of your program and you need to implement a non-recursive version. The biggest issue is to know when to issue a notification.

现在，您需要基于堆栈的实现，因为您的示例不起作用。例如，复杂的图可能会使程序的堆栈崩溃，而您需要实现非递归版本。最大的问题是知道何时发出通知。

The following pseudo-code works (mix of Java and C++ for readability):

下面的伪代码工作(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);
  }
}

It looks complicated but the extra logic needed for issuing notifications exists because you need to notify in reverse order of visit - DFS starts at root but notifies it last, unlike BFS which is very simple to implement.

它看起来很复杂，但是发出通知所需的额外逻辑是存在的，因为您需要以相反的顺序通知访问—DFS从根开始，但最后通知它，不像BFS，它很容易实现。

For kicks, try following graph: nodes are s, t, v and w. directed edges are: s->t, s->v, t->w, v->w, and v->t. Run your own implementation of DFS and the order in which nodes should be visited must be: w, t, v, s A clumsy implementation of DFS would maybe notify t first and that indicates a bug. A recursive implementation of DFS would always reach w last.

对于踢腿，可以尝试以下图:节点为s、t、v、w向边为:s->t、s->v、t->w、v->w、v->t。运行您自己的DFS实现和访问节点的顺序必须是:w、t、v, DFS的笨拙实现可能会首先通知t，这表示bug。DFS的递归实现总是会达到w的最后。

#9

Non-recursive DFS using ES6 generators

使用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 
  }    
}

It deviates from typical non-recursive DFS to easily detect when all reachable descendants of given node were processed and to maintain the current path in the list/stack.

它偏离了典型的非递归DFS，以便在处理给定节点的所有可到达的后代并维护列表/堆栈中的当前路径时轻松地检测。

#10

You can use a stack. I implemented graphs with Adjacency Matrix:

您可以使用堆栈。我用邻接矩阵实现了图形:

void DFS(int current){
    for(int i=1; i<N; i++) visit_table[i]=false;
    myStack.push(current);
    cout << current << "  ";
    while(!myStack.empty()){
        current = myStack.top();
        for(int i=0; i<N; i++){
            if(AdjMatrix[current][i] == 1){
                if(visit_table[i] == false){ 
                    myStack.push(i);
                    visit_table[i] = true;
                    cout << i << "  ";
                }
                break;
            }
            else if(!myStack.empty())
                myStack.pop();
        }
    }
}

#11

DFS iterative in Java:

DFS在Java迭代:

//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;
}

#12

http://www.youtube.com/watch?v=zLZhSSXAwxI

http://www.youtube.com/watch?v=zLZhSSXAwxI

Just watched this video and came out with implementation. It looks easy for me to understand. Please critique this.

只是看了这段视频，然后就出来了。我很容易理解。请批评。

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()
}

#13

Using Stack, here are the steps to follow: Push the first vertex on the stack then,

使用堆栈，这里是下面的步骤:在堆栈上按第一个顶点，

1. If possible, visit an adjacent unvisited vertex, mark it, and push it on the stack.
2. 如果可能，访问一个相邻的未访问顶点，标记它，并将其推到堆栈上。
3. If you can’t follow step 1, then, if possible, pop a vertex off the stack.
4. 如果您不能遵循步骤1，那么，如果可能的话，从堆栈中弹出一个顶点。
5. If you can’t follow step 1 or step 2, you’re done.
6. 如果你不能遵循步骤1或步骤2，你就完成了。

---

Here's the Java program following the above steps:

下面是Java程序的步骤:

public void searchDepthFirst() {
    // begin at vertex 0
    vertexList[0].wasVisited = true;
    displayVertex(0);
    stack.push(0);
    while (!stack.isEmpty()) {
        int adjacentVertex = getAdjacentUnvisitedVertex(stack.peek());
        // if no such vertex
        if (adjacentVertex == -1) {
            stack.pop();
        } else {
            vertexList[adjacentVertex].wasVisited = true;
            // Do something
            stack.push(adjacentVertex);
        }
    }
    // stack is empty, so we're done, reset flags
    for (int j = 0; j < nVerts; j++)
            vertexList[j].wasVisited = false;
}

#14

        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);
            }
        }