Given a undirected graph with "v" vertices (0 to v-1), check whether the graph contains a cycle or not.
Solutions
Method 1: Using BFS
If the graph is disconnected, then call the function for individual trees (start from each non-visited node).
Start traversing the graph in a BFS manner and keep track of visited nodes in visited[] array.
Also, keep track of the prev (parent) node; if any already visited node is found that is not the parent node, a cycle is detected.
This is because in an undirected graph we consider adjacent in both directions, and so for any node in a non-cyclic graph, there should be only one visited adjacent node (parent node).
Complexity
The time complexity of this solution is O(v+e) and space complexity is O(v).
Method 2: Using DFS
If the graph is disconnected, then call the function for individual trees (start from each non-visited node).
Start traversing the graph in a DFS manner and keep track of visited nodes in visited[] array.
Also, keep track of the prev (parent) node; if any already visited node is found that is not the parent node, a cycle is detected.
This is because in an undirected graph we consider adjacent in both directions, and so for any node in a non-cyclic graph, there should be only one visited adjacent node (parent node).
Complexity
The time complexity of this solution is O(v+e) and space complexity is O(v).