C++ प्रोग्राम: टोपोलॉजिकल सॉर्ट का उपयोग करके ग्राफ में साइकिल चेक करें

एक डायरेक्टेड एसाइक्लिक ग्राफ में, हम वर्टेक्स को टोपोलॉजिकल सॉर्ट का उपयोग करके लीनियर ऑर्डर में सॉर्ट कर सकते हैं।

टोपोलॉजिकल सॉर्ट केवल डायरेक्टेड एसाइक्लिक ग्राफ पर काम करता है। एक डायरेक्टेड एसाइक्लिक ग्राफ (DAG) में एक से अधिक टोपोलॉजिकल सॉर्ट हो सकते हैं।

हम एक C++ प्रोग्राम पर विचार करेंगे, जो ग्राफ में साइकिल चेक करने के लिए टोपोलॉजिकल सॉर्ट करेगा।

उदाहरण के लिए

एल्गोरिदम

Topological Sort:
Begin
    topo_sort(int *v, int T_S[][5], int i) फंक्शन घोषित करें
        a = new NodeInfo.
        a->n = i
        a->S_Time = cn.
        push_node(a) फंक्शन कॉल करें डेटा डालने के लिए।
        v[i] = 1.
        for (int j = 0; j < 5; j++)
            if (T_S[i][j] == 0 || (T_S[i][j] == 1 && v[j] == 1)) तो
                continue.
            else if(T_S[i][j] == 1 && v[j] == 0) तो
                cn++.
                topo_sort(v,T_S, j) फंक्शन कॉल करें।
        cn++.
        a = pop().
        a->L_Time = cn.
        Store_Node(a).
End.

उदाहरण

#include <iostream>
#include <conio.h>
using namespace std;

struct NodeInfo {
    int n;
    int L_Time, S_Time;
} *a = NULL;

struct Node {
    NodeInfo *ptr;
    Node *nxt;
} *t = NULL, *b = NULL, *npt = NULL;

struct Node_Link {
    Node_Link *lk;
    NodeInfo *ptr1;
} *hd = NULL, *m = NULL, *n = NULL, *npt1 = NULL;

int cn = 0;
bool flag = false;

void push_node(NodeInfo *pt) { // डेटा डालें
    npt = new Node;
    npt->ptr = pt;
    npt->nxt = NULL;
    if(t == NULL) {
        t = npt;
    } else {
        npt->nxt = t;
        t = npt;
    }
}

NodeInfo *pop() {
    if(t == NULL) {
        cout << "underflow\n";
    } else {
        b = t;
        t = t->nxt;
        return(b->ptr);
        delete(b);
    }
}

void Store_Node(NodeInfo *pt1) { // डेटा स्टोर करें
    npt1 = new Node_Link;
    npt1->ptr1 = pt1;
    npt1->lk = NULL;
    if(cn == 0) {
        hd = npt1;
        m = hd;
        m->lk = NULL;
        cn++;
    } else {
        m = hd;
        npt1->lk = m;
        hd = npt1;
    }
}

void delete_node(int x) { // नोड डिलीट करें
    m = hd;
    if((m->ptr1)->n == x) {
        hd = hd->lk;
        delete(m);
    } else {
        while((m->ptr1)->n != x && m->lk != NULL) {
            n = m;
            m = m->lk;
        }
        if((m->ptr1)->n == x) {
            n->lk = m->lk;
            delete(m);
        } else if(m->lk == NULL) {
            flag = true;
            cout << "There is no circle in this graph\n";
        }
    }
}

void topo_sort(int *v, int T_S[][5], int i) { // टोपोलॉजिकल सॉर्ट करना
    a = new NodeInfo;
    a->n = i;
    a->S_Time = cn;
    push_node(a);
    v[i] = 1;
    
    for(int j = 0; j < 5; j++) {
        if(T_S[i][j] == 0 || (T_S[i][j] == 1 && v[j] == 1))
            continue;
        else if(T_S[i][j] == 1 && v[j] == 0) {
            cn++;
            topo_sort(v, T_S, j);
        }
    }
    cn++;
    a = pop();
    a->L_Time = cn;
    Store_Node(a);
    return;
}

void topologic_sort(int *v, int T_S[][5], int i) {
    v[i] = 1;
    delete_node(i);
    for(int j = 0; j < 5; j++) {
        if(T_S[i][j] == 0 || (T_S[i][j] == 1 && v[j] == 1)) {
            continue;
        } else if(T_S[i][j] == 1 && v[j] == 0) {
            topologic_sort(v, T_S, j);
        }
    }
    return;
}

void Insert_Edge(int T_S[][5], int source, int destination) { // एज का मान डालें
    T_S[source][destination] = 1;
    return;
}

int main() {
    int v[5], T_S[5][5], T_S_N[5][5], cn = 0, a, b;
    for(int i = 0; i < 5; i++) {
        v[i] = 0;
    }
    for(int i = 0; i < 5; i++) {
        for(int j = 0; j < 5; j++) {
            T_S[i][j] = 0;
        }
    }
    
    while(cn < 5) {
        cout << "Enter the source: ";
        cin >> a;
        cout << "Enter the destination: ";
        cin >> b;
        cout << endl;
        Insert_Edge(T_S, a, b);
        cn++;
    }
    
    topo_sort(v, T_S, 0);
    
    for(int i = 0; i < 5; i++) {
        v[i] = 0;
        for(int j = 0; j < 5; j++) {
            T_S_N[j][i] = T_S[i][j];
        }
    }
    
    if(hd != NULL) {
        topologic_sort(v, T_S_N, (hd->ptr1)->n);
        if(flag == false) {
            cout << "There is a cycle in this graph...\n";
        }
    }
    return 0;
}

आउटपुट

Enter the source: 0
Enter the destination: 1
Enter the source: 1
Enter the destination: 2
Enter the source: 2
Enter the destination: 3
Enter the source: 3
Enter the destination: 4
Enter the source: 4
Enter the destination: 0
There is a cycle in this graph...

यह प्रोग्राम टोपोलॉजिकल सॉर्ट का उपयोग करके डायरेक्टेड ग्राफ में साइकिल डिटेक्ट करता है। यदि टोपोलॉजिकल सॉर्ट के बाद सभी नोड्स प्रोसेस नहीं हो पाते (कुछ नोड्स शेष रह जाते हैं), तो ग्राफ में साइकिल है। दृष्टिकोण: 1) DFS करके टोपोलॉजिकल ऑर्डर प्राप्त करें, 2) ग्राफ को रिवर्स करें, 3) सिंक नोड से रिवर्स ग्राफ पर DFS करें। यदि सभी नोड्स विजिट नहीं होते, तो साइकिल मौजूद है।