Finding length of shortest cycle in undirected graph

Viewed 25700

I tried the following :

1) DFS, keeping track of level of each vertex in my DFS tree

2) Each time a back edge (x,y) is seen, I calculate cycle length = level[x] - level[y] + 1, and save it if it is smaller than the shortest

Can someone tell a counter example for which this approach is wrong ?

What could be a better way to find shortest cycle in undirected graphs ?

Thanks.

3 Answers
Related