के साथ न्यूनतम स्पैनिंग पेड़ अपडेट करें एक एमएसटी के साथ एक ग्राफ (सकारात्मक वजन किनारों) यदि कुछ किनारे, ई को नए मान में संशोधित किया गया है, तो एमएसटी को पूरी तरह से रीमेक किए बिना अपडेट करने का सबसे अच्छा तरीका क्या है। मुझे लगता है कि यह रैखिक समय में किया जा सकता है। साथ ही, ऐसा लगता है कि मुझे एक अलग एल्गोरिदम की आवश्यकता होगी कि 1) ई पहले से ही एमएसटी का हिस्सा है और 2) चाहे नया किनारा, ईकिनारे
मेरा ओ (एन) समाधान से बड़ा या छोटा है धारणा पर आधारित है, इससे पहले कि आप किनारों को संशोधित करना शुरू करें, आपको एमएसटी मिलना चाहिए (ग्राफ के साथ नहीं दिया गया है)। ऐसा करने के लिए, आप क्रस्कल एल्गोरिदम का उपयोग कर सकते हैं जो ओ (एन लॉग एन) में काम करता है, और एक दुष्प्रभाव के रूप में किनारों की क्रमबद्ध सूची उत्पन्न करता है। इसकी लागत को सॉर्ट करके नियंत्रित किया जाता है, इसलिए जब आप किनारे के वजन को संशोधित करते हैं, तो आप ओ (लॉग एन) में क्रमबद्ध सूची से इसे हटा सकते हैं, और ओ (लॉग एन) में भी इसे नए मान के साथ सम्मिलित कर सकते हैं, और अंततः क्रस्कल को कॉल करें एल्गोरिदम फिर से, जो अब रैखिक समय में चलता है क्योंकि किनारों को क्रमबद्ध किया जाता है।
यह अनुरोध किया गया है कि यह एक रैखिक समाधान है, लेकिन ऐसा लगता है कि इसे तेज़ी से किया जा सकता है।
4 मामलों के होते हैं:
एज MST में है और आप किनारे का मूल्य कम हो रही:
वर्तमान MST अभी भी MST
एज MST में नहीं है और आप कम हो रही किनारे का मूल्य:
इस किनारे को एमएसटी में जोड़ें। अब आपके पास बिल्कुल 1 चक्र है।
एमएसटी में cycle property के आधार पर आपको उस चक्र पर उच्चतम मूल्य के साथ किनारे को खोजने और निकालने की आवश्यकता है। आप इसे dfs या bfs का उपयोग करके कर सकते हैं। जटिलता ओ (एन)।
एज MST में है और आप बढ़त के अपने मूल्य में वृद्धि:
निकालें MST से इस बढ़त। अब आपके पास 2 कनेक्टेड घटक हैं जिन्हें कनेक्ट किया जाना चाहिए। आप ओ (एन) (बीएफएस या डीएफएस) में दोनों घटकों की गणना कर सकते हैं। आपको इन घटकों को जोड़ने वाले छोटे मूल्य के साथ किनारे को खोजने की आवश्यकता है। अपने मूल्य से आरोही क्रम में किनारों पर इटरेट करें। जटिलता ओ (एन)।
एज MST में नहीं है और आप बढ़त के अपने मूल्य में वृद्धि: जो हे नहीं है
वर्तमान MST अभी भी MST
मामला 3. ओ (एन) नहीं है। आरोही क्रम में किनारों पर फिर से शुरू करने के लिए। हमें उन्हें क्रमबद्ध करने की जरूरत है। ओ (एन^2) किनारों हैं। भले ही हम सॉर्ट किए गए किनारों को ले रहे हों, जिन्हें हमने एमएसटी बनाने के दौरान गणना की थी, फिर भी इन्हें इन सभी (सभी को सबसे बुरी स्थिति में) किनारों से गुजरना होगा। –
यह ओ (एन) हो सकता है। 1. किनारे को हटाएं जिसका वजन बढ़ गया था और इस किनारे से जुड़े दो नोड्स का ट्रैक रखें 2. इन दो नोड्स के साथ शुरू होने वाले बीएफएस/डीएफएस को चलाएं जो अब 2 अपवाद सेट में हैं। आपको किसी भी तरह से शिखर का दौरा किया जाना चाहिए ताकि आप उन्हें ओ (1) में एक्सेस कर सकें। मैं दो हैशटेबल बनाएगा, प्रत्येक डिजॉइंट सेट के लिए एक। 3. ई-ई में सभी किनारों के माध्यम से लूप जहां जी = (वी, ई) और एमएसटी = (वी, ई ')। यदि किसी किनारे में प्रत्येक हैशटेबल से 1 नोड होता है, तो यह दो अलग-अलग सेट जोड़ता है। यह तय करने के लिए एक न्यूनतम चर बनाए रखें कि किन किनारे से दो सेट जुड़े थे और सबसे कम वजन था। ओ (ई) – Olshansk
ओल्शांस्क, ओ (ई) ओ (एन^2) है, जैसा आशीष ने बताया।जहां तक मैं कह सकता हूं, हटाने के लिए ओ (एन^2) की आवश्यकता होती है, क्योंकि प्रत्येक किनारे के लिए (पहले से ही सूची में क्रमबद्ध मान लीजिए), हमें सबसे छोटे किनारे को खोजने की ज़रूरत है जो दो फैलाने वाले पेड़ों को जोड़ती है। यह ओ (एन^2) तक ले सकता है यदि उन्हें जोड़ने वाला एकमात्र किनारा भी उच्चतम मूल्य वाला किनारा है। –
Kruskal एल्गोरिथ्म आप संघ-लगता है की जरूरत है Unfortunetly है (1) ;/ –