C++ प्रोग्राम: Dominating Set Problem हल करना

यह C++ प्रोग्राम Dominating Set Problem को हल करता है। एक ग्राफ में डोमिनेटिंग सेट वर्टेक्स का एक सबसेट होता है जिसमें ग्राफ का प्रत्येक वर्टेक्स या तो सेट में होता है या सेट के कम से कम एक वर्टेक्स से आसन्न होता है।

एल्गोरिदम

शुरुआत
  1. वर्टेक्स और एज की संख्या इनपुट लें, साथ ही एज के एंडपॉइंट भी।
  2. फंक्शन dominant():
     - वेक्टर Set डिक्लेयर करें।
     - कोई भी एज लें जो वर्टेक्स X और Y को जोड़ता है।
     - X और Y के बीच के एक वर्टेक्स को सेट S में जोड़ें।
     - X से जुड़े सभी एज डिलीट करें।
समाप्ति

उदाहरण कोड

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

vector<vector<int>> graph;
bool visited[10001];
int i, j;

vector<int> dominant(int v, int e) {
    vector<int> domSet;
    
    for (i = 0; i < v; i++) {
        if (!visited[i]) {
            domSet.push_back(i); // वर्टेक्स जोड़ें
            visited[i] = true;
            
            for (j = 0; j < (int)graph[i].size(); j++) {
                if (!visited[graph[i][j]]) {
                    visited[graph[i][j]] = true;
                    break;
                }
            }
        }
    }
    return domSet;
}

int main() {
    int v, e, a, b;
    
    cout << "Enter number of vertices: ";
    cin >> v;
    cout << "Enter number of Edges: ";
    cin >> e;
    
    graph.resize(v);
    memset(visited, 0, sizeof(visited));
    
    for (i = 0; i < e; i++) {
        cout << "Enter the end-points of edge " << i+1 << " : ";
        cin >> a >> b;
        a--; b--; // 0-based indexing
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    vector<int> domSet = dominant(v, e);
    
    cout << "The Dominant Set is:\n";
    for (i = 0; i < (int)domSet.size(); i++)
        cout << domSet[i] + 1 << " "; // 1-based आउटपुट के लिए
    
    return 0;
}

आउटपुट

Enter number of vertices: 7
Enter number of Edges: 6
Enter the end-points of edge 1 : 1 2
Enter the end-points of edge 2 : 2 3
Enter the end-points of edge 3 : 3 4
Enter the end-points of edge 4 : 4 5
Enter the end-points of edge 5 : 6 7
Enter the end-points of edge 6 : 4 5
The Dominant Set is: 1 3 5 6

व्याख्या: यह प्रोग्राम एक लालची दृष्टिकोण (greedy approach) का उपयोग करता है। यह अनविजिटेड वर्टेक्स को डोमिनेटिंग सेट में जोड़ता है और उसके सभी पड़ोसियों को विजिटेड मार्क कर देता है। ध्यान दें कि यह एक सन्निकटन एल्गोरिदम है क्योंकि Dominating Set Problem NP-Complete है।