二叉树和图中的 DFS

Question

我对二叉树和图的DFS感到困惑。在我的理解中，二叉树的DFS类似于PreOrder遍历？图中的 DFS 有很大不同吗？请帮助阐明二叉树和 DFS 中的这个概念。我知道在二叉树中，我们可以这样做 DFS：

public static List<int> postorder(TreeNode root)
{
    List<int> res = new List<int>();
    traverse1(root, res);
    return res;
}

public static void traverse1(TreeNode root, List<int> res)
{
    if (root == null)
        return;    

    traverse1(root.left, res);             
    traverse1(root.right, res);
    res.Add(root.val); 
}

图中呢？我们可以这样做吗？

Answer 1

基本一样

为了帮助理解，我认为最好从二叉树过渡到通用树，最后过渡到图。

DFS 和 BFS 只是遍历树和图的技术。它们之间的区别在于访问给定节点的兄弟姐妹和 children 的顺序。在 DFS 中，在遍历下一个兄弟之前访问给定节点的所有 children。

所以在二叉树中，这意味着在访问 X 的右 child 之前访问节点 X 的左 child 的所有后代。

现在如果你想一想一般的树，每个节点都有一个 children 的列表，而不仅仅是左和右 child。所以在一般树的DFS中，先访问节点X的第一个child的所有后代，然后再访问X的第二个child，以及第二个child的所有后代在访问 X 的第三个 child 之前访问 X，依此类推。

DFS 和树的问题是你知道你最终会碰到一片叶子，递归将 return 到调用者（或因堆栈溢出而停止，但这是另一个主题时间）。使用图表，您无法保证。该图可能有环，或者可能有带有多个传入边的顶点。正如我之前提到的，DFS 只是一种技术，而不是一种算法本身，因此您要做的是使该技术适应您正在解决的问题。如果在你正在解决的问题中你对多次访问一个顶点不感兴趣，或者你对在一个循环中无限迭代不感兴趣（或者直到你遇到堆栈溢出），那么你必须添加某种控制代码可以让你摆脱那些情况。

图上 DFS 的一般结构可能类似于：

void DFS(G<V,E> g, V v, Set<V> visited)
{
    if (visited.Contains(v))
        return;
    visited.Add(v);
    // do something interesting here?
    foreach (w in g.getEdges(v))
        DFS(g, w, visited);
    // uncomment this to allow visiting vertices more than once, and just avoid cycles.
    // visited.Remove(v);
}

Answer 2

没有。 深度拳头搜索（DFS）和前序遍历不一样

这些概念与图论和二叉树相互关联，因为二元 tree/tree 结构是图结构的特例。

我们在graphs/trees

中有2种遍历

深度优先遍历（DFS）（也称为层序遍历）
广度优先遍历（BFS）

在广度优先遍历 (BFS) 下我们有

前序（访问顺序根->左子树->右子树）
顺序（访问顺序左子树->根->右子树）
Post顺序（访问顺序左子树->右子树->根）

希望本文能解决您对DFS和预购的困惑。

DFS表示按级别完成节点。意思是访问 level 0 nodes.Then level 1 节点等等。根据图像，DFS将是A,B,C,D,E,F,G,H,I

前序的意思是，先从一个节点开始，然后遍历它的左子树，再遍历它的右子树。如果左子树有一个节点，访问它的左子树，然后访问它的右子树，依此类推。所以前序遍历会是A,B,D,E,H,I,C,F,G

DFS 与预购不同

在此博客上查看更多信息http://goo.gl/gR4oWp

这个也有很好的解释。 https://www.youtube.com/watch?v=gm8DUJJhmY4

Answer 3

图的DFS和二叉树的DFS看起来不一样，但本质上是一样的。如果您记录节点并检查它们，您将看到相似性。

二叉树和图中的 DFS

DFS in binary tree and graph

c#

binary-tree

depth-first-search

postorder