chinesecoder's blog

By chinesecoder, history, 11 months ago, In English,

suppose we are doing dfs on tree .

Your code here...

dfs(int current ,  int parent)
{
     for(auto child : v[current]
    {
        if(child == parent) continue ;
        dfs(child , current);
         code...
       what happens when we write something here. 
        
}
code .... 
And what happens when we write something here ... 

}

what are the difference between two above .

Please tell , i have difficulty in distinguishing between two

 
 
 
 
  • Vote: I like it
  • -4
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the first, you do something after you visit each child (e.g. count number of subtrees).

In the second, you do something just before you exit the node (e.g. mark this node as visited).

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    ok .. i understand the first one.. that in case 1 while visiting every child we also do some operations simultaneously. and the operation will only util the last child is visted.. just like a part of subtree.

    case u eleborate 2nd case. what u mean here by exiting the node. does it mean that when we explored all the child of a current node. then we do some processing in step2 ? please tell

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes. For the second case, the operation is done only after all subtrees have been visited and before the recursion returns to the parent node.