Bipartite Graph with BFS

"In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V (that is, U and V are each independent sets) such that every edge connects a vertex in U to one in V . Vertex sets U and V are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles."

#include <stdio.h>
#include <iostream>
#include <queue>
using namespace std;

class CheckwhetheragivengraphisBipartiteornot
{
    const static int V = 4;
    bool isBipartite(int G[][V], int src)
    {
        int colors[V]; //there are V vertices in total
        fill(colors, colors+V, -1);

        colors[src] = 1;

        queue<int> qu;
        qu.push(src);
        while (qu.size())
        {
            int u = qu.front();
            qu.pop();

            for (int v = 0; v < V; v++)//check each col in the same row
            {
                if (G[u][v] && colors[v] == -1)
                {
                    colors[v] = 1 - colors[u];
                    qu.push(v); //push vertex for later check
                }
                else if (G[u][v] && colors[v] == colors[u]) return false;
            }
        }
        return true;
    }
public:
    int main()
    {
        int G[][V] = 
        {
            {0, 1, 0, 1},
            {1, 0, 1, 0},
            {0, 1, 0, 1},
            {1, 0, 1, 0}
        };

        isBipartite(G, 0) ? cout << "Yes" : cout << "No";
    }
};
  • for better understand: if we have (0,1) (1,2) (2,0) an odd cycle, we initialized color[0] = 1 -> color[1]=1-1=0 -> color[2]=1-0=1 -> color[2]==color[0]=1 fails the cond G[u][v] && colors[v] == colors[u] return false

REF:

results matching ""

    No results matching ""