CODEWITHSUNDEEP
javagraphdepth-first-search
Brandon
Brandon

Reputation: 1027

Iterative Graph DFS how to add a postvisit?

So I'm attempted to implement the following Graph DFS method:

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

I have the general algorithm correct according to my tests, but I'm still missing the requirement in the last sentence: "After the traversal of all successors of a node is complete, the node itself is revisited by calling the postVisit method on it."

I'm rather stumped on how to add this postVisit method in iteratively (can't change the function signature so recursion is out of the question). Any ideas?

Upvotes: 3

Views: 1196

Answers (1)

Thomas
Thomas

Reputation: 1090

You need a stack, the possibility to mark a vertex as visited, and to mark a vertex as processed. As long as the stack is not empty, you do the following where v is the top vertex on the stack.

  • v is neither marked as visited nor as processed: push all non-visited neighbors to the stack. Important: do NOT pop v.
  • v is marked as visited but not as processed: this is the point where you call the postVisit on v. Afterwards you must pop v from the stack and mark it as processed
  • v is marked as visited and as processed: just pop v from the stack and do nothing.

Upvotes: 4

Related Questions