0

Can you give me an hint how to develop an algorithm as this task? Everytime if I am reading something like this I don't know how to develop with using the run time. Thanks!

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

Sayuri
  • 63
  • 6
  • Can you find what you are searching in: https://stackoverflow.com/questions/12367801/finding-all-cycles-in-undirected-graphs ? – Damien Jan 10 '20 at 10:09
  • Thanks its a helpful content. But I am interested into the way to solve such a problem or in general O(nlogn). How can I create an algorithm with this runtime? Because I don't know how to solve this problem. I mean how to work with runtime and develop the code which cover this. – Sayuri Jan 10 '20 at 10:37
  • For a normal (no multi-edge) connected undirected graph, if number of edges is greater than number of vertices-1, [ e > v-1] then there will be a cycle. – User_67128 Jan 10 '20 at 13:37
  • I doubt if there is any algorithm that should run in O(|V|) unless you can come up with a new technique. The DFS and BFS techniques for detecting cycle both has time complexity is O(V+E). – User_67128 Jan 10 '20 at 14:42

1 Answers1

1

Currently, there aren't algorithms for that problem working with only |V|, obviously, you can conclude some cases for example if |E| >= |V| and every edge is different(different pair) there will be a cycle, but it's not necessary. You can consider also more cases for example when |V| <= 2 or |E| <= 2.

Jakub Swistak
  • 304
  • 3
  • 10