The Gateway to Computer Science Excellence

+1 vote

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?

+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).

52,345 questions

60,498 answers

201,865 comments

95,323 users