C++ में बायपार्टाइट ग्राफ पर ग्राफ कलरिंग करना

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

एल्गोरिदम

Begin
    BFS एल्गोरिदम का उपयोग सभी वर्टेक्स को ट्रैवर्स करने के लिए किया जाता है।
    एक वर्टेक्स लें और उसे पीला रंग दें।
    उसके सभी पड़ोसी वर्टेक्स को नीला रंग दें।
    अगले स्तर के वर्टेक्स को पीला रंग दें और इसी तरह, जब तक सभी वर्टेक्स कलर न हो जाएं।
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";
    }
    return 0;
}

आउटपुट

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