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

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

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

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

इनपुट:0 0 0 0 0 00 0 0 0 00 0 0 1 0 00 1 0 0 01 1 0 0 0 01 0 1 0 0 आउटपुट:टोपोलॉजिकल सॉर्ट किए गए क्रम के बाद नोड्स:5 4 2 3 1 0 
एल्गोरिदम
 

 topoSort(u, विज़िट किया गया, स्टैक) 
 

 इनपुट - स्टार्ट वर्टेक्स यू, एक ऐरे का ट्रैक रखने के लिए कि किस नोड का दौरा किया गया है या नहीं। नोड्स को स्टोर करने के लिए एक स्टैक। 
 आउटपुट - स्टैक में टोपोलॉजिकल अनुक्रम में शीर्षों को क्रमबद्ध करना।
 
सभी शीर्षों के लिए u को विज़िट के रूप में चिह्नित करना शुरू करें v जो u से सटा हुआ है, यदि v विज़िट नहीं किया गया है, तो topoSort(c, विज़िट, स्टैक) किया गया आपको एक स्टैक में धकेलता हैअंत
 

 टोपोलॉजिकल सॉर्टिंग (ग्राफ़) करें 
 

 इनपुट - दिया गया निर्देशित चक्रीय ग्राफ। 
 आउटपुट - नोड्स का अनुक्रम।
 
शुरू में ग्राफ के सभी नोड्स v के लिए सभी नोड्स को बिना देखे के रूप में चिह्नित करना शुरू करें, यदि v का दौरा नहीं किया जाता है, तो topoSort(i, विज़िट, स्टैक) किया पॉप और स्टैकएंड से सभी तत्वों को प्रिंट करें।
 
उदाहरण
 
#शामिल करें#शामिल करें<स्टैक>#नेमस्पेस एसटीडी का उपयोग करके नोड 6 परिभाषित करें;इंट ग्राफ[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}}; शून्य टोपोसॉर्ट (इंट यू, बूल विज़िट किया गया [], स्टैक <इंट> और एसटीके) { का दौरा किया [यू] =सच; // सेट के रूप में नोड वी के लिए दौरा किया जाता है (int v =0; v stk; बूल विज़ [नोड]; for(int i =0; i 
आउटपुट
 
टोपोलॉजिकल क्रमबद्ध क्रम के बाद नोड्स:5 4 2 3 1 0