C++ प्रोग्राम: जांचें कि क्या ग्राफ में टोपोलॉजिकल सॉर्टिंग की जा सकती है

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

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

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

एल्गोरिदम

Topo_Sort फंक्शन के लिए

Begin
    फंक्शन Topo_Sort() परिभाषित करें
        x को इंटीजर डेटाटाइप, vstd[] बूलियन ऐरे और Stack को स्टैक के रूप में घोषित करें।
        उन्हें पैरामीटर के रूप में पास करें।
        vstd[x] = true इनिशियलाइज़ करें वर्तमान नोड को विजिटेड मार्क करने के लिए।
        एक इटरेटर i घोषित करें।
        for (i = a[x].begin(); i != a[x].end(); ++i)
            if (!vstd[*i]) तो
                Topo_Sort(*i, vstd, Stack) फंक्शन कॉल करें।
        push() फंक्शन कॉल करें स्टैक में मान डालने के लिए।
End.

उदाहरण

#include <iostream>
#include <list>
#include <stack>
using namespace std;

class Graph { // ग्राफ को दर्शाने वाला क्लास
    int V;
    list *adj; // एडजेसेंसी लिस्ट्स वाले ऐरे का पॉइंटर
    
    void Topo_Sort(int v, bool visited[], stack &Stack); // TopologicalSort द्वारा उपयोग किया जाने वाला फंक्शन
    
public:
    Graph(int V); // Graph का कंस्ट्रक्टर
    void Insert_Edge(int v, int w); // ग्राफ में एज जोड़ने के लिए
    void Topol_Sort(); // पूरे ग्राफ का टोपोलॉजिकल सॉर्ट प्रिंट करता है
};

Graph::Graph(int V) {
    this->V = V;
    adj = new list[V];
}

void Graph::Insert_Edge(int v, int w) {
    adj[v].push_back(w); // v की लिस्ट में w जोड़ें
}

// Topol_Sort द्वारा उपयोग किया जाने वाला एक रिकर्सिव फंक्शन
void Graph::Topo_Sort(int v, bool visited[], stack &Stack) {
    visited[v] = true; // वर्तमान नोड को विजिटेड मार्क करें
    
    list::iterator i;
    for(i = adj[v].begin(); i != adj[v].end(); ++i)
        if(!visited[*i])
            Topo_Sort(*i, visited, Stack);
    
    // वर्तमान वर्टेक्स को स्टैक में पुश करें जो परिणाम स्टोर करता है
    Stack.push(v);
}

void Graph::Topol_Sort() {
    stack Stack;
    
    // सभी वर्टेक्स को विजिटेड नहीं के रूप में मार्क करें
    bool *visited = new bool[V];
    for(int i = 0; i < V; i++)
        visited[i] = false;
    
    for(int i = 0; i < V; i++)
        if(visited[i] == false)
            Topo_Sort(i, visited, Stack);
    
    while(Stack.empty() == false) {
        cout << Stack.top() << " ";
        Stack.pop();
    }
}

int main() {
    Graph g(6); // उपरोक्त आरेख में दिए गए ग्राफ को बनाएं
    g.Insert_Edge(5, 2);
    g.Insert_Edge(5, 0);
    g.Insert_Edge(4, 0);
    g.Insert_Edge(4, 1);
    g.Insert_Edge(2, 3);
    g.Insert_Edge(3, 1);
    
    cout << "Topological Sort of the graph is: \n";
    g.Topol_Sort();
    return 0;
}

आउटपुट

Topological Sort of the graph is: 5 4 2 3 1 0

टोपोलॉजिकल सॉर्ट DAG के वर्टेक्स का एक लीनियर ऑर्डरिंग है जहां प्रत्येक डायरेक्टेड एज uv के लिए, वर्टेक्स u, v से पहले आता है। यह प्रोग्राम DFS-आधारित दृष्टिकोण का उपयोग करता है। यदि ग्राफ में साइकिल है, तो टोपोलॉजिकल सॉर्ट संभव नहीं है। अनुप्रयोगों में टास्क शेड्यूलिंग, कोर्स प्रीरिक्विजिट्स, बिल्ड सिस्टम्स और डिपेंडेंसी रिजॉल्यूशन शामिल हैं।