The Gateway to Computer Science Excellence
+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?

in Algorithms by (131 points) | 400 views

1 Answer

+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.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,648 questions
56,459 answers
195,335 comments
100,190 users