0 votes 0 votes Algorithms algorithms graph-algorithms test-series + – vaishali jhalani asked Jan 7, 2017 • retagged Jul 14, 2022 by makhdoom ghaya vaishali jhalani 2.7k views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply santhoshdevulapally commented Jan 7, 2017 reply Follow Share If i remove edge b/w B and E the graph is acyclic. then apply DFS starts from vertex A. A-B-C-E-D. It results two back edges D-C and E-B. most cases it results only one back edge and in certain case like above it results two also. Hence it results multiple back edges. 2 votes 2 votes saurabh rai commented Jan 7, 2017 reply Follow Share bt d-c is nt back edge it is cross edge 0 votes 0 votes vaishali jhalani commented Jan 7, 2017 reply Follow Share If some node is previously visited and we visit that node again then that edge is the back edge. 0 votes 0 votes santhoshdevulapally commented Jan 7, 2017 reply Follow Share yes.bro. i missed it 1 votes 1 votes santhoshdevulapally commented Jan 7, 2017 reply Follow Share Once u refer Coreman text book for DFS traversal,then u can easily understand. parent node time intervals are u/v and child is x/y then backside lies in b/w parent.i.e)u<=x<=y<=v // condition for back edges. 0 votes 0 votes Akriti sood commented Jan 7, 2017 reply Follow Share so,whats the answer ..single or multiple?? 0 votes 0 votes MIRIYALA JEEVAN KUMA commented Jan 23, 2018 reply Follow Share https://gateoverflow.in/145735/dfs-back-edge 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes here is a result given in cormen book..... A directed graph G is acyclic iff depth first search of G yields no back edges i think b is correct saurabh rai answered Jan 7, 2017 saurabh rai comment Share Follow See all 0 reply Please log in or register to add a comment.