BFS를 사용하여 그래프가 이분법인지 확인하는 C++ 프로그램

이분 그래프는 두 가지 색상을 사용하여 그래프 채색이 가능한 그래프입니다. 세트의 꼭짓점은 같은 색으로 지정됩니다. BFS를 사용하여 그래프의 이분화 여부를 확인하는 C++ 프로그램입니다.

알고리즘

Begin
   Function Bipartite():
   1) Assign a color to the source vertex
   2) Color all the neighbors with another color except first one color.
   3) Color all neighbor’s neighbor with First color.
   4) Like this way, assign color to all vertices such that it satisfies all the constraints of k way coloring problem where k = 2.
   5) While assigning colors, if we find a neighbor which is colored with same color as current vertex, then the graph cannot be colored with 2 vertices i.e.; graph is not Bipartite
End

예시

#include <iostream>
#include <queue>
#define V 5
using namespace std;
bool Bipartite(int G[][V], int s) {
   int colorA[V];
   for (int i = 0; i < V; ++i)
   colorA[i] = -1;
   colorA[s] = 1; //Assign a color to the source vertex
   queue <int> q; //Create a queue of vertex numbers and enqueue source vertex for BFS traversal
   q.push(s);
   while (!q.empty()) {
      int w = q.front(); //dequeue a vertex
      q.pop();
      for (int v = 0; v < V; ++v) //Find all non-colored adjacent vertices {
         if (G[w][v] && colorA[v] == -1) //An edge from w to v exists and destination v is not colored {
            colorA[v] = 1 - colorA[w]; //Assign alternate color to this adjacent v of w
            q.push(v);
         } else if (G[w][v] && colorA[v] == colorA[w]) //An edge from w to v exists and destination
            //v is colored with same color as u
            return false;
      }
   }
   return true; //if all adjacent vertices can be colored with alternate color
}
int main() {
   int G[][V] = {{ 0, 1, 0, 0},
                { 1, 0, 0, 0},
                { 0, 0, 0, 1},
                { 1, 0, 1, 0}};
   if (Bipartite(G, 0))
      cout << "The Graph is Bipartite"<<endl;
   else
      cout << "The Graph is Not Bipartite"<<endl;
   return 0;
}

출력

The Graph is Bipartite