30 views

Give an algorithm that determines whether or not a given undirected graph G=(V,E) contains a cycle. Your algorithm should run in $O(V)$ time, independent of E.

Solution:

If there’s a back edge, there’s a cycle. If there’s no back edge, there are only tree edges.  Hence, the graph is acyclic.
Thus, we can run DFS: if we find a back edge, there’s a cycle.

My doubt is how to manage this in $O(V)$ time ?

| 30 views
+1
0
Already have that. You just give a little explanation about the complexity either from the link you provided or self explanation. Getting little difficulty to get that. Thank you.
+2
In simple terms, undirected connected graph which doesn't have cycles, should be a tree.

For Tree, edges=nodes-1

So, your dfs = O(nodes+edges) =O(2nodes-1)= O(nodes)
0

If we ever see $|V |$ distinct edges, we must have seen a back edge because in an acyclic (undirected) forest, $|E| ≤ |V | − 1$.

@Shaik Masthan

Got it sir, Thankyou