+1 vote
400 views

Which of the following condition is sufficient to detect cycle in a directed graph?
(A) There is an edge from currently being visited node to an already visited node.
(B) There is an edge from currently being visited node to an ancestor of currently visited node in DFS forest.
(C) Every node is seen twice in DFS.
(D) None of the bove

here option B is right, but why not option A?

| 400 views

+1 vote

Depth First Traversal can be used to detect a cycle in a Graph. DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. A back edge is an edge that is from a node to itself (self-loop) or one of its ancestor in the tree produced by DFS.

For a disconnected graph, we get the DFS forest as output. To detect cycle, we can check for a cycle in individual trees by checking back edges.

To detect a back edge, we can keep track of vertices currently in recursion stack of function for DFS traversal. If we reach a vertex that is already in the recursion stack, then there is a cycle in the tree. The edge that connects current vertex to the vertex in the recursion stack is a back edge.

Time Complexity of this method is the same as time complexity of DFS traversal which is O(V+E).

by Active (4.7k points)
0
you have explained why B is right, but please explain why A is wrong
0
Because that is maybe not guaranteed.