2 votes 2 votes How many times 8 is pushed into stack ? a detail answer will be welcomed. Programming in C stack graph-theory depth-first-search + – vishwa ratna asked Nov 10, 2016 • edited Nov 10, 2016 by Habibkhan vishwa ratna 2.5k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Habibkhan commented Nov 10, 2016 reply Follow Share What is the starting vertex of DFS?? SInce answer will differ based on this.. 1 votes 1 votes vishwa ratna commented Nov 10, 2016 reply Follow Share should be 1 0 votes 0 votes Amit Pal commented Nov 25, 2016 reply Follow Share Habibkhan . for the first part what will be the ans . According to me all vertices will pushed in to stack . 1 votes 1 votes Purple commented Jan 12, 2017 reply Follow Share Why will a vertex be added more than once in the stack? https://www.tutorialspoint.com/data_structures_algorithms/depth_first_traversal.htm I checked and I still don't get how any node will be added more than once. Also, all nodes will be added in the stack. How can there be some nodes which are not added in the stack? 0 votes 0 votes Please log in or register to add a comment.
Best answer 5 votes 5 votes Given graph according to adjacency list . Answer will be 3. Solution : X means already visted and Down arrow means need to check. Prashant. answered Nov 10, 2016 • selected Nov 10, 2016 by vishwa ratna Prashant. comment Share Follow See all 4 Comments See all 4 4 Comments reply thor commented Dec 10, 2016 reply Follow Share Every element is pushed onto stack only once, because in typical DFS implementation we check whether a vertex is visted or not befor calling dfs. if(visited[i]==0) dfs(i) If dfs(8) is excuted once means vertex-8 is pushed once, then next time visited[8]=1. And condition evaluates to be false and dfs is not called on vertex 8. And What will be answer for part-1 of question? 3 votes 3 votes Shivam Chauhan commented Dec 11, 2016 i edited by Shivam Chauhan Dec 11, 2016 reply Follow Share @Anirudh sir What will be answer for part-1 of question? 0 votes 0 votes Purple commented Jan 12, 2017 reply Follow Share Ideally all will be pushed, but since that is not the option, so i guess it is option 1. 1 votes 1 votes Nidhi Budhraja commented Nov 13, 2018 reply Follow Share Pls explain the figure. 0 votes 0 votes Please log in or register to add a comment.