A question regarding DFS
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3

Thread: A question regarding DFS

  1. #1
    Join Date
    Jul 2005
    Posts
    928

    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?

  2. #2
    Join Date
    Oct 2006
    Posts
    616

    Re: A question regarding DFS

    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

  3. #3
    Join Date
    Jul 2005
    Posts
    928

    Re: A question regarding DFS

    Thanks for your explaination.
    Quote Originally Posted by Zachm View Post
    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

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center