C++ প্রোগ্রাম: হিউরিস্টিক ব্যবহার করে গ্রাফের ভার্টেক্স কভার (Vertex Cover) বের করা

গ্রাফের ভার্টেক্স কভার হলো একটি ভার্টেক্স সেট V খুঁজে বের করা যাতে গ্রাফের প্রতিটি এজ (M, N)-এর জন্য কমপক্ষে M বা N (বা উভয়) V-তে থাকে। এই প্রোগ্রামে হিউরিস্টিক ব্যবহার করে ভার্টেক্স কভার বের করা হয়েছে।

অ্যালগরিদম

Begin
    1) সেট S খালি রাখুন।
    2) সংযুক্ত গ্রাফ থেকে একটি এজ E নিন (M এবং N)।
    3) উভয় ভার্টেক্স S-তে যোগ করুন।
    4) M বা N এন্ডপয়েন্ট সম্পন্ন সকল এজ গ্রাফ থেকে বাদ দিন।
    5) যদি গ্রাফে এজ অবশিষ্ট থাকে, ধাপ ২-এ যান।
    6) চূড়ান্ত সেট S প্রিন্ট করুন যা গ্রাফের ভার্টেক্স কভার।
End

উদাহরণ

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

vector> g;
bool v[11110];
int i, j;

vector sol_vertex(int n, int e) {
    vector S;
    for(i = 0; i < n; i++) {
        if(!v[i]) {
            for(j = 0; j < (int)g[i].size(); j++) {
                if(!v[g[i][j]]) {
                    v[i] = true;
                    v[g[i][j]] = true;
                    break;
                }
            }
        }
    }
    for(i = 0; i < n; i++)
        if(v[i]) S.push_back(i);
    return S;
}

int main() {
    int n, e, a, b;
    cout << "Enter number of vertices:";
    cin >> n;
    cout << "Enter number of Edges:";
    cin >> e;
    g.resize(n);
    memset(v, 0, sizeof(v));
    for(i = 0; i < e; i++) {
        cout << "Enter the end-points of edge " << i+1 << " : ";
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector S = sol_vertex(n, e);
    cout << "The required vertex cover is as follows:\n";
    for(i = 0; i < (int)S.size(); i++)
        cout << S[i]+1 << " ";
    return 0;
}

আউটপুট

Enter number of vertices:4
Enter number of Edges:5
Enter the end-points of edge 1 : 2 1
Enter the end-points of edge 2 : 3 2
Enter the end-points of edge 3 : 4 3
Enter the end-points of edge 4 : 1 4
Enter the end-points of edge 5 : 1 3
The required vertex cover is as follows: 1 2 3 4