Depth First Search

Question

Please someone explain ....

A directed graph G is acyclic iff depth first search of G yields no back edges

Answer 1

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/