মডিউল ১০_৫ঃ Union and Union by Size

আগের ডকুমেন্টে আমরা find এলগোরিদমের ইমপ্লিমেন্টেশন দেখেছিলাম। এখন আমরা দেখবো union এলগোরিদম কিভাবে কাজ করে।

আমরা জানি যে দুইটা নোড এর মধ্যে লিডার সিলেক্ট করার প্রক্রিয়া হচ্ছে union।

তাহলে আমরা union এর ক্ষেত্রে করব যে দুইটা নোড এর লিডার খুঁজে বের করব। তারপর যেকোনো একটা লিডার এর প্যারেন্ট হিসেবে আরেকটা লিডারকে সেট করে দেব।

যেমনঃ

ধরি এখানে ২ আর ৬ এর union করতে চাই। তাহলে প্রথমে ২ এর লিডার খুঁজে বের করব যা হচ্ছে ১। আর ৬ এর লিডার খুঁজে বের করব যা হচ্ছে ৪। এবার ১ এর প্যারেন্ট হিসেবে ৪ কে সেট করে দিব(আমরা চাইলে উলটো ও করতে পারি)। তাহলে ৪ হয়ে যাবে এখন পুরো গ্রুপের লিডার।

// Some code
void dsu_union(int node1, int node2)
{
    // bad
    int leaderA = dsu_find(node1);
    int leaderB = dsu_find(node2);
    par[leaderA] = leaderB;
}

কিন্তু এখানে একটি সমস্যা আছে। যদি আমার অনেক বড় গ্রাফ হয় তাহলে লিডার খুঁজে আপডেট করার জন্য অনেক ট্রাভারস করতে হবে।

এটিকে অপ্টিমাইজ করা পসিবল ২টা পদ্ধতিতেঃ

১। Union By Size

২। Union By Rank

এইখানে আমরা শুধু union by size সম্পর্কে জানবো। union by rank নেক্সট ডকুমেন্টে দেখবো।

union by size এর লজিকটা খুবই সোজা। দুইটা গ্রুপের মধ্যে যেটা বড় গ্রুপ সেটার লিডারকে ছোট গ্রুপের লিডার হিসেবে সেট করব। যেমন উপরের এক্সাম্পল্টারে ১ আর ৪ এর মধ্যে আমরা ১ কে লিডার বানাইতাম কারন সেই গ্রুপের সাইজ ৪ আর পরেরটার সাইজ ৩। সেই ক্ষেত্রে যে গ্রুপ এর লিডার অন্য গ্রুপের লিডার হবে সেই গ্রুপের সাইজ লিডার গ্রুপের সাথে যোগ হয়ে যাবে।

// Some code
void dsu_union_by_size(int node1, int node2)
{
    int leaderA = dsu_find(node1);
    int leaderB = dsu_find(node2);
    if (group_size[leaderA] > group_size[leaderB])
    {
        par[leaderB] = leaderA;
        group_size[leaderA] += group_size[leaderB];
    }
    else
    {
        par[leaderA] = leaderB;
        group_size[leaderB] += group_size[leaderA];
    }
}