किनारों की लम्बाई बाधित होने पर न्यूनतम स्पैनिंग पेड़ के लिए एक तेज़ एल्गोरिदम?

Question

मान लीजिए कि आपके पास एक निर्देशित ग्राफ़ है जो गैर-ऋणात्मक, पूर्णांक किनारों की लंबाई है जो 0 से यू -1 में हैं, समावेशी। इस ग्राफ के न्यूनतम स्पैनिंग पेड़ की गणना करने के लिए सबसे तेज़ एल्गोरिदम क्या है? हम अभी भी क्रुस्कल के एल्गोरिदम ओ (एम लॉग एन) जैसे मौजूदा न्यूनतम स्पैनिंग पेड़ एल्गोरिदम का उपयोग कर सकते हैं) या प्राइम के एल्गोरिदम (ओ (एम + एन लॉग एन))। हालांकि, उन मामलों के लिए जहां यू छोटा है, मुझे लगता है कि इसे बेहतर करना संभव होना चाहिए।

क्या कोई एल्गोरिदम है जो अधिक पारंपरिक एमएसटी एल्गोरिदम के साथ प्रतिस्पर्धी हैं जो इस तथ्य का फायदा उठाने में सक्षम हैं कि किनारों की लंबाई कुछ सीमा में बाधित है?

धन्यवाद!

Answer 1

फ्रेडमैन-विलार्ड ने यूनिट-लागत रैम पर पूर्णांक किनारों की लंबाई के लिए ओ (एम + एन) एल्गोरिदम दिया।

यह तर्कसंगत रूप से सुधार में नहीं है: किनारों की लंबाई पर प्रतिबंध के बिना (यानी, लंबाई एक अपारदर्शी डेटा प्रकार है जो केवल तुलना का समर्थन करता है), चाज़ेल ने ओ (एम अल्फा (एम, एन) + एन) एल्गोरिदम दिया (अल्फा उलटा एकरमेन फ़ंक्शन है) और कारगर-क्लेन-तारजन ने यादृच्छिक ओ (एम + एन) एल्गोरिदम दिया।

मुझे नहीं लगता कि डैरेन का विचार ओ (एम + एन + यू) -टाइम एल्गोरिदम की ओर जाता है। जार्निक ("प्राइम") अपनी प्राथमिकता कतार का उपयोग एकान्त रूप से नहीं करता है, इसलिए बाल्टी कई बार स्कैन की जा सकती है; कृष्काल को एक पृथक सेट डेटा संरचना की आवश्यकता होती है, जो ओ (एम + एन) नहीं हो सकता है।

Answer 2

पूर्णांक किनारों के भार के साथ आप सबसे बुरी स्थिति O(1) जटिलता के साथ प्राथमिकता कतार प्राप्त करने के लिए बाल्टीिंग का उपयोग कर सकते हैं, लेकिन अतिरिक्त O(U) अंतरिक्ष जटिलता।

एमएसटी एल्गोरिदम के भीतर आपने उल्लेख किया है कि आप इस पूर्णांक संरचना के साथ तुलना आधारित प्राथमिकता कतारों को प्रतिस्थापित करने में सक्षम होना चाहिए, और इसलिए जटिलता आवश्यकताओं में O(log(n)) depenedence को हटा दें। मुझे उम्मीद है कि आप O(n + m) की शैली में एक समग्र जटिलता के साथ समाप्त हो जाएंगे।

मूलतः

आप सेटअप संकुचित लिंक्ड सूचियों, जहां प्रत्येक सूची द्वारा अनुक्रमित की लागत एक सेट है कि बाल्टी के साथ जुड़े (पूर्णांक!):

struct bucket_list 
{ 
    _cost; // array[0..N-1] holding current cost for each item 

    _head; // array[0..U-1] holding index of first item in each bucket 

    _next; // array[0..N-1] where _next[i] is the next item 
      // in a list for the ith item 

    _prev; // array[0..N-1] where _prev[i] is the last item 
      // in a list for the ith item 
}; 

यह संरचना तथ्य पर आधारित है कि प्रत्येक आइटम कर सकते हैं केवल एक ही बाल्टी सूची में एक बार में रहें।

push(item, cost); // push an item onto the head of the appropriate bucket list 

_pop(item, cost); // _pop an item from (anywhere!) within a bucket list 

update(item, old_cost, new_cost); // move an item between buckets by combining 
            // push and _pop 

इस संरचना एक प्राथमिकता कतार के रूप में आप बस एक सूचकांक स्कैन करने के लिए वर्तमान न्यूनतम बाल्टी पर इशारा करते हुए बनाए रखने का उपयोग करें:

इस संरचना आप इन कार्यों के लिए बुरी से बुरी हालत O(1) जटिलता प्राप्त कर सकते हैं के आधार पर। जब आप अगली सबसे कम लागत वाली वस्तु प्राप्त करना चाहते हैं, तो आप बस इस बाल्टी से मुख्य आइटम पॉप करें। यदि बाल्टी खाली है तो आप अपनी बाल्टी इंडेक्स बढ़ाते हैं जब तक आपको एक खाली नहीं मिलता है।

बेशक अगर U अतिरिक्त अंतरिक्ष जटिलता बहुत बड़ा हो जाता है, और बाल्टी पर वस्तुओं के एक दुर्लभ वितरण की संभावना इस तरह के दृष्टिकोण को अनैतिक बना सकती है।