java中后序图遍历的迭代版本

Question

我正在寻找java中图后顺序遍历的迭代版本。我已经编写了代码来执行迭代的DFS。我如何修改代码，以便下面的代码能够打印出迭代后顺序DFS遍历的路径？例如，下图的输出应该是FCBEDA(G)。

​

​

public void DFS(int sourceVertex) {
     Stack<Integer> stack = new Stack<>();
     stack.push(sourceVertex);
     while (!stack.isEmpty()) {
          int v = stack.pop();
          if (!marked[v]) {
               marked[v] = true;
               for (int w : v.adj) {
                    stack.push(w);
               }
          }
     }
}

Answer 1

您的图是有向图，您不能从F转到任何其他节点，DFS从F只返回F节点。通常，当您使用不同的起始节点(以及图形是否有向)时，输出是不同的。

迭代DFS算法可以写成：

static List<Node> DFS(Node n) {

    Stack<Node> current = new Stack<>();
    Set<Node> visited = new HashSet<>(); // efficient lookup
    List<Node> result = new ArrayList<>(); // ordered

    current.push(n);

    while(!current.isEmpty()) {
        Node c = current.pop();
        if(!visited.contains(c)) {
            result.add(c);
            visited.add(c);
            // push in reversed order
            IntStream.range(0, c.getChildren().size())
                    .forEach(i -> current.push(c.getChildren().get(c.getChildren().size() - i - 1)));
        }
    }

    return result;
}

您可以避免visited Set，但是可以使用result来检查节点是否被访问，当Set采取O(1) (摊销)时，采取O(n)时间。

一个完整的例子：

public static void main(String[] args) {

    Node A = new Node("A");
    Node B = new Node("B");
    Node C = new Node("C");
    Node D = new Node("D");
    Node E = new Node("E");
    Node F = new Node("F");
    Node G = new Node("G");

    A.getChildren().addAll(asList(B, D));
    B.getChildren().addAll(asList(C));
    C.getChildren().addAll(asList(F));
    D.getChildren().addAll(asList(B, F, E));
    E.getChildren().addAll(asList(F));
    //F.getChildren().addAll(asList());
    G.getChildren().addAll(asList(F));

    testDFS(F);
    testDFS(G);
    testDFS(A);

}

static class Node {
    private final String label;
    private final List<Node> children;

    Node(String label) {
        this.label = label;
        this.children = new ArrayList<>();
    }

    public String getLabel() {
        return label;
    }

    public List<Node> getChildren() {
        return children;
    }

    @Override
    public int hashCode() {
        return getLabel().hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof Node))
            return false;
        return getLabel().equals(((Node) obj).getLabel());
    }
}

产出：

From 'F': F
From 'G': G, F
From 'A': A, B, C, F, D, E

如果您希望postorder (首先显示上次访问的节点)，反转结果列表(或添加到head等)。

若要反转children顺序，请在插入之前不要反转：

static List<Node> DFSreversedPostOrder(Node n) {

    Stack<Node> current = new Stack<>();
    Set<Node> visited = new HashSet<>(); // efficient lookup
    List<Node> result = new ArrayList<>(); // ordered

    current.push(n);

    while(!current.isEmpty()) {
        Node c = current.pop();
        if(!visited.contains(c)) {
            result.add(0, c);
            visited.add(c);
            c.getChildren().forEach(current::push);
        }
    }

    return result;
}

现在，你得到了CBFEDA

From 'F': F
From 'G': F, G
From 'A': C, B, F, E, D, A

注意:您的示例是错误的，因为在E节点之后，您必须访问F而不是B。

Answer 2

您应该尽可能深入的方法，然后将其放在postorder列表中：

public LinkedList<Integer> postorder(Digraph digraph, int source) {

    Stack<Integer> stack = new Stack<>();
    LinkedList<Integer> postorder = new LinkedList<>();

    visited[source] = true;           // visited = new boolean[V], # of vertices
    stack.push(source);

    while (!stack.isEmpty()) {

        int cur = stack.peek();       // don't pop(), just peek(), we will pop() it 
        boolean tail = true;          // only if this vertex is tail
        for (Integer v : digraph.adj(cur)) {
            if (visited[v] == false) {
                tail = false;         // found one vertex that can be approached next
                visited[v] = true;    // then vertex cur is not tail yet 
                stack.push(v);
                break;                // one neighbor is found and that is enough, 
                                      // let's examine it in next peek(), others 
            }                         // will be found later
        }                             
        if (tail) {                   // we didn't enter for-loop above, then cur is 
            stack.pop();              // tail, we pop() it and add to postorder list
            postorder.addLast(cur);
        }

    }
    return postorder; 
}

代码中的注释应该解释方法。