C++ প্রোগ্রাম: গ্রাফের এজ কালারিং (Edge Coloring of a Graph)

এই প্রোগ্রামে আমরা গ্রাফের এজ কালারিং করব যাতে দুটি আডজাসেন্ট এজে একই রঙ না থাকে।

অ্যালগরিদম

Begin
    ভার্টেক্স সংখ্যা 'n' এবং এজ সংখ্যা 'e' ইনপুট নিন।
    গ্রাফ অ্যাডজেসেন্সি লিস্ট হিসেবে সংরক্ষণ করুন।
    BFS ব্যবহার করে কিউ দিয়ে প্রতিটি এজে রঙ অ্যাসাইন করুন।
End

উদাহরণ

#include <bits/stdc++.h>
using namespace std;

int n, e, i, j;
vector>> g;
vector color;
bool v[111001];

void col(int n) {
    queue q;
    int c = 0;
    set vertex_colored;
    if(v[n]) return;
    v[n] = 1;
    for(i = 0; i < g[n].size(); i++) {
        if(color[g[n][i].second] != -1)
            vertex_colored.insert(color[g[n][i].second]);
    }
    for(i = 0; i < g[n].size(); i++) {
        if(!v[g[n][i].first])
            q.push(g[n][i].first);
        if(color[g[n][i].second] == -1) {
            while(vertex_colored.find(c) != vertex_colored.end())
                c++;
            color[g[n][i].second] = c;
            vertex_colored.insert(c);
            c++;
        }
    }
    while(!q.empty()) {
        int temp = q.front();
        q.pop();
        col(temp);
    }
    return;
}

int main() {
    int u, w;
    set empty;
    cout << "Enter number of vertices and edges respectively:";
    cin >> n >> e;
    cout << "\n";
    g.resize(n);
    color.resize(e, -1);
    memset(v, 0, sizeof(v));
    for(i = 0; i < e; i++) {
        cout << "\nEnter edge vertices of edge " << i+1 << " :\n";
        cin >> u >> w;
        u--; w--;
        g[u].push_back(make_pair(w, i));
        g[w].push_back(make_pair(u, i));
    }
    col(0);
    for(i = 0; i < e; i++)
        cout << "Edge " << i+1 << " is coloured with colour " << color[i]+1 << "\n";
    return 0;
}

আউটপুট

Enter number of vertices and edges respectively:4 5
Enter edge vertices of edge 1 :1 2
Enter edge vertices of edge 2 :2 3
Enter edge vertices of edge 3 :1 1
Enter edge vertices of edge 4 :3 4
Enter edge vertices of edge 5 :1 4
Edge 1 is coloured with colour 1
Edge 2 is coloured with colour 2
Edge 3 is coloured with colour 2
Edge 4 is coloured with colour 1
Edge 5 is coloured with colour 3