data-structures
संघ-खोज डेटा संरचना

परिचय

सिद्धांत

संघ डेटा संरचनाओं को निम्नलिखित संचालन प्रदान करता है:

• make_sets(n) के साथ एक संघ-खोज डेटा संरचना initializes n एकमात्र
• find(i) तत्व के सेट के लिए एक प्रतिनिधि देता है i
• union(i,j) सेट सेट को i और j

हम प्रत्येक तत्व i लिए मूल तत्व parent[i] को संग्रहीत करके तत्वों के हमारे विभाजन को 0 से n - 1 तक दर्शाते हैं, जो अंततः i वाले सेट के प्रतिनिधि की ओर जाता है।
यदि कोई तत्व स्वयं एक प्रतिनिधि है, तो वह उसका अपना माता-पिता है, अर्थात parent[i] == i ।

इस प्रकार, यदि हम सिंगलटन सेट से शुरू करते हैं, तो प्रत्येक तत्व इसका अपना प्रतिनिधि है:

हम इन मूल बिंदुओं का अनुसरण करके किसी दिए गए सेट के लिए प्रतिनिधि पा सकते हैं।

आइए अब देखते हैं कि हम कैसे सेट को मर्ज कर सकते हैं:
यदि हम 0 और 1 के तत्वों और तत्वों 2 और 3 का विलय करना चाहते हैं, तो हम इसे 0 से 1 के माता-पिता को सेट करके और 2 से 3 के माता-पिता को सेट करके कर सकते हैं:

इस साधारण मामले में, केवल मूल माता-पिता पॉइंटर को ही बदलना होगा।
यदि हम बड़े सेट को मर्ज करना चाहते हैं, तो हमें हमेशा उस सेट के प्रतिनिधि के पैरेंट पॉइंटर को बदलना होगा जिसे दूसरे सेट में मर्ज किया जाना है: मर्ज (0,3) के बाद, हमने सेट के प्रतिनिधि के माता-पिता को सेट कर दिया है 3 वाले सेट के प्रतिनिधि को 0 युक्त

उदाहरण को थोड़ा और दिलचस्प बनाने के लिए, आइए अब विलय (4,5), (5,6) और (3,4) :

अंतिम धारणा जो मैं पेश करना चाहता हूं वह पथ संपीड़न है :
यदि हम एक सेट के प्रतिनिधि को ढूंढना चाहते हैं, तो हमें प्रतिनिधि तक पहुंचने से पहले कई मूल बिंदुओं का पालन करना पड़ सकता है। हम प्रत्येक सेट के लिए प्रतिनिधि को सीधे उनके मूल नोड में संग्रहीत करके इसे आसान बना सकते हैं। हम उस क्रम को खो देते हैं जिसमें हमने तत्वों को मिला दिया था, लेकिन संभावित रूप से एक बड़े क्रम में लाभ हो सकता है। हमारे मामले में, केवल पथ जो संकुचित नहीं हैं वे 0, 4 और 5 से 3 तक के पथ हैं:

मूल कार्यान्वयन

संघ-खोज डेटा संरचना का सबसे बुनियादी कार्यान्वयन एक सरणी parent होते हैं जो संरचना के प्रत्येक तत्व के लिए मूल तत्व का भंडारण करते हैं। एक तत्व के लिए इन माता-पिता 'संकेत' के बाद i हमें प्रतिनिधि के j = find(i) युक्त i ओर ले जाता है, जहाँ parent[j] = j धारण करते हैं।

using std::size_t;

class union_find {
private:
    std::vector<size_t> parent;  // Parent for every node

public:
    union_find(size_t n) : parent(n) {
        for (size_t i = 0; i < n; ++i)
            parent[i] = i;      // Every element is its own representative
    }

    size_t find(size_t i) const {
        if (parent[i] == i)     // If we already have a representative
            return i;           // return it
        return find(parent[i]); // otherwise return the parent's representative
    }

    void merge(size_t i, size_t j) {
        size_t pi = find(i);
        size_t pj = find(j);
        if (pi != pj) {        // If the elements are not in the same set: 
            parent[pi] = pj;   // Join the sets by marking pj as pi's parent
        }
    }
};

सुधार: पथ संपीड़न

यदि हम संघ-खोज डेटा संरचना पर कई merge संचालन करते हैं, तो parent बिंदुओं द्वारा दर्शाए गए मार्ग काफी लंबे हो सकते हैं। पथ संपीड़न , जैसा कि पहले से ही सिद्धांत भाग में वर्णित है, इस मुद्दे को कम करने का एक सरल तरीका है।

हम हर k -th मर्ज ऑपरेशन या कुछ समान के बाद पूरे डेटा संरचना पर पथ संपीड़न करने की कोशिश कर सकते हैं, लेकिन इस तरह के ऑपरेशन में काफी बड़ा रनटाइम हो सकता है।

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

size_t find(size_t i) const {
    if (parent[i] == i)          // If we already have a representative
        return i;                // return it
    parent[i] = find(parent[i]); // path-compress on the way to the representative
    return parent[i];            // and return it
}

सुधार: आकार द्वारा संघ

merge हमारे वर्तमान कार्यान्वयन में, हम हमेशा सेट के आकार को ध्यान में रखे बिना, सही सेट के बच्चे होने के लिए बाएं सेट का चयन करते हैं। इस प्रतिबंध के बिना, अपने प्रतिनिधि को एक तत्व से पथ (पथ संपीड़न के बिना) काफी लंबा हो सकता है, इस प्रकार पर बड़े runtimes के लिए अग्रणी find कॉल।

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

हम अपनी कक्षा में एक अतिरिक्त सदस्य std::vector<size_t> size संग्रहीत करते हैं, जो प्रत्येक तत्व के लिए 1 से आरंभिक हो जाता है। दो सेटों को मिलाते समय, बड़ा सेट छोटे सेट का जनक बन जाता है और हम दो आकारों को जोड़ते हैं:

private:
    ...
    std::vector<size_t> size;

public:
    union_find(size_t n) : parent(n), size(n, 1) { ... }

    ...

    void merge(size_t i, size_t j) {
        size_t pi = find(i);
        size_t pj = find(j);
        if (pi == pj) {            // If the elements are in the same set: 
            return;                // do nothing
        }
        if (size[pi] > size[pj]) { // Swap representatives such that pj
            std::swap(pi, pj);     // represents the larger set
        }
        parent[pi] = pj;           // attach the smaller set to the larger one
        size[pj] += size[pi];      // update the size of the larger set
    }

सुधार: रैंक द्वारा संघ

आकार के अनुसार संघ के बजाय आमतौर पर इस्तेमाल किया जाने वाला एक और अनुमानी रैंक है

इसका मूल विचार यह है कि हमें वास्तव में सेट के सटीक आकार को संग्रहीत करने की आवश्यकता नहीं है, आकार का एक अनुमान (इस मामले में: मोटे तौर पर सेट के आकार का लघुगणक) आकार द्वारा संघ के समान गति प्राप्त करने के लिए पर्याप्त है।

इसके लिए, हम एक सेट की रैंक की धारणा को पेश करते हैं, जो इस प्रकार है:

• सिंगलेट्स को रैंक 0 है
• यदि असमान रैंक वाले दो सेटों को मिला दिया जाता है, तो बड़े रैंक वाला सेट अभिभावक बन जाता है जबकि रैंक को अपरिवर्तित छोड़ दिया जाता है।
• यदि समान रैंक के दो सेट मर्ज किए जाते हैं, तो उनमें से एक दूसरे के माता-पिता बन जाते हैं (पसंद मनमानी हो सकती है), इसकी रैंक बढ़ जाती है।

रैंक द्वारा यूनियन का एक फायदा अंतरिक्ष उपयोग है: जैसे-जैसे अधिकतम रैंक लगभग बढ़ता जाता है सभी यथार्थवादी इनपुट आकारों के लिए, रैंक को एक बाइट में संग्रहीत किया जा सकता है ( n < 2^255 बाद से)।

रैंक द्वारा संघ का एक सरल कार्यान्वयन इस तरह दिखाई दे सकता है:

private:
    ...
    std::vector<unsigned char> rank;

public:
    union_find(size_t n) : parent(n), rank(n, 0) { ... }

    ...

    void merge(size_t i, size_t j) {
        size_t pi = find(i);
        size_t pj = find(j);
        if (pi == pj) {
            return;
        }
        if (rank[pi] < rank[pj]) {
            // link the smaller group to the larger one
            parent[pi] = pj;
        } else if (rank[pi] > rank[pj]) {
            // link the smaller group to the larger one
            parent[pj] = pi;
        } else {
            // equal rank: link arbitrarily and increase rank
            parent[pj] = pi;
            ++rank[pi];
        }
    }

अंतिम सुधार: आउट-ऑफ-बाउंड्स भंडारण के साथ रैंक द्वारा संघ

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

• हमें वास्तव में केवल प्रतिनिधियों के लिए रैंक को स्टोर करने की आवश्यकता है, अन्य तत्वों के लिए नहीं। इन प्रतिनिधियों के लिए, हमें parent को संग्रहीत करने की आवश्यकता नहीं है।
• अब तक, parent[i] अधिकांश size - 1 , अर्थात बड़े मान अप्रयुक्त हैं।
• सभी रैंक अधिकतम हैं ।

यह हमें निम्नलिखित दृष्टिकोण के लिए लाता है:

• शर्त के बजाय parent[i] == i , अब हम प्रतिनिधियों की पहचान करते हैं
  parent[i] >= size
• हम इन बाहर के मूल्यों सीमा के प्रतिनिधि के साथ सेट का उपयोग सेट की श्रेणी में स्टोर करने के लिए, यानी i रैंक है parent[i] - size
• इस प्रकार हम माता-पिता की सरणी को parent[i] = size बजाय parent[i] = i आरंभ करते हैं, अर्थात प्रत्येक सेट रैंक 0 के लिए अपना प्रतिनिधि है।

चूँकि हम केवल रैंक मानों को size से size , इसलिए हम केवल merge के कार्यान्वयन में parent वेक्टर द्वारा rank वेक्टर को बदल सकते हैं और केवल find में प्रतिनिधियों की पहचान करने वाली स्थिति का आदान-प्रदान करने की आवश्यकता है:

रैंक और पथ संपीड़न द्वारा संघ का उपयोग कर समाप्त कार्यान्वयन:

using std::size_t;

class union_find {
private:
    std::vector<size_t> parent;

public:
    union_find(size_t n) : parent(n, n) {} // initialize with parent[i] = n

    size_t find(size_t i) const {
        if (parent[i] >= parent.size()) // If we already have a representative
            return i;                   // return it
        return find(parent[i]);         // otherwise return the parent's repr.
    }

    void merge(size_t i, size_t j) {
        size_t pi = find(i);
        size_t pj = find(j);
        if (pi == pj) {
            return;
        }
        if (parent[pi] < parent[pj]) {
            // link the smaller group to the larger one
            parent[pi] = pj;
        } else if (parent[pi] > parent[pj]) {
            // link the smaller group to the larger one
            parent[pj] = pi;
        } else {
            // equal rank: link arbitrarily and increase rank
            parent[pj] = pi;
            ++parent[pi];
        }
    }
};