与 DFS 实施混淆

Question

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

我对 DFS 算法感到困惑。上述代码将所有子节点入栈，出栈并访问直到到达尾节点，而另一种实现（参考link后）将一个节点入栈，访问直到到达尾节点结束节点和回溯。

以上代码是DFS算法的实现吗？如是？它与其他 DFS 实现有何不同？其他DFS算法的输出应该是：

输出：

A B E F C D

参考： Introduction to Graph with Breadth First Search(BFS) and Depth First Search(DFS) Traversal Implemented in JAVA

Answer 1

输出不同，但您的实施是正确的。我不知道您是如何构建自己的图的，但我认为它有所不同，因为该算法从右到左访问了根节点的邻居。

你的根节点 (A) 的邻居是一个有序数组 [D, C, B]

所以A先访问了D，然后是C，依此类推...它只是从右到左。毕竟，这实际上取决于您构建图表的方式。

我假设你的图表是颠倒的。

Answer 2

它之所以成为 DFS（深度-首次搜索）是因为它通过在回溯和访问其他节点之前不断访问图中越来越深的节点来遍历图已添加到堆栈的节点。 注意：这不能保证以指定的顺序访问节点。两个完美的 DFS 实现可以有完全不同的输出，如果它们只是选择以不同的顺序访问节点，例如从左侧 (A -> B) 而不是右侧 (A -> D) 侧开始。

与 DFS 实施混淆

Confused with DFS implementation

java

graph

depth-first-search

graph-traversal