迭代图DFS如何添加后序遍历？

Question

我尝试实现以下图形 DFS 方法：

 /** Performs a depth-first traversal of G over all vertices
 *  reachable from V.  That is, the fringe is a sequence and
 *  vertices are added to it or removed from it at one end in
 *  an undefined order.  After the traversal of all successors of
 *  a node is complete, the node itself is revisited by calling
 *  the postVisit method on it. */
public void depthFirstTraverse(Graph<VLabel, ELabel> G,
                               Graph<VLabel, ELabel>.Vertex v) {
    Stack<Vertex> fringe = new Stack<Vertex>();
    HashSet<Vertex> marked = new HashSet<Vertex>();
    fringe.push(v);
    while (!fringe.isEmpty()) {
        Vertex vert = fringe.pop();
        if (!marked.contains(vert)) {
            marked.add(vert);
            visit(vert);
            for (Edge edge : G.edges(vert)) {
                preVisit(edge, vert);
                fringe.add(edge.getV1());
            }
        }
    }
}

根据我的测试，我已经掌握了一般的算法，但是我仍然缺少最后一句话中的要求：“在遍历完一个节点的所有后继节点之后，通过调用 postVisit 方法重新访问该节点本身。”我不知道如何迭代地添加这个 postVisit 方法（不能更改函数签名，所以递归不可行）。有什么想法吗？

- Brandon

Answer 1

你需要一个堆栈，能够标记顶点为已访问和已处理。只要堆栈不为空，就按照以下步骤进行，其中v是堆栈上的顶点。

• v既没有标记为已访问也没有标记为已处理：将所有未访问的邻居推入堆栈。重要提示：不要弹出v。
• v被标记为已访问但未标记为已处理：这是您调用v上的postVisit的时候。之后必须从堆栈中弹出v并将其标记为已处理
• v被标记为已访问和已处理：只需从堆栈中弹出v并什么都不做。

- Thomas

---

这个想法非常简单，但我整天都在苦苦挣扎。抓住机会。 - zefciu