1 votes 1 votes How to know no. of back edges in directed as well in undirected graph using DFS..can some1 tell some good source.?? cse23 asked Oct 7, 2016 cse23 491 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Habibkhan commented Oct 7, 2016 reply Follow Share Just do a DFS traversal of the graph.Those nodes visited first can be treated as ancestor and coming later can be treated as descendent . So after doing DFS traversal , if in the graph u find the edges which are directed from descendent to ancestor in the graph w.r.t the DFS traversal done earlier , then such edges are referred to as back edges. 0 votes 0 votes dd commented Oct 7, 2016 reply Follow Share reference : Page 6 Images in this pdf 1 votes 1 votes Please log in or register to add a comment.
2 votes 2 votes Tree edges which used in Dfs traversal. Back edges ehich is goes already visited node ( condition here is it is ancestors) in dfs traversal. Prashant. answered Oct 7, 2016 • edited Oct 7, 2016 by Prashant. Prashant. comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments cse23 commented Oct 8, 2016 reply Follow Share i am not able to paste the screen-shot here..can any1 suggest how to do? 0 votes 0 votes cse23 commented Oct 8, 2016 reply Follow Share oh..ya..sorry u r ryt,there is no back edge concept in BFS. so with cross edge and forward edge, cycle is possible by doing BFS? 0 votes 0 votes Prashant. commented Oct 8, 2016 reply Follow Share In BFs case if cycle is thier then always cross edge present but vice versa no true since for cross edges are prsent in graph when no cycle. 0 votes 0 votes Please log in or register to add a comment.