圖形和樹之間的DFS差異

Question

我想了解一般圖形和樹木的DFS算法是特定的。我注意到對於圖和樹，打印出的節點順序是不同的。

在圖中，我們打印父節點，然後打印子節點。

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

這些是DFS的兩種變體：預購和後訂單。兩者都有效;你使用哪一個取決於你正試圖解決的問題。

你只是碰巧找到一個後序樹遍歷和一個前序圖遍歷。它也可能以其他方式走了。

Answer 2

遍歷圖中的節點時有兩種變化形式：預訂和後序。在二叉樹中，還有另一種選擇：按順序。有不同之處：

1. 預購：當前節點處理之前處理它的鄰國/兒童。

2. 後爲了：當前節點處理後處理它的鄰國/兒童。

3. 有序：只適用於二叉樹。首先，處理左側的孩子，然後處理當前的節點，最後處理右側的孩子。

不同的變化，在不同的情況下是有用的，例如遍歷BST有序會給它在順序的元件。