使用堆栈以 DFS 顺序遍历图形

Question

我正在尝试按 dfs 顺序迭代遍历一个图。
下面是我的代码。 当我对此进行测试时，输出与递归 dfs 的输出不同（也包括在下面）。

有人可以帮忙调试吗？

  public static void dfs(GraphNode root) {
        if (root != null && !root.visited) {
            for (GraphNode kid : root.children) {
                dfs(kid);
            }
            System.out.println(root);
            root.visited = true;
        }
    }

  public static void dfsIter(GraphNode root) {
        Stack<GraphNode> stack = new Stack<>();
        stack.push(root);

        do {
            GraphNode cur = stack.pop();
            if (cur != null && !cur.visited) {
                // leaf node or all children have been visisted
                if (cur.children.isEmpty() || childrenVisisted(cur)) {
                    System.out.println(cur);
                    cur.visited = true;
                }
                else {
                    // put it back
                    stack.push(cur);
                    for (GraphNode child :cur.children) {
                        if (!child.visited) {
                            stack.push(child);
                        }
                    }
                }

            }
        }
        while (!stack.isEmpty());
    }

    static boolean childrenVisisted(GraphNode node) {
        for (GraphNode child : node.children) {
            if (!child.visited) return false;
        }
        return true;
    }

Answer 1

1. 在递归 DFS 中，您应该先标记顶点，然后遍历子节点。否则，如果图形有循环，您将得到一个无限循环。
2. 如果您想在迭代方法中使用相同的遍历顺序，则需要以相反的顺序将子项添加到堆栈中。因为你先弹出最后一个被压入的元素。