Menu
Given an undirected graph G=(V, E) with n vertices (|V| = n), how do you find if it contains a cycle in O(n)?
543
Here for finding the number of cycles in the undirected graph, the time complexity is the same as DFS traversal, i.e., O(V+E), where V is the number of vertices and E is the number of edges in the graph. Space complexity is O(V) as extra color[ ] and par[ ] is used here.
An undirected graph is acyclic (i.e., a forest) if a DFS yields no back edges. Since back edges are those edges ( u , v ) connecting a vertex u to an ancestor v in a depth-first tree, so no back edges means there are only tree edges, so there is no cycle.
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 joining a node to itself (self-loop) or one of its ancestor in the tree produced by DFS.
Insert the edges into an adjacency list. Call the DFS function which uses the coloring method to mark the vertex. Whenever there is a partially visited vertex, backtrack till the current vertex is reached and mark all of them with cycle numbers. Once all the vertexes are marked, increase the cycle number.
I think that depth first search solves it. If an unexplored edge leads to a node visited before, then the graph contains a cycle. This condition also makes it O(n), since you can explore maximum n edges without setting it to true or being left with no unexplored edges.
142
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
