C++ प्रोग्राम: बाइनरी खोज का उपयोग करके ग्राफ के न्यूनतम वर्टेक्स कवर आकार को खोजना

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

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

उदाहरण के लिए, ग्राफ लें

2 ---- 4 ---- 6
|      |     |
|      |     |
3 ---- 5

यहां, न्यूनतम वर्टेक्स कवर में शीर्ष 3 और 4 शामिल हैं। ग्राफ के सभी किनारे ग्राफ के शीर्ष 3 या 4 पर आपतित हैं।

उदाहरण

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

// ग्राफ को संग्रहीत करने के लिए एरे
bool arr[max][max];

// जांचें कि क्या न्यूनतम वर्टेक्स कवर मौजूद है
bool check_cover(int V, int k, int E) {
    int set = (1 << k) - 1;
    int limit = (1 << V);
    // आकार 'k' के किनारों को चिह्नित करने के लिए
    bool vis[max][max];
    while (set < limit) {
        // प्रत्येक पुनरावृत्ति के लिए वर्टेक्स कवर रीसेट करना
        memset(vis, 0, sizeof vis);
        int count = 0;
        // उन मानों की जांच करना जिनका मान उच्च है
        for (int j = 1, v = 1; j < limit; j = j << 1, v++) {
            if (set & j) {
                // किनारों को विजिटेड मार्क करना
                for (int k = 1; k <= V; k++) {
                    if (arr[v][k] && !vis[v][k]) {
                        vis[v][k] = 1;
                        vis[k][v] = 1;
                        count++;
                    }
                }
            }
        }
        // यदि सभी किनारे कवर हैं
        if (count == E)
            return true;
        int c = set & -set;
        int r = set + c;
        set = (((r ^ set) >> 2) / c) | r;
    }
    return false;
}

// न्यूनतम वर्टेक्स कवर खोजने के लिए
int find_cover(int n, int m) {
    // बाइनरी खोज करना
    int left = 1, right = n;
    while (right > left) {
        int mid = (left + right) >> 1;
        if (check_cover(n, mid, m) == false)
            left = mid + 1;
        else
            right = mid;
    }
    return left;
}

// ग्राफ में किनारा डालने के लिए
void add_edge(int u, int v) {
    arr[u][v] = 1;
    arr[v][u] = 1;
}

int main() {
    memset(arr, 0, sizeof arr);
    int V = 6, E = 5;
    add_edge(2, 3);
    add_edge(2, 4);
    add_edge(3, 5);
    add_edge(4, 5);
    add_edge(4, 6);
    cout << "Size of Minimum Vertex Cover : " << find_cover(V, E) << endl;
    return 0;
}

आउटपुट

Size of Minimum Vertex Cover : 2