C++-এ বাইপার্টাইট গ্রাফে গ্রাফ কালারিং (দুই রঙে)

বাইপার্টাইট গ্রাফ (Bipartite Graph) হলো এমন একটি গ্রাফ যার ভার্টেক্সগুলো দুটি ডিজজয়েন্ট সেটে ভাগ করা যায় যাতে প্রতিটি এজ দুটি সেটের নোডের সাথে থাকে। এই গ্রাফগুলো দুই রঙে (2-colorable) কালার করা সম্ভব — একই সেটের নোডগুলো একই রঙ পাবে।

এলগরিদম (BFS-ভিত্তিক)

শুরু
  BFS অ্যালগরিদম ব্যবহার করে সব ভার্টেক্স ট্রাভার্স করুন
  একটি ভার্টেক্স নিন এবং ইয়েলো (Yellow) রঙ দিন
  এর সব নেইবhour কে ব্লু (Blue) রঙ দিন
  পরবর্তী লেভেলের ভার্টেক্সগুলো আবার ইয়েলো, তারপর ব্লু — এভাবে চলুন
  যতক্ষণ সব ভার্টেক্স কালার না হয়
শেষ

উদাহরণ কোড

#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 col) {
    queue<int> q;
    if (v[node]) return;
    color[node] = col;
    v[node] = 1;

    for (i = 0; i < (int)g[node].size(); i++) {
        if (!v[g[node][i]])
            q.push(g[node][i]);
    }

    while (!q.empty()) {
        c(q.front(), (col + 1) % 2);  // অল্টারনেট কালার: 0/1
        q.pop();
    }
}

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.\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);  // নোড ০ থেকে শুরু, কালার ১ (Yellow)

    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

দ্রষ্টব্য: এই কোডে BFS-র বদলে রিকার্সিভ DFS-র মিশ্রণ ব্যবহার করা হয়েছে (কিউ আছে কিন্তু রিকার্সিভ কলও)। বাইপার্টাইট চেক করতে হলে কালারিং সময় কনফ্লিক্ট (একই রঙের নেইবhour) পাওয়া গেলে গ্রাফ বাইপার্টাইট নয়। আধুনিক কোডে vector<int> color(n, -1) এবং ইটারেটিভ BFS ব্যবহার করা ভালো।