Which of the following statement is correct:

Explanation:

A directed graph G is acyclic (DAG) if and only if a depth-first search of G yields no back edges.

Proof.

1.Direct: Suppose that there is a back edge (u, v). Then vertex v is an ancestor of vertex u in the depth-first forest. There is thus a path from v to u in G, and the back edge (u,v) completes a cycle.

2.Reverse: Suppose that G contains a cycle c. We show that a depth-first search of G yields a back edge. Let v be the first vertex to be discovered in c, and let (u,v) be the preceding edge in c. At time d[v], there is a path of white vertices from v to u. By the white-path theorem, vertex u becomes a descendant of v in the depth-first forest. Therefore (u,v) is a back edge.

Three possible scenarios of edge classification:

Fig. Edge classification with DFS. In the case of scenario (a), the discovery sequence is a, b, d, e, f, c, g, h. When we reach node d from a, we characterize edge (a.d) as a forward edge because d is already discovered (from node b). The same applies for node f. When examining the outgoing edges of e we characterize edge (e,a) as a back edge, since a is already discovered and is an ancestor of e. Edges (c,d), (c,e) are cross edges because d and e are already discovered and have no ancestor-descendant relation with c. The same applies for edges (g,b) and (h,d).