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()删除并返回列表中的第一个元素。

虽然“使用堆栈”可能是人为的面试问题的答案，但实际上，它只是显式地做递归程序在幕后所做的事情。

递归使用程序内置堆栈。当你调用一个函数时，它将函数的参数推入堆栈，当函数返回时，它通过弹出程序堆栈来执行。

如果你有指向父节点的指针，你可以在没有额外内存的情况下完成。

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

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

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

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

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。

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中的所有节点。