Introduction
Graphs are of two kinds on the basis of the way edges are directed. In Undirected graph all the edges go forward as well as backward between two vertices. In Directed graph edges between two vertices are directional.
Algorithm For Detecting Cycle
To detect cycles using DFS, use two colors in a undirected graph and three colors in directed graph. A node is in one of three states during DFS traversal
- Before being visited i.e. initial state
- During recursively visiting its descendants
- After all its descendants have been visited (returning to its parent, i.e., wrap-up phase).
Three colors correspond to each of the three states i.e. before being visited, during recursively visiting its descendants, and after all its descendants have been visited (returning to its parent). In a directed graph, a cycle is present if and only if a node is seen again before all its descendants have been visited. If a node has a neighbor which is grey, then there is a cycle. A grey node means we are currently exploring its descendants. So, for cycle detection in directed graphs requires three colors, while undirected graphs requires two colors. 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 all descendants of this vertex are not processed yet.
- 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.
Example
Consider a graph G, with 3 vertices – A, B, C with directed edges as A->B, B->C, A->C to check for the existence of cycles in case of a directed graph. Suppose the DFS starts at A, then visits B, and then C. When DFS has returned to A, it then checks that C as already been visited and is black. But there is no cycle in the graph. In an undirected graph, if the node under consideration has a black or grey neighbor, it indicates a cycle (and the DFS does not visit further). In this example if G is undirected, then G has cycle. For every visited vertex ‘A’ in DFS traversal, if there is an adjacent ‘B’ such that B is already visited and B is not parent of A, then there is a cycle in graph.