CODEWITHSUNDEEP
c++algorithmgraphcyclebreadth-first-search
odbhut.shei.chhele
odbhut.shei.chhele

Reputation: 6254

What is odd length cycle and how can I know if there is an odd cycle in my graph?

I am new to graph theory. Suppose there is a connected and undirected graph. I want to know if there is an odd length cycle in it. I can find if there is an cycle in my graph using BFS. I haven't learnt DFS yet. Here is my code which just finds if there is a cycle or not. Thanks in advance.

#include<iostream>
#include<vector>
#include<queue>
#include<cstdio>
#define max 1000

using namespace std;

bool find_cycle(vector<int> adjacency_list[]);

int main(void)
{
     freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);

int vertex, edge;
vector<int> adjacency_list[max];

cin >> vertex >> edge;

//Creating the adjacency list
for(int i=1; i<=edge; i++)
{
    int n1, n2;
    cin >> n1 >> n2;

    adjacency_list[n1].push_back(n2);
    adjacency_list[n2].push_back(n1);
}

if(find_cycle(adjacency_list))
    cout << "There is a cycle in the graph" << endl;
else cout << "There is no cycle in the graph" << endl;

return 0;
}

bool find_cycle(vector<int> adjacency_list[])
{
queue<int> q;
bool taken[max]= {false};
int parent[max];

q.push(1);
taken[1]=true;
parent[1]=1;

//breadth first search
while(!q.empty())
{
    int u=q.front();
    q.pop();

    for(int i=0; i<adjacency_list[u].size(); i++)
    {
        int v=adjacency_list[u][i];

        if(!taken[v])
        {
            q.push(v);
            taken[v]=true;
            parent[v]=u;
        }
        else if(v!=parent[u]) return true;
    }
}

return false;
}

Upvotes: 0

Views: 2622

Answers (1)

anonymous
anonymous

Reputation: 201

The property "2-colorable" is also termed "bipartite". Whether you use DFS or BFS shouldn't matter in this case; as you visit the graph's nodes, label them 0 / 1 alternatively, depending on the color of the neighbor you came from. If you find a node which is already labelled, but labelled differently than you would label it when visiting, there is a cycle of odd length. If no such node occurs, there is no cycle of odd length.

Upvotes: 3

Related Questions