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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,648 questions

56,459 answers

195,335 comments

100,190 users