3 votes 3 votes Is following statement true/false? A DFS of a directed graph always produces the same number of tree edges, i.e., independent of the order in which vertices are considered for DFS. Answer is FALSE please explain Algorithms depth-first-search algorithms + – Rishav Kumar Singh asked Jul 30, 2018 Rishav Kumar Singh 2.0k views answer comment Share Follow See 1 comment See all 1 1 comment reply Shaik Masthan commented Jul 30, 2018 reply Follow Share The statement is should be true, Why because no.of edges in a tree always n-1. I hope they want to ask A DFS of a directed graph always produces the same number of tree edges btw root to some vertex, i.e., independent of the order in which vertices are considered for DFS. Then it is FALSE 2 votes 2 votes Please log in or register to add a comment.
0 votes 0 votes this may help... i think they are asking for this... arvin answered Jul 30, 2018 • edited Jul 30, 2018 by arvin arvin comment Share Follow See all 4 Comments See all 4 4 Comments reply Rishav Kumar Singh commented Jul 30, 2018 reply Follow Share When A->D is selected as first edge then I think B->C can't be possible. 1 votes 1 votes arvin commented Jul 30, 2018 reply Follow Share it is possible as we are using stack and when d is popped out b is pushed than c and than popped out. 0 votes 0 votes Rishav Kumar Singh commented Jul 30, 2018 reply Follow Share In your graph D will not popped out untill it visits C, yes after visiting C it will pop 1 votes 1 votes arvin commented Jul 30, 2018 reply Follow Share yes i got u i was in a hurry i think its right now. i updated 1 votes 1 votes Please log in or register to add a comment.
