Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> JavaScript

जावास्क्रिप्ट DFS का उपयोग करके टोपोलॉजिकल सॉर्टिंग


डायरेक्टेड ग्राफ का टोपोलॉजिकल सॉर्ट या टोपोलॉजिकल ऑर्डरिंग उसके वर्टेक्स का एक लीनियर ऑर्डरिंग है जैसे कि वर्टेक्स 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

  1. Firebug का उपयोग करके जावास्क्रिप्ट डीबगिंग Firebug का उपयोग करके जावास्क्रिप्ट डीबगिंग

    डीबगिंग दोषों को व्यवस्थित रूप से हटाने की विधि है। यह सब टेस्ट केसेस के एक्जीक्यूशन से शुरू होता है। जब भी टेस्ट केसेस एक्जीक्यूट होते हैं, वास्तविक परिणामों की तुलना अपेक्षित परिणामों से की जाती है। यदि वास्तविक परिणामों और अपेक्षित परिणामों के बीच कोई पत्राचार नहीं है, तो रूट कॉज विश्लेषण किया जा

  1. JavaScript इम्पोर्ट्स में  { }  का उपयोग JavaScript इम्पोर्ट्स में '{ }' का उपयोग

    JavaScript इम्पोर्ट्स में {} का उपयोग करने का निम्नलिखिक कोड है:उदाहरण<!DOCTYPE html> <html lang="hi"> <head> <meta charset="UTF-8" /> <meta name="viewport" content="width=device-width, initial-scale=1.0" /> <title>Import wi

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

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