डायरेक्टेड ग्राफ का टोपोलॉजिकल सॉर्ट या टोपोलॉजिकल ऑर्डरिंग उसके वर्टेक्स का एक लीनियर ऑर्डरिंग है जैसे कि वर्टेक्स u से वर्टेक्स v तक के हर डायरेक्टेड एज UV के लिए, u ऑर्डरिंग में v से पहले आता है। यह केवल डायरेक्टेड ग्राफ में समझ में आता है।
कई स्थान हैं जहां टोपोलॉजिकल सॉर्ट बहुत मायने रखता है। उदाहरण के लिए, मान लीजिए आप एक रेसिपी फॉलो कर रहे हैं, इसमें कुछ स्टेप्स हैं जो अगले स्टेप्स पर जाने के लिए जरूरी हैं। लेकिन इनमें से कुछ को समानांतर में किया जा सकता है। इसी तरह, कॉलेज में कोर्स चुनते समय, अधिक एडवांस कोर्स के लिए कुछ पूर्वापेक्षाएँ होती हैं जो स्वयं आगे के कोर्स के लिए पूर्वापेक्षाएँ हो सकती हैं। उदाहरण के लिए:
उदाहरण
/** * CS101 CS102 * / \ / * CS204 CS340 * \ /| \ * CS380 | CS410 * \ | / * CS540 */
उपरोक्त ग्राफ में, यदि आप एक लेवल पर कोर्स लेना चाहते हैं, तो आपको उससे ऊपर के लेवल से जुड़े सभी कोर्स पहले लेने होंगे। उपरोक्त ग्राफ के लिए कुछ संभावित टोपोलॉजिकल सॉर्ट निम्नलिखित हैं:
CS101 -> CS204 -> CS102 -> CS340 -> CS410 -> CS380 -> CS540 CS102 -> CS101 -> CS340 -> CS204 -> CS410 -> CS380 -> CS540
आइए इसे जावास्क्रिप्ट में लागू करते हैं। हम 2 फ़ंक्शन लिखेंगे, टोपोलॉजिकल सॉर्ट, और टोपोलॉजिकलसॉर्टहेल्पर ग्राफ को रिकर्सिवली मार्क और एक्सप्लोर करने में मदद के लिए।
उदाहरण
topologicalSortHelper(node, explored, s) {
explored.add(node);
// इस नोड को विजिटेड मार्क करता है और उन नोड्स पर जाता है
// जो इस नोड पर निर्भर हैं, एज है node ----> n
this.edges[node].forEach(n => {
if (!explored.has(n)) {
this.topologicalSortHelper(n, explored, s);
}
});
// इस नोड के लिए सभी निर्भरताएं हल हो गई हैं, हम अब कर सकते हैं
// इसे स्टैक में जोड़ें।
s.push(node);
}
topologicalSort() {
// सॉर्टेड ऑर्डर में सभी एलिमेंट्स को ट्रैक करने के लिए स्टैक बनाएं
let s = new Stack(this.nodes.length);
let explored = new Set();
// हमारे ग्राफ में हर अनविजिटेड नोड के लिए, हेल्पर को कॉल करें।
this.nodes.forEach(node => {
if (!explored.has(node)) {
this.topologicalSortHelper(node, explored, s);
}
});
while (!s.isEmpty()) {
console.log(s.pop());
}
}
आप इसका परीक्षण इस तरह कर सकते हैं:
उदाहरण
let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");
g.addDirectedEdge("A", "C");
g.addDirectedEdge("A", "B");
g.addDirectedEdge("A", "D");
g.addDirectedEdge("C", "D");
g.addDirectedEdge("D", "E");
g.addDirectedEdge("E", "F");
g.addDirectedEdge("B", "G");
g.topologicalSort();
हमने जो ग्राफ बनाया वह इस तरह दिखता है:
उदाहरण
/** * A * / | \ * C | B * \ | | * D G * | * E * | * F */
आउटपुट
इससे निम्न आउटपुट मिलेगा:
A B G C D E F