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 full binary tree is also a complete binary tree.
D. None of the above
Solution :
B) is correct.
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 ancestors in the tree produced by DFS.
