Geek Answers Handbook

How to check if an undirected graph has an odd length cycle

I am trying to find the O (| V | + | E |) time algorithm to check if a connected unoriented graph has an odd-length cycle or not.

I am considering the possibility of doing the first search on a graph and trying to identify the vertices of black and white, so that the two vertices marked with the same color are adjacent.

Is there any known lead algorithm to solve this problem in linear time?

+8
algorithm graph
source share
3 answers

Your approach is correct. You cannot do it better.

The reason it works is that if you mark the vertices with their depth during the execution of the BFS, then all the edges connect the same marks or marks that are different from each other. It is clear that if there is an edge connecting the same labels, then there is an odd cycle. If not, then we can color all the odd labels white, and all the even labels black.

+9
source share

This can also be done using DFS and vertex numbering.

  • Clock = 1
  • Start at the top of 's', mark it as “visited” and call “Explore (s)

Explore (s)

  • if u is already “visited”, then if (clock-Num [u]) is odd, then there is an odd cycle,

    else mark 'u' as "visited"

  • Num [and] = hours ++;

  • for all adjacent nodes v from u

    i) Explore(v) ii) clock=Num[u]
0
source share

In initialization, you also need to set Num [s] = 0.

0
source share

More articles:


All Articles