1
$\begingroup$

I am working on an algorithm but there is so much about math that I don't know and I could speed up my algorithm a ton if there was a trick here.

I have a weighted, undirected graph. From this graph I have attained a set of n edges (to, from) where "to" and "from" represent nodes in my graph.

Within this set, every node is represented once and only once as a "to", and once and only once as a "from".

One can probably see that this set will contain at least one cycle.

My question is, what is the fastest way to detect if the set contains only one cycle? That is to say, that the the set of n edges contains a cycle of size n.

I can't come up with anything more efficient than pulling out an edge and then traversing all of it's connections until I have found the length of the first cycle.

Is there something better than this? Thank you.

$\endgroup$
1
  • $\begingroup$ There are very few of us who can claim to have nothing left to learn about maths. I know none. $\endgroup$ Commented Jan 18, 2018 at 18:01

1 Answer 1

1
$\begingroup$

Your algorithm has worst case runtime linear in $n$, which is already pretty fast. Especially when checking that a sequence of edges is in fact a cycle necessarily takes length-of-cycle-many operations, I wouldn't expect any faster without preprocessing.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .