DFS सहोदर शीर्षों पर जाने से पहले बच्चे के शीर्षों पर जाता है; यानी यह किसी विशेष पथ की चौड़ाई का पता लगाने से पहले उसकी गहराई को पार कर जाता है। एक स्टैक (अक्सर प्रोग्राम का कॉल स्टैक रिकर्सन के माध्यम से) आमतौर पर एल्गोरिथम को लागू करते समय उपयोग किया जाता है।
DFS कैसे काम करता है -
- आसन्न अगोचर शीर्ष पर जाएं। इसे विज़िट किए गए के रूप में चिह्नित करें। इसे प्रदर्शित करें। इसे एक स्टैक में पुश करें।
- यदि कोई आसन्न शीर्ष नहीं मिलता है, तो स्टैक से एक शीर्ष पॉप अप करें। (यह स्टैक से सभी शीर्षों को पॉप अप करेगा, जिसमें आसन्न कोने नहीं हैं।)
- नियम 1 और नियम 2 को तब तक दोहराएं जब तक कि स्टैक खाली न हो जाए।
आइए एक उदाहरण देखें कि डीएफएस ट्रैवर्सल कैसे काम करता है।
| चरण | ट्रैवर्सल | <थ>विवरण
|---|---|
| 1 | <टीडी>स्टैक को इनिशियलाइज़ करें। |
| 2 | <टीडी>Sचिह्नित करें के रूप में दौरा किया और इसे ढेर पर रख दिया। S . से किसी भी न देखे गए आसन्न नोड को एक्सप्लोर करें . हमारे पास तीन नोड हैं और हम उनमें से किसी को भी चुन सकते हैं। इस उदाहरण के लिए, हम नोड को वर्णानुक्रम में लेंगे। |
| 3 | <टीडी>Aचिह्नित करें के रूप में दौरा किया और इसे ढेर पर रख दिया। A . से किसी भी न देखे गए आसन्न नोड को एक्सप्लोर करें . दोनों एस और डी ए के निकट हैं लेकिन हम केवल अनजान नोड्स के लिए चिंतित हैं। |
| 4 | <टीडी>विजिट D और इसे विज़िट के रूप में चिह्नित करें और स्टैक पर रखें। यहां, हमारे पास B . है और सी नोड्स, जो D . के निकट हैं और दोनों अनजान हैं। हालाँकि, हम फिर से वर्णानुक्रम में चयन करेंगे। |
| 5 | <टीडी>हम B, . चुनते हैं इसे विज़िट के रूप में चिह्नित करें और स्टैक पर रखें। यहां बी कोई अनजान आसन्न नोड नहीं है। तो, हम B pop पॉप करते हैं ढेर से। |
| 6 | <टीडी>हम पिछले नोड पर लौटने के लिए स्टैक टॉप की जांच करते हैं और जांचते हैं कि क्या इसमें कोई अनजान नोड है। यहां, हमें D . मिलता है ढेर के शीर्ष पर होना। |
| 7 | <टीडी>केवल विज़िट नहीं किया गया आसन्न नोड D . से है सी . है अभी। इसलिए हम C, . पर जाते हैं इसे विज़िट के रूप में चिह्नित करें और इसे स्टैक पर रखें। |
सी . के रूप में कोई अनजान आसन्न नोड नहीं है इसलिए हम स्टैक को तब तक पॉप करते रहते हैं जब तक हमें एक ऐसा नोड नहीं मिल जाता है जिसमें एक अनजान आसन्न नोड होता है। इस मामले में, कोई नहीं है और हम स्टैक खाली होने तक पॉप करते रहते हैं। आइए देखें कि हम इसे जावास्क्रिप्ट में कैसे लागू कर सकते हैं।
उदाहरण
DFS(node) {// एक स्टैक बनाएं और उसमें अपना प्रारंभिक नोड जोड़ें s =new Stack(this.nodes.length); चलो पता लगाया =नया सेट (); एस.पुश (नोड); // पहले नोड को एक्सप्लोर किए गए के रूप में चिह्नित करें। जोड़ें (नोड); // हम तब तक जारी रखेंगे जब तक हमारा स्टैक खाली नहीं हो जाता (!s.isEmpty ()) {let t =s.pop (); // स्टैक कंसोल से बाहर आने वाले प्रत्येक तत्व को लॉग करें। लॉग (टी); // 1. किनारों की वस्तु में, हम उन नोड्स की खोज करते हैं जिनसे यह नोड सीधे जुड़ा हुआ है। // 2. हम उन नोड्स को फ़िल्टर करते हैं जिन्हें पहले ही खोजा जा चुका है। // 3. फिर हम प्रत्येक बेरोज़गार नोड को खोजे गए के रूप में चिह्नित करते हैं और इसे स्टैक पर धकेलते हैं। this.edges[t] .filter(n => !explored.has(n)) .forEach(n => {explored.add(n); s.push(n); }); }}
खैर, यह आसान था। हमने वास्तव में स्टैक और वॉइला के लिए कतार की अदला-बदली की, हमारे पास DFS है। यह वास्तव में 2 के बीच एकमात्र अंतर है। डीएफएस को रिकर्सन का उपयोग करके भी लागू किया जा सकता है। लेकिन इस मामले में इससे बचना सबसे अच्छा है क्योंकि बड़े ग्राफ़ का मतलब है कि हमें कॉल स्टैक का ट्रैक रखने के लिए अतिरिक्त मेमोरी की आवश्यकता है।
आप -
. का उपयोग करके इसका परीक्षण कर सकते हैं चलो g =नया ग्राफ़ ();g.addNode("A");g.addNode("B");g.addNode("C");g.addNode("D");g.addNode ("ई");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"); आउटपुट
यह आउटपुट देगा।
एडीईएफबीजीसी