C++ में DAG के लिए रैंडम लीनियर एक्सटेंशन बनाना

यहां हम डायरेक्टेड एसाइक्लिक ग्राफ (DAG) के रैंडम लीनियर एक्सटेंशन बनाने का तरीका देखेंगे। लीनियर एक्सटेंशन मूल रूप से DAG की टोपोलॉजिकल सॉर्टिंग है। आइए मान लें कि ग्राफ नीचे जैसा है -

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

जैसा कि हम जानते हैं कि सोर्स वर्टेक्स डेस्टिनेशन वर्टेक्स के बाद आएगा, इसलिए हमें पिछले एलिमेंट्स को स्टोर करने के लिए स्टैक का उपयोग करने की आवश्यकता है। सभी नोड्स पूरे होने के बाद, हम बस उन्हें स्टैक से प्रदर्शित कर सकते हैं।

इनपुट

आउटपुट

टोपोलॉजिकली सॉर्टेड ऑर्डर के बाद नोड्स - 5 4 2 3 1 0

एल्गोरिदम

topoSort(u, visited, stack)

इनपुट - प्रारंभ वर्टेक्स u, एक ऐरे जो ट्रैक रखता है कि कौन सा नोड विजिट किया गया है या नहीं। नोड्स स्टोर करने के लिए एक स्टैक।

आउटपुट - स्टैक में टोपोलॉजिकल क्रम में वर्टेक्स सॉर्ट करना।

Begin
    u को विजिटेड के रूप में चिह्नित करें
    u के साथ आसन्न सभी वर्टेक्स v के लिए, do
        यदि v विजिटेड नहीं है, तो
            topoSort(v, visited, stack)
        done
    u को स्टैक में पुश करें
End

performTopologicalSorting(Graph)

इनपुट - दिया गया डायरेक्टेड एसाइक्लिक ग्राफ।

आउटपुट - नोड्स का अनुक्रम।

Begin
    प्रारंभ में सभी नोड्स को अनविजिटेड चिह्नित करें
    ग्राफ के सभी नोड्स v के लिए, do
        यदि v विजिटेड नहीं है, तो
            topoSort(i, visited, stack)
        done
    स्टैक से सभी एलिमेंट्स पॉप और प्रिंट करें
End

उदाहरण

#include <iostream>
#include <stack>
#define NODE 6
using namespace std;

int graph[NODE][NODE] = {
    {0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0},
    {0, 0, 0, 1, 0, 0},
    {0, 1, 0, 0, 0, 0},
    {1, 1, 0, 0, 0, 0},
    {1, 0, 1, 0, 0, 0}
};

void topoSort(int u, bool visited[], stack<int> &stk) {
    visited[u] = true; // नोड v को विजिटेड के रूप में सेट करें
    for (int v = 0; v < NODE; v++) {
        if (graph[u][v]) { // u के आसन्न सभी वर्टेक्स v के लिए
            if (!visited[v])
                topoSort(v, visited, stk);
        }
    }
    stk.push(u); // प्रारंभिक वर्टेक्स को स्टैक में पुश करें
}

void performTopologicalSort() {
    stack<int> stk;
    bool vis[NODE];
    for (int i = 0; i < NODE; i++)
        vis[i] = false; // प्रारंभ में सभी नोड्स अनविजिटेड हैं
    for (int i = 0; i < NODE; i++)
        if (!vis[i]) // जब नोड विजिटेड नहीं है
            topoSort(i, vis, stk);
    while (!stk.empty()) {
        cout << stk.top() << " ";
        stk.pop();
    }
}

int main() {
    cout << "Nodes after topological sorted order: ";
    performTopologicalSort();
    return 0;
}

आउटपुट

Nodes after topological sorted order: 5 4 2 3 1 0