Kruskal Algorithm

ক্রুসকাল এলগোরিদম  দিয়ে আমরা সহজেই মিনিমাম স্প্যানিং ট্রি বের করতে পারি। ক্রুসকাল সম্পর্কে বিস্তারিত বলার আগে কিছু ডেফিনেশন জানিয়ে দেই।

একটি গ্রাফ থেকে কিছু নোড ও এজ নিয়ে আমরা সাব গ্রাফ তৈরি করতে পারি। স্প্যানিং ট্রি ও এক ধরণের সাব গ্রাফ যাতে মূল গ্রাফের সব নোড গুলো আছে কিন্তু এজ থাকবে n-1 টি যেখানে n হচ্ছে নোড সংখ্যা। একটি গ্রাফ থেকে অনেক গুলো স্প্যানিং ট্রি তৈরী করা যায়, যে স্প্যানিং ট্রি এর এজের ওয়েইটের যোগফল সর্বনিম্ন হবে তাকে  মিনিমাম স্প্যানিং ট্রি বলে। ট্রি তে সাইকেল থাকতে পারে না। 

যখন কোন গ্রাফে কোন নোড থেকে ট্রাভার্স শুরু করে বিভিন্ন এজ ট্রাভার্স করে আবার সেই নোডে ফিরে আসা যায় তাকে সাইকেল বলে।

উপরের গ্রাফটি দিয়ে ক্রুসকাল এলগোরিদম বুঝতে চেষ্টা কর। উপরের গ্রাফের এজগুলোকে প্রথমে ওয়েইট এর উপর ভিত্তি করে ছোট থেকে বড় এই অর্ডারে সাজাই। এরপর নিচের স্টেপগুলো এক্সেকিউট করব-

1. দুটি নোডের মধ্যে যে এজের ওয়েইট কম সেটি আগে নিব অর্থাৎ ওই দুটি নোড ওই এজ দ্বারা কানেক্ট করব।
2. দুটি নোডের মধ্যে যে এজের ওয়েইট বেশি সেটি পরে নিব অর্থাৎ ওই দুটি নোড ওই এজ দ্বারা কানেক্ট করব না 
3. দুটি এজের ওয়েইট সমান হলে যে কোন একটি নিব
4. এভাবে নোড গুলো কানেক্ট করার সময় যাতে সাইকেল তৈরী না হয় সেটি খেয়াল রাখতে হবে।

এখন AD ও CE দুটি এজেরই ওয়েইট সর্বনিম্ন। যেকোন একটি নেয়া যাবে। আমরা AD নিব।

 এরপর CE কে নেই

এরপর DF কে নেই

এরপর AB কে নেই

এরপর BE কে নেই

এখন BC ও EF কে নিব না কারন গ্রাফে সাইকেল তৈরি হবে। এরপর EG কে নেই

এখন BD, FG ও DE কে নিব না কারন গ্রাফে সাইকেল তৈরি হবে। এই অবস্থায় আমরা যে স্প্যানিং ট্রি টি পেলাম এটিই মিনিমাম স্প্যানিং ট্রি (MST)। 

ক্রুসকাল এলগোরিদম এর কনসেপ্ট আশা করি বুঝতে পেরেছ। আমরা যখন কোন এজ নেয়, এবং দুটি নোডের মধ্যে কানেক্ট করি, তখন ওই দুই নোডের মধ্যে পথ আছে কিনা তা জানা জরুরি। এটি আমরা ডিসজয়েন্ট সেট এলগোরিদম থেকে জানতে পারি। আমরা ক্রুসকাল এলগোরিদম এর ইম্প্লিমেন্টেশনে ডিসজয়েন্ট সেট এর কনসেপ্ট ব্যবহার করব। তাই ডিসজয়েন্ট সেট নিয়ে ইউটিউবের টিউটোরিয়ালটি আগে দেখে এসো-

Code:

/*  Kruskal */

#include <bits/stdc++.h>
using namespace std;

struct edge
{
    int u;
    int v;
    int w;
};

bool cmp(edge a, edge b)
{
    return a.w<b.w;
}

int pr[100],n,m;
edge c[100];

int find_set(int r) //parent find
{
    if(pr[r]==r)
        return r;
    else
        find_set(pr[r]);
}

int kruskal()
{
    sort(c,c+m,cmp); //sorting edges according to cost

    for(int i=1; i<=n; i++)
    {
        pr[i]=i;
    }

    int cnt=0,mst=0;

    for(int i=0; i<m && cnt<n-1; i++)
    {
        int u=find_set(c[i].u);
        int v=find_set(c[i].v);

        if(u!=v)
        {
            printf("%d %d %d\n",c[i].u, c[i].v, c[i].w);
            mst+=c[i].w;
            pr[u]=v;
            cnt++;
        }
    }
    return mst;
}

int main()
{
    scanf("%d%d", &n, &m);// n is number of nodes, m is number of edges

    for(int i=0; i<m; i++)
    {
        int u,v,w;
        scanf("%d%d%d", &u, &v, &w);
        edge input;
        input.u=u;
        input.v=v;
        input.w=w;
        c[i]=input;
    }

    printf("Minimum Spanning tree :\n");
    printf("%d", kruskal());
    return 0;
}

/*
Input:
7 11
1 2 7
1 4 5
2 3 8
2 4 9
2 5 7
3 5 5
4 5 15
4 6 6
5 6 8
5 7 9
6 7 11
*/

ক্রুসকাল এলগোরিদম রিলেটেড প্রোগ্রামিং প্রবলেম Link- UVA 11631-Dark Roads