टोपोलॉजिकल सॉर्टिंग

निर्देशित चक्ररहित ग्राफ के लिए टोपोलॉजिकल सॉर्टिंग शीर्षों का रैखिक क्रम है। एक निर्देशित ग्राफ के प्रत्येक किनारे U-V के लिए, शीर्ष u क्रम में शीर्ष v से पहले आएगा।

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

इनपुट और आउटपुट

इनपुट: 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 आउटपुट: टोपोलॉजिकली क्रमबद्ध क्रम के बाद नोड्स: 5 4 2 3 1 0

एल्गोरिदम

topoSort(u, visited, stack)

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

शुरू     u को देखा गया चिह्नित करें     u के साथ आसन्न सभी शीर्ष v के लिए, करें       यदि v नहीं देखा गया है, तो         topoSort(c, visited, stack)     किया     u को स्टैक में पुश करें अंत

performTopologicalSorting(Graph)

इनपुट: दिया गया निर्देशित चक्ररहित ग्राफ।
आउटपुट: नोड्स का अनुक्रम।

शुरू     प्रारंभ में सभी नोड्स को अनदेखा चिह्नित करें     ग्राफ के सभी नोड्स v के लिए, करें       यदि v नहीं देखा गया है, तो         topoSort(i, visited, stack)     किया     स्टैक से सभी तत्वों को पॉप और प्रिंट करें अंत।

उदाहरण

#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
आउटपुट
Nodes after topological sorted order: 5 4 2 3 1 0