डिस्जिइंट सेट पर कौन से ऑपरेशन किए जा सकते हैं?

Question

मैंने अभी विवादित सेट डेटा संरचना का अध्ययन किया है और मुझे पता है कि इसे "यूनियन-फाइंड डेटा स्ट्रक्चर्स" भी कहा जाता है, यूनियन और खोज इस डेटा संरचना के दो मुख्य संचालन हैं। हम विवादित सेट पर संघ कर सकते हैं, इसी तरह हम खोज संचालन कर सकते हैं; मैं जानना चाहता हूं कि यूनियन को छोड़कर और अलग-अलग सेट पर हम कौन से अन्य ऑपरेशन कर सकते हैं।

Answer 1

डिस्जॉइंट सेट संरचना को "यूनियन-स्ट्रक्चर स्ट्रक्चर" भी कहा जाता है। तो union, find और MakeSet संचालन वैसे भी समर्थित होना चाहिए। अन्य परिचालन इस संरचना के बारे में नहीं हैं, और क्या वे समर्थित हैं कार्यान्वयन और आपके लक्ष्य पर निर्भर करता है। कभी-कभी आपको अतिरिक्त संचालन की अपनी परियोजना की जरूरतों को पूरा करने के लिए विशेष रूप से विशेष कार्यान्वयन चुनना होगा।

इसके अलावा अगर हम अन्य मूल सेट-संबंधित संचालन का समर्थन करते हैं तो यह अच्छा होगा। उन्हें बताना करते हैं:

• चौराहे दो की सेट। चूंकि सेट अलग हैं, यह हमेशा खाली रहता है जब तक कि ये दो सेट मेल नहीं खाते।
• यूनियन दो सेटों में से - बॉक्स से बाहर समर्थित।
• सेट से समर्थित तत्व प्राप्त करें, यह find का परिणाम होने की संभावना है।
• सेट से तत्व को हटाएं - कार्यान्वयन पर निर्भर करता है। जब सेट जंगल के रूप में लागू होते हैं, तो यह मुश्किल है और धीमे अतिरिक्त संचालन की आवश्यकता होती है। जब सेट लिंक्ड सूचियों के रूप में लागू होते हैं, तो यह आसान है।
• सेट की गणना करें, यानी दिए गए सेट में प्रत्येक तत्व को दोहराएं। यह फिर से कार्यान्वयन पर निर्भर करता है: लिंक्ड सूचियों के लिए यह आसान है, वन-जैसे कार्यान्वयन के लिए इसे समर्थन के लिए अतिरिक्त संरचनाओं की आवश्यकता होती है।

Answer 2

वेनिला संघ-खोज डेटा संरचना के साथ, आप वास्तविक सेट की गणना नहीं कर सकते हैं, इसलिए कई सेट ऑपरेशन उपलब्ध नहीं हैं। ऐसा इसलिए है क्योंकि वेनिला संस्करण में आपके पास केवल एक दिशा में पॉइंटर्स हैं --- नीचे दी गई तस्वीर में, प्रत्येक विकर्ण रेखा ऊपर तीर से मेल खाती है, और जड़ें (शीर्ष रेखा) सेट के लिए मूल वस्तुएं हैं:

 o [set1]   o [Set2] 
    /\    \ 
    o o    o 
/
o 

तो सभी वस्तुओं को खोजने, कहने, सेट करने का कोई तरीका नहीं है; उदाहरण के लिए, आप रूट नोड से पथ का पता नहीं लगा सकते हैं। आप पॉइंटर्स को नीचे भी देख सकते हैं, लेकिन यह डेटा संरचना को महत्वपूर्ण रूप से जटिल करता है क्योंकि किसी ऑब्जेक्ट में डेटा संरचना में माता-पिता की मनमानी संख्या हो सकती है। मेरी वस्तुओं ए और बी नहीं एक ही सेट के हैं या कार्य करें:

तो यह निम्नलिखित कार्यों के लिए वास्तव में ज्यादातर है:

• उत्तर के लिए?
• मर्ज सेट एस 1 और एस 2 ताकि सेट में सभी वस्तुओं को अब एक ही सेट

इस विस्तार करने के लिए से संबंधित माना जाता है, संघ-सेट डेटा संरचना के संचालन इसके समर्थन के लिए बहुत कम समय जटिलता है ; दोनों विलय सेट और एक ही सेट क्वेरी का जवाब देने के लिए निरंतर निरंतर समय (ओ (1)) लेते हैं; इस समय जटिलता के कारण, आप सभी सेट परिचालनों का समर्थन नहीं कर सकते हैं।उदाहरण के लिए, एक मानक सेट प्रतिनिधित्व एक [बाइनरी] खोज पेड़ द्वारा होता है, जहां अधिकांश परिचालनों में कम से कम ओ (लॉग एन) जटिलताएं होती हैं।

Answer 3

संघ-खोज डिस्जिइंट सेट संरचना का बिंदु प्राथमिक सेट ऑपरेशंस करने के बारे में इतना नहीं है, क्योंकि आपका प्रश्न और अन्य उत्तरदाता सुझाव दे रहे हैं। इसके बजाए, यह संरचना के अत्यधिक कुशल कार्यान्वयन के बारे में है कि कुछ एल्गोरिदम की आवश्यकता है। विशेष रूप से, जुड़े घटकों को ढूंढना और न्यूनतम स्पैनिंग पेड़ यूनियन-डिस्प्ले सेट के शीर्ष पर अपने सबसे कुशल कार्यान्वयन का निर्माण करते हैं।