所以我尝试实现以下图 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 方法感到相当困惑(无法更改函数签名，因此递归是不可能的)。有任何想法吗？
最佳答案
您需要一个堆栈，能够将顶点标记为已访问，并将顶点标记为已处理。只要堆栈不为空，您就可以执行以下操作，其中 v 是堆栈上的顶部顶点。
- v 既不标记为已访问，也不标记为已处理:将所有未访问的邻居推送到堆栈。重要提示:请勿弹出 v。
- v 被标记为已访问，但未标记为已处理:这是您在 v 上调用 postVisit 的点。之后，您必须从堆栈中弹出 v 并将其标记为已处理
- v 被标记为已访问并已处理:只需将 v 从堆栈中弹出，不执行任何操作。
关于java - 迭代图DFS如何添加后访问？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20309140/