Wikipedia article on breadth-first search ग्राफ पर चौड़ाई-पहली खोज के लिए दो बार जटिलताएं सूचीबद्ध करता है: ओ (| ई |) और ओ (बी डी)। बाद में पृष्ठ पर, हालांकि, यह केवल ओ (| ई |) सूचीबद्ध करता है।चौड़ाई पहली खोज के लिए दो सूचीबद्ध समय जटिलताओं क्यों हैं?
दो अलग-अलग रनटाइम क्यों हैं? कौनसा सही है?
दोनों समय जटिलताओं सही हैं, लेकिन विभिन्न परिस्थितियों में दो अलग-अलग मात्राओं के सापेक्ष समय जटिलता को मापने के लिए उपयोग किया जाता है। इसे इस तथ्य के साथ करना है कि चौड़ाई-पहले खोज एल्गोरिदम आम तौर पर विभिन्न संदर्भों में उपयोग किए जाने वाले दो अलग-अलग संबंधित एल्गोरिदम को संदर्भित करता है।
एक संदर्भ में, बीएफएस एक एल्गोरिदम है कि ग्राफ में एक ग्राफ और प्रारंभ नोड दिया जाता है, पहले नोड से पहुंचने वाले प्रत्येक नोड को दूरी 0 पर सभी नोड्स पर जाकर, फिर दूरी 1, फिर दूरी 2, आदि जब तक सभी नोड्स का दौरा नहीं किया जाता है। यह ग्राफ में प्रत्येक नोड पर जायेगा और ऐसा करने की प्रक्रिया में प्रत्येक नोड एक और किनारे किनारे को एक बार (निर्देशित मामले में) या दो बार (अप्रत्यक्ष मामले में) का पता लगाएं। कौन से नोड्स का पता लगाने और उचित बहीखाता का उपयोग करने के ट्रैक रखने के लिए कतारों का उपयोग करके, रनटाइम ओ (| ई | + | वी |) होगा (और आगे अनुकूलन के साथ, यह ओ (| ई |) होगा)।
एक अलग संदर्भ में, बीएफएस एक खोज एल्गोरिदम है जो ग्राफ में किसी गंतव्य नोड में ग्राफ में कुछ प्रारंभ नोड से सबसे छोटा पथ खोजने के लिए प्रयोग किया जाता है। इस मामले में, जैसे ही यह गंतव्य नोड को खोजता है, एल्गोरिदम चलना बंद कर देता है। इसका मतलब यह है कि रनटाइम इस बात पर निर्भर करता है कि गंतव्य नोड स्रोत नोड से कितना दूर है। बदले में वह दूरी ग्राफ की संरचना पर निर्भर करती है। यदि ग्राफ घनत्व से जुड़ा हुआ है, तो नोड इतना दूर नहीं हो सकता है, और यदि ग्राफ स्पैस है, तो नोड बेहद दूर हो सकता है। इस संदर्भ में, "शाखाकरण कारक" बी नामक पैरामीटर में जोड़ना आम है, जो कि किसी भी नोड के समीप औसत या अधिकतम संख्या का वर्णन करता है। इसका मतलब है कि
अगर हम मान लेते हैं कि गंतव्य नोड शुरू नोड से दूरी घ पर है, तो BFS ज्यादा से ज्यादा का दौरा करेंगे ख + b + ... + ख घ = हे (बी डी) अपनी खोज के दौरान नोड्स, उनमें से प्रत्येक पर ओ (बी) समय खर्च करना। तदनुसार, कुल रनटाइम ओ (बी डी) होगा।
सारांश में:
आशा है कि इससे मदद मिलती है!
मुझे अभी एहसास हुआ कि आप अपने प्रश्न का उत्तर दे रहे हैं। हाहा – justhalf
मुझे भी! हालांकि मैं आपको समय लेने की सराहना करता हूं। मुझे कुछ चीजों को साफ़ करने में मदद मिली! :) – Rishi
बीएफएस को पहली शाखा में लक्ष्य नोड पाता है तो 'बी' और' डी' के मामले में जटिलता क्या है? $ b^d $ अधिकतम संख्या में नोड्स का विस्तार किया जाना चाहिए यदि यह अंत में नोड पर लक्ष्य पाता है तो न्यूनतम संख्या में नोड्स का उत्तर क्या है जिसे बीएफएस द्वारा विस्तारित किया जा सकता है? – orange
क्या चौड़ाई-पहली खोज ओ (| वी | + | ई |) की समय जटिलता नहीं है? क्योंकि हर नोड और किनारे बिल्कुल एक बार दौरा किया जाता है। एल्गोरिदम का एक दृश्य प्रतिनिधित्व यह साबित करता है ... – nbro
एक जुड़े ग्राफ में, | वी | = ओ (| ई |), तो दोनों ग्राफ के कनेक्ट होने तक बराबर हैं। – templatetypedef