Menu
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?
468
In other words, a cycle is a path with the same first and last vertex. The length of the cycle is the number of edges that it contains, and a cycle is odd if it contains an odd number of edges. Theorem 2.5 A bipartite graph contains no odd cycles.
Depth First Traversal can be used to detect a cycle in a Graph. There is a cycle in a graph only if there is a back edge present in the graph. A back edge is an edge that is indirectly joining a node to itself (self-loop) or one of its ancestors in the tree produced by DFS.
1. Which type of graph has no odd cycle in it? Explanation: The graph is known as Bipartite if the graph does not contain any odd length cycle in it. Odd length cycle means a cycle with the odd number of vertices in it.
Here for finding the number of cycles in the undirected graph, the time complexity is the same as DFS traversal, i.e., O(V+E), where V is the number of vertices and E is the number of edges in the graph.
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.
132
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
