सी ++ प्रोग्राम द्विदलीय ग्राफ़ पर ग्राफ़ रंग प्रदर्शन करने के लिए

एक द्विदलीय ग्राफ एक ग्राफ है जिसमें यदि दो रंगों का उपयोग करके ग्राफ को रंगना संभव है, समुच्चय के शीर्षों को एक ही रंग से रंगा जाता है। इस कार्यक्रम में हम इनपुट के रूप में एक द्विदलीय ग्राफ लेते हैं और शीर्षों को रंगने के बाद प्रत्येक शीर्ष के रंगों को आउटपुट करते हैं।

एल्गोरिदम

Begin
   BFS algorithm is used to traverse all the vertices.
   Take a vertex and colour it yellow.
   Colour all its neighbour vertices as blue.
   Colour the next level vertices as yellow and so, until all vertices are coloured.
End.

उदाहरण कोड

#include<bits/stdc++.h>
using namespace std;
int n, e, i, j;
vector<vector<int> > g;
vector<int> color;
bool v[11101];
void c(int node,int n) {
   queue<int> q;
   if(v[node])
      return;
   color[node]=n;
   v[node]=1;
   for(i=0;i<n;i++) {
      if(!v[g[node][i]]) {
         q.push(g[node][i]);
      }
   }
   while(!q.empty()) {
      c(q.front(),(n+1)%2);
      q.pop();
   }
   return;
}
int main() {
   int a,b;
   cout<<"Enter number of vertices and edges respectively:";
   cin>>n>>e;
   cout<<"'Y' is for Yellow Colour and 'B' is for Blue Colour.";
   cout<<"\n";
   g.resize(n);
   color.resize(n);
   memset(v,0,sizeof(v));
   for(i=0;i<e;i++) {
      cout<<"\nEnter edge vertices of edge "<<i+1<<" :";
      cin>>a>>b;
      a--; b--;
      g[a].push_back(b);
      g[b].push_back(a);
   }
   c(0,1);
   for(i=0;i<n;i++) {
      if(color[i])
         cout<<i+1<<" "<<'Y'<<"\n";
      else
         cout<<i+1<<" "<<'B'<<"\n";
   }
}

आउटपुट

Enter number of vertices and edges respectively:4 3
'Y' is for Yellow Colour and 'B' is for Blue Colour.

Enter edge vertices of edge 1 :1 2
Enter edge vertices of edge 2 :3 2
Enter edge vertices of edge 3 :4 2
1 Y
2 B
3 B
4 B