A question regarding DFS

As we know, DFS(Depth First Search) is the pre-order traverse of a binary tree. Here is the typical implementaion of DFS,

Code:

---

void treeDFS(mynode *root)
{
    if(root == 0)
      return;

    printf("[%d] ", root->value);
    root->visited = 1;
   
    if (root->left)
    {
      if(root->left->visited==0)
      {
        treeDFS(root->left);
      }
    }

    if (root->right)
    {
      if(root->right->visited==0)
      {
        treeDFS(root->right);
      }
    }
}

---

My question is that why'd we need to mark each visited vertex? If I follow the pre-order , I don't need to mark each visited vertex. Any guru here can give me an explaination why?

DFS is a general search algorithm for graphs, not just for trees, and as such, it needs to be informed which nodes have already been visited since it might be possible to reach the same node several times from different paths.
The implementation you suggested only fits binary trees, and won't work for any general graph.

Regards,
Zachm

Thanks for your explaination.

Quote:

---

Originally Posted by Zachm

DFS is a general search algorithm for graphs, not just for trees, and as such, it needs to be informed which nodes have already been visited since it might be possible to reach the same node several times from different paths.
The implementation you suggested only fits binary trees, and won't work for any general graph.

Regards,
Zachm

---