关于DFS代码实现合规性及不同版本遍历输出差异的疑问

你提供的DFS实现代码：

public void dfs(){
    ArrayList<Node> exploredList = new ArrayList<>();
    Stack s=new Stack();
    s.push(this.rootNode);
    while(!s.isEmpty()){
        Node n = (Node)s.pop();
        exploredList.add(n);
        printNode(n);
        ArrayList<Node> childList = getChildNodes(n);
        for (Node child : childList){
            if (!exploredList.contains(child) && !s.contains(child)) {
                s.push(child);
            }
        }
    }
}

运行输出：

A D C F B E 

参考实现输出：

A B E F C D 

1. 该代码属于合法的DFS实现 #

DFS的核心逻辑是优先沿当前节点的分支深入到最末端，再回溯处理其他分支，只要符合这个规则的实现都属于合法DFS，你提供的迭代版本完全满足该逻辑。

2. 和常规DFS实现的核心差异 #

• 子节点入栈逻辑不同：该实现会一次性将当前节点所有未访问的子节点全部压入栈；而常见的递归DFS、另一种迭代DFS实现，是每次仅处理当前节点的第一个未访问子节点，剩余子节点留待回溯时再处理。
• 子节点遍历顺序相反：由于栈是后进先出结构，若getChildNodes返回的子节点顺序固定，该实现会优先处理子节点列表的最后一个元素，常规实现会优先处理子节点列表的第一个元素。

3. 两次输出不同的原因 #

输出差异完全由子节点的入栈顺序导致，和DFS本身的合法性无关：
假设示例图中getChildNodes返回的子节点顺序为：A的子节点是[B, C, D]，B的子节点是[E, F]，C的子节点是[F]：

• 该实现将B、C、D依次压栈，弹出顺序为D→C→B，所以优先走D分支，再走C、B分支，最终输出A D C F B E
• 参考实现优先处理第一个子节点B，再深入B的第一个子节点E，回溯后处理F，再回溯处理C、D分支，最终输出A B E F C D

两种输出都是合法的DFS遍历结果，仅和子节点的处理顺序有关，没有对错之分。

内容的提问来源于stack exchange，提问作者Hisham Syed