determine if undirected graph has cycle/s

[chickenandfries]

Is there an algorithm in determining whether an undirected graph has cycle/s? I've tried implementing Aho's suggestion of looking for cross edges in the breadth-first forest/tree of the graph but it doesn't seem to work. Also, if the graph has a cycle, how do I determine that cycle?

[chickenandfries]

I'm done with determining if the graph has cycle/s. I checked the depth-first tree/forest for back edge/s. My problem now is to list this cycle.

[chickenandfries]

Done it! Just walk through the depth-first tree/forest starting from the back edge.

[Saeven]

Also easy in a digraph, just map the edges into a vertex adjacency matrix, and check for Weisstein's conjecture, which has that:

For each n = 1,2,3, … , the number of acyclic directed graphs with n labeled vertices is equal to the number of n x n matrices of 0's and 1's whose eigenvalues are positive real numbers

This can be computed very quickly, and is a great way to do things on a huge graph (walking and checking can be a killer).

[sinchoss]

which data representation did you use? adjacency matrix or adjaceny list?
which one leads a faster algorithm?

[ishaypeled]

Best, easiest, simplest method to find (not track down) a cycle in an undirected graph is to count the number of vertices (|V|) and the number of edges (|E|), if |E| > |V|-1 the graph contains at least one cycle (interesting to note that if |E| = |V|-1 then the graph has precisely one MST, the graph itself).