使用Stack，以下是要遵循的步骤:

如果可能，访问一个相邻的未访问顶点，标记它， 然后把它推到堆栈上。 如果您不能遵循第1步，那么，如果可能的话，弹出一个顶点 堆栈。 如果你不能遵循第1步或第2步，你就完了。

下面是执行上述步骤的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;
}

使用堆栈来跟踪节点

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)

}

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

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

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

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

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。

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