Question: Detect cycle in a directed graph
Answer:
Depth First Traversal can be used to detect 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 (selfloop) or one of its ancestor in the tree produced by DFS.
The idea is to do DFS of given graph and while doing traversal, assign one of the below three colors to every vertex.
WHITE : Vertex is not processed yet. Initially all vertices are WHITE. GRAY : Vertex is being processed (DFS for this vertex has started, but not finished which means that all descendants (ind DFS tree) of this vertex are not processed yet (or this vertex is in function call stack) BLACK : Vertex and all its descendants are processed. While doing DFS, if we encounter an edge from current vertex to a GRAY vertex, then this edge is back edge and hence there is a cycle. https://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/