Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction📌
2.
What is a Graph?📌
2.1.
Applications of a Graph🎯
3.
What is a Cycle in a Graph?🤷‍♀️🤷‍♀️
4.
Brief of the Problem❓
5.
Odd Length Cycles in a Graph⭕
5.1.
Bipartite Graph
5.1.1.
Visual Representation⭕
6.
Algorithm to Check for Odd Length Cycle in a Graph❗
6.1.
Steps to Construct a Bipartite Graph
6.2.
Code for Detection of Odd Length Cycle in C++💻
6.2.1.
Sample Input
6.2.2.
Output
6.3.
Code for Detection of Odd Length Cycle in Java💻
6.3.1.
Sample Input
6.3.2.
Output
7.
Frequently Asked Questions
7.1.
What is an odd length cycle?
7.2.
What is a Bipartite Graph in terms of Colouring?
7.3.
What is meant by the n cycle graph?
7.4.
Can spanning trees have cycles?
7.5.
Is a bipartite graph always connected?
8.
Conclusion
Last Updated: Mar 27, 2024
Medium

Check if a Graph has a Cycle of Odd Length

Author Akriti Bhan
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction📌

Graph of odd length cycle

This blog will cover everything right from what are graphs, and cycles in a graph, to how we can check whether a graph has a cycle of odd length or not in a straightforward manner.

Let us now straightaway dive deeper into the topic.

What is a Graph?📌

A graph is a non-linear data structure that consists of two non-empty sets of vertices and edges. The vertices are also known as nodes.

Applications of a Graph🎯

Here, we will discuss the applications of a graph data structure in our daily lives.

➡️Graphs used in social networks.

➡️We use graphs in google maps.

➡️We use graphs in the operating system.

 

Graph

In the above-mentioned graph, set of vertices V={1,2,3,4,5} and set of edges E={12,25,54,43,24}

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

What is a Cycle in a Graph?🤷‍♀️🤷‍♀️

To understand a cycle in a graph, we must first know what a trail is. 

trail is a path covering the vertices joined through edges. In this, we try to traverse every edge only once.

Coming back to the point, a cycle in a graph is a non-empty trail in which the first and the last vertices are the same.

The graphs containing cycles are known as cyclic graphs.

E.g., let us take a directed graph.

Graph example

In the above graph, a trail from 1->2->3->4->5->1 is a closed trail as the end vertices are the same. Therefore this is a cyclic graph. 

Brief of the Problem

Given a graph, we have to check whether a graph has a cycle of odd length.

We will be given a graph, it can be a graph of any type.

We will apply specific concepts to check whether the provided graph has a cycle of odd length using the technique of looking for a bipartite graph.

Odd Length Cycles in a Graph

We will detect whether a graph has a cycle of odd length or not in a somewhat more straightforward manner.

The idea is simple to think about. We use the concept of bipartite graphs for the same.

Bipartite Graph

In technical terms, a bipartite graph is a graph whose vertex set can be divided into two non-empty disjoint sets, for instance, A and B, such that a vertex in A is connected to a vertex in B, or we can also say that no two vertices of the same set are connected.

An important characteristic of a bipartite graph is that it does not contain an odd length cycle.

This will be a major point in determining if the graph has a cycle of odd length.
 

Visual Representation⭕

Let us assume that A and B are two non-empty disjoint sets containing vertices of graph G and that graph G is a bipartite graph.

 

Bipartite graph example using sets

Suppose we connect first edge 1 from a1 to b1. This brings the cycle to set B. Retaking the second edge brings the cycle to set A.

Now since this has to be a cycle, we have to bring the cycle from where it started.

Therefore, the figure will look somewhat like this-

Bipartite graph example using sets

This shows that if a graph is bipartite, then it cannot contain an odd length cycle.

Algorithm to Check for Odd Length Cycle in a Graph

For detecting the odd length cycle in a graph we basically check for the fact that is the graph bipartite or not. The algorithm for this is given below.

Steps to Construct a Bipartite Graph

1️⃣Choose a vertex  aand set B0={a0}

2️⃣Let C0 be the set of vertices that are adjacent to a0.

3️⃣Let Bk be the set of vertices that are adjacent to vertex Ck-1 and are not chosen.

4️⃣Let Ck be the set of vertices that are adjacent to the vertex Bk-1 and are not chosen.

5️⃣Repeat steps 3 and 4 till all vertices are covered.

6️⃣Finally when all the vertices are chosen, B=B0 U BU B2….. and C=CU C1 U C2

Code for Detection of Odd Length Cycle in C++💻

#include <bits/stdc++.h>
#define V 4
using namespace std;
/*We have defined a graph G[V][V]
function isOddCycle gives true value if the Graph has a cycle of odd length*/
bool isOddCycle(int G[][V], int source)
{
    /*create an array named colourArray. In this
    we will store the colours that are assigned to each         vertex.*/
    /*The indices of the array will be the vertex number.
    If no colour is assigned to a vertex at ith position, its*/
    //value will be -1
   
    int colourArray[V];
    for (int i = 0; i < V; ++i)
        colourArray[i] = -1;// no colour assigned initially
    //starting with the source vertex
    colourArray[source] = 1;
    //creating a queue to push vertices for BFS
    queue <int> q;
    q.push(source); //start by pushing the source

    //will run till queue is not empty
    while (!q.empty())
    {
   
        int vertex = q.front();
        q.pop();

        // Return true if there is a self-loop
        if (G[vertex][vertex] == 1)
        return true;
        // notcol finds the non-coloured vertices
        for (int notcol = 0; notcol < V; ++notcol)
        {
            /* An edge from vertex to notcol exists and destination
             notcol is not assigned any colour*/
            if (G[vertex][notcol] && colourArray[notcol] == -1)
            {
                //assigning a different colour
                colourArray[notcol] = 1 - colourArray[vertex];
                q.push(notcol);
            }
            /* An edge from vertex to notcol exists and destination
            notcol is of same colour as vertex*/
            else if (G[vertex][notcol] && colourArray[notcol] == colourArray[vertex])
                return true;
        }
    }
    /*therefore all vertices can be coloured using alternating colours*/
    return false;
}
int main()
{
    //making a graph
    int G[][V] = {{0, 0, 0, 1},
        {1, 0, 0, 1},
        {0, 1, 1, 1},
        {1, 0, 1, 0}
    };
    isOddCycle(G, 0) ? cout << "Odd cycle is present" : cout << "Odd cycle is not present";
    return 0;
}

Sample Input

int G[][V] = {{0, 0, 0, 1},
        {1, 0, 0, 1},
        {0, 1, 1, 1},
        {1, 0, 1, 0}
    };

Output

Output for C++ code

Code for Detection of Odd Length Cycle in Java💻

import java.util.*;
class codegraph2 {
    public static int V =4;
    /*this is a boolean function and returns true if the Graph has a cycle of odd length, else returns false*/

    public static boolean isOddCycle(int G[][], int source)
    {
        /*create an array named colourArray. In this
        we will store the colours that are assigned to each vertex.
         The indices of the array will be the vertex number.
        If no colour is assigned to a vertex at ith position, its
        value will be -1*/


        int colourArray[] = new int[V];
        for (int i = 0; i < V; ++i)
            colourArray[i] = -1;
   
        //starting with the source
        colourArray[source] = 1;
   
        //create a queue and keep on adding vertices for BFS
        LinkedList<Integer> q = new LinkedList<Integer>();
        q.add(source); //start by enqueuing the source vertex
   
        //run till the queue is empty
        while (!q.isEmpty())
        {
            // Dequeue a vertex from queue
            int vertex = q.peek();
            q.pop();
            if (G[vertex][vertex] == 1)
            return true;
   
            /*finding all the adjacent vertices that are not coloured*/
            for (int notcol = 0; notcol < V; ++notcol)
            {
                /*An edge from vertex to u exists and
                notcol is not coloured*/
                if (G[vertex][notcol] == 1 && colourArray[notcol] == -1)
                {
                    colourArray[notcol] = 1 - colourArray[vertex];
                    q.push(notcol);
                }
   
                 /*An edge from vertex to notcol exists and
                 notcol is coloured same as vertex*/
                else if (G[vertex][notcol] == 1 && colourArray[notcol] ==
                                        colourArray[vertex])
                    return true;
            }
        }
        /*therefore all adjacent vertices are coloured with alternate colours*/
        return false;
    }
    public static void main(String[] args)
    {
        int G[][] = {{0, 0, 1, 1},
                    {1, 0, 1, 0},
                    {1, 0, 0, 1},
                    {1, 1, 1, 0}};    
        if (isOddCycle(G, 0))
            System.out.println("Odd cycle is present") ;
            else
                System.out.println("Odd cycle is not present ");}}
 

Sample Input

int G[][] = {{0, 0, 1, 1},
                    {1, 0, 1, 0},
                    {1, 0, 0, 1},
                    {1, 1, 1, 0}};

Output

Output for Java code


Check out this problem - No of Spanning Trees in a Graph

Frequently Asked Questions

What is an odd length cycle?

An odd-length cycle is a cycle in a graph with an odd number of vertices in it.

What is a Bipartite Graph in terms of Colouring?

A bipartite graph is a graph that has no two adjacent vertices of the same colour.

What is meant by the n cycle graph?

An n cycle graph means that the graph cycle has n vertices and n edges.

Can spanning trees have cycles?

No, spanning trees cannot have cycles. Cycles are only present in graphs.

Is a bipartite graph always connected?

No, the bipartite graph doesn't need to be constantly connected. A graph with no edges is also a bipartite graph.

Conclusion

In this blog, we have discussed graphs and pondered upon a graph's cycles. This blog also discusses how we can determine if there is an odd length cycle in a given graph.

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available.

You can refer to other similar articles as well-

Happy Learning Ninja! 🥷

Previous article
Detect cycle in a directed graph using colors
Next article
Maximum Bipartite Matching in Graph
Live masterclass