DAG (डायरेक्टेड एसाइक्लिक ग्राफ) का टोपोलॉजिकल सॉर्टिंग वर्टेक्स का एक रैखिक क्रम है जिसमें प्रत्येक डायरेक्टेड एज uv के लिए, वर्टेक्स u क्रम में v से पहले आता है। यदि ग्राफ DAG नहीं है, तो ग्राफ के लिए टोपोलॉजिकल सॉर्टिंग संभव नहीं है।
फंक्शन और स्यूडोकोड
Begin function topologicalSort(): a) वर्तमान नोड को विज़िटेड मार्क करें। b) इस वर्टेक्स से सटे सभी वर्टेक्स के लिए पुनरावृत्ति करें। c) वर्तमान वर्टेक्स को स्टैक में पुश करें जो परिणाम संग्रहीत करता है। End Begin function topoSort() जो रिकर्सिव topologicalSort() फंक्शन का उपयोग करता है: a) उन सभी वर्टेक्स को मार्क करें जो विज़िटेड नहीं हैं। b) topologicalSort() फंक्शन को कॉल करें। c) सामग्री प्रिंट करें। End
उदाहरण
#include<iostream> #include <list> #include <stack> using namespace std; class G { int n; list<int> *adj; // फंक्शन की घोषणा void topologicalSort(int v, bool visited[], stack<int> &Stack); public: G(int n); // कंस्ट्रक्टर void addEd(int v, int w); void topoSort(); }; G::G(int n) { this->n = n; adj = new list<int> [n]; } void G::addEd(int v, int w) // ग्राफ में एज जोड़ें। { adj[v].push_back(w); // w को v की सूची में जोड़ें } void G::topologicalSort(int v, bool visited[], stack<int> &Stack) { visited[v] = true; // वर्तमान नोड को विज़िटेड मार्क करें list<int>::iterator i; // इस वर्टेक्स से सटे सभी वर्टेक्स के लिए पुनरावृत्ति करें। for (i = adj[v].begin(); i != adj[v].end(); ++i) if (!visited[*i]) topologicalSort(*i, visited, Stack); Stack.push(v); } void G::topoSort() { stack<int> Stack; bool *visited = new bool[n]; // उन सभी वर्टेक्स को मार्क करें जो विज़िटेड नहीं हैं। for (int i = 0; i < n; i++) visited[i] = false; for (int i = 0; i < n; i++) if (visited[i] == false) // topologicalSort() फंक्शन को कॉल करें। topologicalSort(i, visited, Stack); while (Stack.empty() == false) { cout << Stack.top() << " "; // एलिमेंट प्रिंट करें Stack.pop(); } } int main() { G g(6); g.addEd(4, 2); g.addEd(5, 1); g.addEd(4, 0); g.addEd(3, 1); g.addEd(1, 3); g.addEd(3, 2); cout << " Topological Sort of the given graph \n"; g.topoSort(); return 0; }
आउटपुट
Topological Sort of the given graph 5 4 1 3 2 0
