रैखिक समय एल्गोरिथ्म MST

Question

के लिए मैं किसी को भी एक ग्राफ के MST खोजने के लिए एक रेखीय समय एल्गोरिथ्म को इंगित कर सकते हैं अगर जब वहाँ वजन की एक छोटी संख्या (यानी किनारों केवल 2 अलग वजन हो सकता है) है सोच रहा था।

मैं Boruvka की जिनमें से कोई भी किसी भी गुण है कि इस विशेष मामले में रन टाइम को कम करेगा है लगता है गूगल रस्मी की, Kruskal के, के अलावा अन्य पर कुछ भी नहीं मिला। मैं इसे रैखिक समय यह कुछ (जो MST पाता है जब वजन वर्दी कर रहे हैं) BFS के संशोधन की तरह होना चाहिए था बनाने के लिए अनुमान लगा रहा हूँ।

Answer 1

रस्मी के O(V lg V) क्रम में lg V कारक के कारण ढेर है कि अगले उम्मीदवार बढ़त को खोजने के लिए इस्तेमाल किया जाता है। मैं बहुत यकीन है कि यह एक प्राथमिकता कतार कब वहां संभव वजन की एक सीमित संख्या है, जो O(V) को रस्मी को कम करेगा कि लगातार समय में प्रविष्टि और हटाने करता है डिजाइन करने के लिए संभव है हूँ।

प्राथमिकता कतार के लिए, मेरा मानना ​​है कि यह एक सरणी जिसका सूचकांक हर संभव वजन को शामिल किया गया, साथ पर्याप्त होगा जहां एक लिंक्ड सूची है कि वजन के साथ तत्व शामिल करने के लिए प्रत्येक तत्व अंक। तुम अब भी पता लगाना है जो ("सबसे कम" गैर खाली एक) से बाहर अगले तत्व प्राप्त करने के लिए सूची के लिए d का एक पहलू (अलग वजन की संख्या) होगा, लेकिन अगर d एक निरंतर है, तो आप करेंगे ठीक रहो।

Answer 2

एसमंड एल्डहुसेट के उत्तर पर विस्तार से: यदि एमएसटी में वजन 0, 1, 2, 3, ..., यू -1 में संख्याओं तक सीमित है, तो आप चलाने के लिए कई मौजूदा एल्गोरिदम अनुकूलित कर सकते हैं यू (स्थिर) रैखिक समय में यदि यू स्थिर है।

उदाहरण के लिए, Kruskal एल्गोरिथ्म लेते हैं। कृष्काल के एल्गोरिदम में पहला कदम किनारों को वजन के आरोही क्रम में क्रमबद्ध करना है। यदि आप प्रकार या समय हे (एम एलजी यू) की गिनती का उपयोग करें यदि आप मूलांक प्रकार का उपयोग आप समय हे (एम + यू) में ऐसा कर सकते हैं। यदि यू स्थिर है, तो इन दोनों सॉर्टिंग चरणों में रैखिक समय लगता है। नतीजतन, इस मामले में कृष्काल के एल्गोरिदम चलाने के लिए रनटाइम ओ (एम α (एम)) होगा, जहां α (एम) उलटा एकरमेन समारोह है, क्योंकि सीमित कारक विवादित सेट वन को बनाए रखने का रनटाइम होगा ।

वैकल्पिक रूप से, रस्मी एल्गोरिथ्म को देखो। आपको नोड्स को उम्मीदवार दूरी की प्राथमिकता कतार बनाए रखने की आवश्यकता है। आप जानते हैं कि सभी किनारों रेंज [0, यू) में हैं, तो आप इस एक सुपर अनुभवहीन रास्ते में बस यू बाल्टी, संभव प्राथमिकता प्रति एक की एक सरणी भंडारण के द्वारा कर सकते हैं। प्राथमिकता कतार में डालने के बाद बस आपको एक वस्तु को दाएं बाल्टी में डंप करने की आवश्यकता होती है। आप तत्व को बेदखल करके इसे कम बाल्टी में ले जाकर कमी-कुंजी कर सकते हैं। फिर आप बाल्टी स्कैन करके एक खोज-मिनट कर सकते हैं। यह हे (एम + नू) है, जो रैखिक है अगर यू एक निरंतर है होना करने के लिए एल्गोरिथ्म क्रम का कारण बनता है।