मुझे इस ऑनलाइन का कोई जवाब नहीं मिल रहा है, और इसके समान प्रश्नों के अन्य उत्तरों में ऐसा लगता है कि डीएफएस का लाभ यह है कि यह डीएफएस की तुलना में कम स्मृति का उपयोग करता है।पहली बार चौड़ाई पहले खोज की तुलना में अधिक मेमोरी का उपयोग क्यों करती है?
मेरे लिए यह मेरी अपेक्षा के विपरीत लगता है। एक बीएफएस को केवल उस अंतिम नोड को स्टोर करना होता है जिसे उसने देखा था। उदाहरण के लिए अगर हम नीचे पेड़ में संख्या 7 के लिए खोज रहे हैं:
यह मूल्य 8, फिर 3, 10, 1, 6, 14, 4 के साथ नोड खोज करेंगे तो अंत में 7। एक डीएफएस के लिए यह नोड को 8 के साथ खोज करेगा, फिर 3, 1, 6, 4, फिर अंत में 7.
यदि प्रत्येक नोड स्मृति में संग्रहीत होता है, तो इसके मूल्य, उसके बच्चों और इसकी स्थिति के बारे में जानकारी के साथ पेड़ में तो एक बीएफएस कार्यक्रम को केवल अंतिम नोड की स्थिति के बारे में जानकारी संग्रहीत करने की आवश्यकता होगी, फिर यह पेड़ की जांच कर सकता है और पेड़ में अगला नोड ढूंढ सकता है। एक डीएफएस कार्यक्रम को उस अंतिम नोड को स्टोर करना होता है, साथ ही सभी नोड्स जो पहले से ही देख चुके हैं, इसलिए यह उन्हें फिर से जांच नहीं करता है और आखिरी पीढ़ी के नोड्स में से किसी एक को आने वाले सभी पत्ते नोड्स के माध्यम से चक्र चलाता है।
तो बीएफएस वास्तव में कम स्मृति का उपयोग क्यों करता है?
एक पूर्ण पेड़ आम तौर पर लंबा होने से अधिक व्यापक होगा। यदि आपका उदाहरण पेड़ भरा हुआ था, तो आपके पास नीचे के स्तर पर 8 नोड्स होंगे। डीएफएस में, आपको केवल एक ढेर की आवश्यकता होगी जो गहरे स्तर के रूप में गहरा है। बीएफएस में, आपको एक कतार की आवश्यकता है जो व्यापक स्तर के रूप में व्यापक है। –
डीएफएस की अंतरिक्ष जटिलता ओ (डी) है जहां डी [व्यास] (http://en.wikipedia.org/wiki/Distance_ (graph_theory) #Related_concepts) ग्राफ का है। बीएफएस का ओ ओ (डब्ल्यू) है, जहां डब्ल्यू अधिकतम संख्या में वर्टेक्स है जो प्रारंभ नोड के लिए एक ही दूरी है। यह ग्राफ संरचना पर निर्भर करता है जो दोनों में से अधिक कुशल है। –