586 views

1 Answer

Best answer
2 votes
2 votes

Back edge

In DFS , if u to v there is an front edge, then there will be a back edge if and only if v is ancestor of u.

Yes if there is a back edge, then there will be a cycle in DFS.(that we can simply predict from the definition of Back edge)

Also , self loop is a part of back edge(See picture)

In (i) DFS will be 12314(so, 1 visited twice, then there must be DFS path)

In (ii) DFS will be 1233 (here 3 visited twice) and simulteneously. So, there is a back edge which here is a self loop

https://courses.csail.mit.edu/6.006/fall11/rec/rec14.pdf

http://www.geeksforgeeks.org/detect-cycle-in-a-graph/

selected by

Related questions

0 votes
0 votes
0 answers
1
Na462 asked Nov 7, 2018
1,005 views
1 votes
1 votes
0 answers
2
3 votes
3 votes
0 answers
4
Na462 asked Aug 21, 2018
1,320 views
The maximum number of edges possible with UDG of n nodes,when DFS call on any random node in the graph result in stack size of 5. i.e. 5 function calls present in stack s...