जावास्क्रिप्ट में डेप्थ-फर्स्ट सर्च ट्रैवर्सल

DFS सिबलिंग वर्टेक्स से पहले चाइल्ड वर्टेक्स को विजिट करता है; यानी, यह किसी विशेष पाथ की गहराई को उसकी चौड़ाई का पता लगाने से पहले ट्रैवर्स करता है। एल्गोरिदम को लागू करते समय आमतौर पर एक स्टैक (अक्सर रिकर्सन के माध्यम से प्रोग्राम का कॉल स्टैक) उपयोग किया जाता है।

DFS ट्रैवर्सल कैसे काम करता है:

• आसन्न अनविजिटेड वर्टेक्स को विजिट करें। इसे विजिटेड मार्क करें। इसे प्रदर्शित करें। इसे स्टैक में पुश करें।
• यदि कोई आसन्न वर्टेक्स नहीं मिलता है, तो स्टैक से एक वर्टेक्स पॉप करें। (यह स्टैक से उन सभी वर्टेक्स को पॉप कर देगा जिनके आसन्न वर्टेक्स नहीं हैं।)
• नियम 1 और नियम 2 को तब तक दोहराएं जब तक स्टैक खाली न हो जाए।

आइए देखते हैं कि DFS ट्रैवर्सल कैसे काम करता है इसका एक चित्रण।

स्टेप	ट्रैवर्सल	विवरण
1		स्टैक इनिशियलाइज़ करें।
2		S को विजिटेड मार्क करें और इसे स्टैक पर रखें। S से किसी अनविजिटेड आसन्न नोड को एक्सप्लोर करें। हमारे पास तीन नोड्स हैं और हम उनमें से किसी को भी चुन सकते हैं। इस उदाहरण के लिए, हम वर्णमाला क्रम में नोड लेंगे।
3		A को विजिटेड मार्क करें और इसे स्टैक पर रखें। A से किसी अनविजिटेड आसन्न नोड को एक्सप्लोर करें। S और D दोनों A के आसन्न हैं लेकिन हम केवल अनविजिटेड नोड्स के लिए चिंतित हैं।
4		D को विजिट करें और इसे विजिटेड मार्क करें और स्टैक पर रखें। यहां, B और C नोड्स हैं, जो D के आसन्न हैं और दोनों अनविजिटेड हैं। हालांकि, हम फिर से वर्णमाला क्रम में चुनेंगे।
5		हम B चुनते हैं, इसे विजिटेड मार्क करते हैं और स्टैक पर रखते हैं। यहां B के पास कोई अनविजिटेड आसन्न नोड नहीं है। तो, हम B को स्टैक से पॉप करते हैं।
6		पिछले नोड पर वापस जाने के लिए स्टैक टॉप की जांच करें और जांचें कि क्या इसके कोई अनविजिटेड नोड हैं। यहां, हम D को स्टैक के टॉप पर पाते हैं।
7		D से केवल अनविजिटेड आसन्न नोड अब C है। तो हम C को विजिट करते हैं, इसे विजिटेड मार्क करते हैं और इसे स्टैक पर रखते हैं।

C के पास कोई अनविजिटेड आसन्न नोड नहीं है इसलिए हम स्टैक को पॉप करते रहते हैं जब तक हमें ऐसा नोड नहीं मिल जाता जिसके पास अनविजिटेड आसन्न नोड हो। इस मामले में, ऐसा कोई नहीं है और हम तब तक पॉप करते रहते हैं जब तक स्टैक खाली नहीं हो जाता। आइए देखते हैं कि हम इसे जावास्क्रिप्ट में कैसे लागू कर सकते हैं।

उदाहरण

DFS(node) {
    // एक स्टैक बनाएं और इसमें अपना प्रारंभिक नोड जोड़ें
    let s = new Stack(this.nodes.length);
    let explored = new Set();
    s.push(node);
    // पहले नोड को एक्सप्लोर्ड मार्क करें
    explored.add(node);
    // हम तब तक जारी रखेंगे जब तक हमारा स्टैक खाली न हो जाए
    while (!s.isEmpty()) {
        let t = s.pop();
        // स्टैक से निकलने वाले हर एलिमेंट को लॉग करें
        console.log(t);
        // 1. एजेज ऑब्जेक्ट में, हम उन नोड्स को खोजते हैं जिनसे यह नोड सीधे जुड़ा हुआ है।
        // 2. हम उन नोड्स को फ़िल्टर करते हैं जो पहले से एक्सप्लोर्ड हैं।
        // 3. फिर प्रत्येक अनएक्सप्लोर्ड नोड को एक्सप्लोर्ड मार्क करते हैं और इसे स्टैक में पुश करते हैं।
        this.edges[t]
            .filter(n => !explored.has(n))
            .forEach(n => {
                explored.add(n);
                s.push(n);
            });
    }
}

खैर, यह आसान था। हमने वास्तव में क्यू को स्टैक से बदल दिया और वॉयला, हमारे पास DFS है। वास्तव में यही एकमात्र अंतर है। DFS को रिकर्सन का उपयोग करके भी लागू किया जा सकता है। लेकिन इस मामले में इससे बचना बेहतर है क्योंकि बड़ा ग्राफ होने पर हमें कॉल स्टैक को ट्रैक करने के लिए अतिरिक्त मेमोरी की आवश्यकता होगी।

आप इसका परीक्षण इस तरह कर सकते हैं:

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.addEdge("A", "C");
g.addEdge("A", "B");
g.addEdge("A", "D");
g.addEdge("D", "E");
g.addEdge("E", "F");
g.addEdge("B", "G");
g.DFS("A");

आउटपुट

इससे निम्न आउटपुट मिलेगा।

A D E F B G C