CODEWITHSUNDEEP
algorithmgraph
user1048858
user1048858

Reputation: 393

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

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

I am considering to do a Breadth First Search on the graph and trying to label the vertices black and white such that no two vertices labeled with the same color are adjacent.

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

Upvotes: 9

Views: 9045

Answers (3)

KeithB
KeithB

Reputation: 252

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

Upvotes: 0

Mostafizar
Mostafizar

Reputation: 71

It can also be done using DFS and numbering the vertices.

  1. Clock=1
  2. Start with a vertex 's',mark it as "visited" and call Explore(s)

Explore(u)

  1. if u is already "visited", then if (clock-Num[u]) is odd, then there is a odd cycle,

    else mark 'u' as "visited"

  2. Num[u]=clock++;

  3. for all adjacent nodes v of u

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

Upvotes: 0

Petar Ivanov
Petar Ivanov

Reputation: 93030

Your approach is the right one. You can't do better than that.

The reason that works is that if you label the vertices by their depth while doing BFS, then all edges connect either same labels or labels that differ by one. It's clear that if there is an edge connecting the same labels then there is an odd cycle. If not then we can color all odd labels white and all even labels black.

Upvotes: 10

Related Questions