Algorithms and Me: Graphs : Detecting cycle in undirected graph

Problem statement Given an undirected graph, check if there is a cycle in it or not. For example below graph has cycles as 3->6->5->3, 1->4->3->6->2->1 Graph with cycle Analysis Simple definition of a cycle in graph would be : If while traversing graph, we reach at a node which we have already traversed to reach current node, then there is a cycle in graph. How can we detect the above condition? It's simple application of Depth First Search. Do depth first traversal of a graph, if we detect any back edge while traversing, then there is a cycle.

Read full article from Algorithms and Me: Graphs : Detecting cycle in undirected graph