bayram's blog

Can anyone solve this problem?
By bayram, 13 years ago, In English

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|.

  • Vote: I like it
  • -17
  • Vote: I do not like it

»
13 years ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

Yes, they can

→ Reply
  • »
    »
    13 years ago, hide # ^ |
     
    Vote: I like it +14 Vote: I do not like it

    To be serious, the algorithm you know using dfs should work in O(V) time. Because until you find a cycle you will try only edges of the tree, so that is O(V).

    Another approach is |E| >= |V| => contains cycle, else O(E) = O(V), so you can do simple algorithm, too.

    → Reply
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Have you tried to google it?

→ Reply
»
13 years ago, hide # |
 
Vote: I like it -7 Vote: I do not like it

If |E| >= |V| graph has a cycle. else you can use dfs. It would be in O(V).

→ Reply
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Thanks everybody!

→ Reply