C++ प्रोग्राम ग्राफ में एक अच्छा फीडबैक एज सेट खोजने के लिए

इस प्रोग्राम में हम मूल रूप से एक फीडबैक आर्क सेट ढूंढते हैं जिसमें ऐसे एजेस होते हैं जिन्हें ग्राफ से हटाने पर, ग्राफ डायरेक्टेड एसाइक्लिक ग्राफ (DAG) बन जाता है।

एल्गोरिदम

checkCG(int n) फंक्शन जांचता है कि ग्राफ DAG है या नहीं। यह वर्टेक्सेस को प्रोसेस करता है और साइकल्स का पता लगाता है।

C++ कार्यान्वयन

#include <iostream>
using namespace std;

int c = 0;
struct AdjList {
    int dest;
    AdjList *next;
} *np = NULL, *np1 = NULL, *p = NULL, *q = NULL;

struct Graph {
    int v;
    AdjList *ptr;
} arr[6];

void addRevEdge(int src, int dest) {
    np1 = new AdjList;
    np1->dest = src;
    np1->next = NULL;
    if (arr[dest].ptr == NULL) {
        arr[dest].ptr = np1;
        q = arr[dest].ptr;
        q->next = NULL;
    } else {
        q = arr[dest].ptr;
        while (q->next != NULL) q = q->next;
        q->next = np1;
    }
}

void addEdge(int src, int dest) {
    np = new AdjList;
    np->dest = dest;
    np->next = NULL;
    if (arr[src].ptr == NULL) {
        arr[src].ptr = np;
        p = arr[src].ptr;
        p->next = NULL;
    } else {
        p = arr[src].ptr;
        while (p->next != NULL) p = p->next;
        p->next = np;
    }
}

void printGraph(int n) {
    for (int i = 0; i < n; i++) {
        cout << "Adjacency List of " << arr[i].v << ": ";
        while (arr[i].ptr != NULL) {
            cout << arr[i].ptr->dest << " ";
            arr[i].ptr = arr[i].ptr->next;
        }
        cout << endl;
    }
}

int checkCG(int n) {
    int cnt = 0;
    int size = n - 1;
    for (int i = 0; i < n; i++) {
        if (cnt == size) return 0;
        if (arr[i].ptr == NULL) {
            cnt++;
            for (int j = 0; j < n; j++) {
                while (arr[j].ptr != NULL) {
                    if (arr[j].ptr->dest == arr[i].ptr->dest)
                        arr[j].ptr->dest = -1;
                    arr[i].ptr = arr[i].ptr->next;
                }
            }
        }
    }
    cout << "after checking dag";
    int visited[n + 1];
    for (int i = 0; i < n; i++) {
        while (arr[i].ptr != NULL) {
            cout << arr[i].ptr->dest << " ";
            visited[i] = 1;
            for (int j = 0; j < n; j++) {
                while (arr[j].ptr != NULL) {
                    cout << arr[j].ptr->dest << " ";
                    if (visited[arr[j].v] == 1)
                        cout << arr[i].v << " - " << arr[j].v;
                    arr[j].ptr = arr[j].ptr->next;
                }
            }
            arr[i].ptr = arr[i].ptr->next;
        }
        cout << endl;
    }
    return 1;
}

int main() {
    int n = 5;
    cout << "Number of vertices: " << n << endl;
    for (int i = 0; i < n; i++) {
        arr[i].v = i;
        arr[i].ptr = NULL;
    }
    addEdge(1, 2);
    addEdge(2, 1);
    addEdge(0, 1);
    addEdge(2, 3);
    addEdge(2, 0);
    addEdge(5, 4);
    addEdge(4, 2);
    printGraph(n);
    cout << "Feedback arc Set: ";
    if (checkCG(n) == 0) cout << " None";
    return 0;
}

आउटपुट

Number of vertices: 5
Adjacency List of 0: 1
Adjacency List of 1: 2
Adjacency List of 2: 1 3 0
Adjacency List of 3: 
Adjacency List of 4: 2
Feedback arc Set: None

नोट

यह कार्यान्वयन शैक्षिक उद्देश्यों के लिए एक बुनियादी दृष्टिकोण दिखाता है। उत्पादन कोड के लिए, टोपोलॉजिकल सॉर्ट या DFS-आधारित साइकल डिटेक्शन जैसे मानक एल्गोरिदम का उपयोग करें।