algorithm - 图和树的DFS区别

Question

我试图理解一般图和树的 DFS 算法。我注意到打印出的节点顺序对于图形和树是不同的。

在 Graphs 中，我们打印父节点，然后打印子节点。

void Graph::DFS(int v)
{   
    // Mark the current node as visited and print it
    visited[v] = true;
    cout << v << " ";

    // Recur for all the vertices adjacent to this vertex
    vector<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
    if (!visited[*i])
        DFS(*i);

}

在树中，我们先打印子节点再打印父节点

void DFS(struct node *head)
{
    if (head)
    {
        if (head->left)
        {
            DFS(head->left);
        }
        if (head->right)
        {
            DFS(head->right);
        }
        printf("%d  ", head->a);
    }
}

我想知道为什么两者的顺序不同。应该一样吗？我认为我对算法的理解是错误的。有人可以纠正我吗？

Answer 1

遍历图中的节点时有两种变体:前序和后序。在二叉树中，还有另一种选择:有序。有区别:

1. 预序:当前节点在处理它的邻居/子节点之前被处理。

2. 后序:当前节点在处理它的邻居/子节点后被处理。

3. In-order:只适用于二叉树。首先处理左 child ，然后是当前节点，最后是右 child 。

不同的变体在不同的情况下很有用，例如遍历 BST in-order 将按顺序给出它的元素。