Implementing Kruskal’s Algorithm

এর আগে আমরা মিনিমাম স্প্যানিং ট্রী এর প্রিমস এলগোরিদম টা ইমপ্লীমেন্ট করেছিলাম, এইবার আমরা ক্রুসকাল এলগোরিদম টা ইমপ্লিমেন্ট করবো এবং ক্রুসকাল দিয়ে একটা প্রবলেম সল্ভ করে দেখব!

এই কোডের রেফারেন্স হলো শাফায়াত ভাইয়ার ব্লগ। কেউ যদি সেইটা না পড়ে এইখানে আসেন, তাহলে আগে সেখান থেকে পড়ে আসুন প্লীজ। আর যদি সেইখান থেকে পড়ে সব কিছু অলরেডি বুঝেই যান, তাহলে এই লেখা আপনার জন্য না।

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

struct hudai
{
    int u,v,w;
    bool operator < ( const hudai& p ) const
    {
        return w < p.w;
    }
};


int pr[MAXN];

vector<hudai>kop;

int findset(int r)
{
    if (pr[r]==r) return r;
    else return findset(pr[r]);
}
void makeset(int n)
{
    for(int i=1;i<=n;i++)pr[i]=i;
}
void Kruskal(int n)
{
    sort(kop.begin(),kop.end());

    makeset(n);

    int sum=0;
    for(int i=0;i<(int)kop.size();i++)
    {
        int u=findset(kop[i].u);
        int v=findset(kop[i].v);
        
        if(u!=v)
        {
            pr[u]=v;

            sum+=kop[i].w;

            printf("%d-%d\n",kop[i].u,kop[i].v);

        }
    }
    printf("%d\n",sum);
}

int main(){

    //freopen("in.txt","r",stdin);
    int n,m;
    cin>>n>>m;//n হলো node m হল এজ
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;//এজ আর ওয়েট নিলাম

        hudai aha;
        aha.u=u;
        aha.v=v;  
        aha.w=w;

        kop.push_back(aha);
    }
    Kruskal(n);

    return 0;

}

প্রথমে আমরা হুদাই টাইপের একটা ডাটাটাইপ বানালাম। এর পর এইখানে আমরা < অপারেটরকে ওভারলোড করে দিলাম। সি প্লাস প্লাসে ফাংশন ওভারলোডের মত অপারেটর ওভারলোডও করা যায়। ফাংশন ওভারলোডে যেমন একই নামের একাধিক ফাংশন থাকত, যাদের প্যারামিটার আলাদা…কারো ইন্টিজার, কারো ডাবল, এইখানেও আমরা অনেকটা একই কাজ করছি। ইন্টিজার টাইপের কিছু থাকলে সেটাকে < অপারেটর সহজেই তুলনা করে নিতে পারে।কিন্তু তা বাদে অন্য কোন টাইপের জিনিস আসলে?

এতখানি বুদ্ধি কম্পিউটারের থাকলে তো কোড করাই লাগত না ! আমাদের তাই বলে দিতে হবে কিসের বেসিসে আমরা তুলনা টা করবো!

আমরা তাই “hudai” টাইপের কোন অবজেক্ট যদি প্যারামিটার হিসেবে আসে তাহলে তাকে তার ওয়েটের ভ্যালু অনুসারে সাজাতে হবে- সেটাই বলে দিচ্ছি।

pr[MAXN] এরের ইনডেক্স হবে ভার্টেক্সগুলা , আর ভ্যালু গুলা রিপ্রেজেন্ট করবে সেইটা ভার্টেক্স কোন সেটের অন্তর্গত। দুইটা pr[প্রথম ভার্টেক্স] এবং pr[সেকেন্ড ভার্টেক্স] সমান হইলে আমরা বুঝব এরা একই সেটের অন্তর্গত, সো এদের মাঝে একটা সাইকেল আছে!

এইবারে কোপ হবে 😛 আমরা হুদাই টাইপের ডাটা টাইপ নিয়ে ভেক্টর বানালাম, যার নাম কোপ!

findset() ফাংশনের কাজ হলো একটা ইন্টিজার রিটার্ন করা, ইন্টিজার টা হবে সেই সেটের রিপ্রেজেন্টিটিভব।যদি দুইবার কল করা হয় আলাদা দুইটা ভার্টেক্স দিয়ে, এবং ভার্টেক্স দুইটা সেইম সেটের অন্তভুর্ক্ত হয়,তবে সেইম ইন্টিজার রিটার্ন করবে। ডিফারেন্ট সেটে ডিফারেন্ট ইন্টিজার রিটার্ন করবে।

এইবার ক্রুসকালে আসা যাক,প্রথমে আমরা ওয়েট অনুসারে এজ সর্ট করলাম।সেট বানালাম makeset() দিয়ে, এই ফাংশনটা প্রথমে প্রত্যেকটা ভার্টেক্স কে আলাদা আলাদা সেটে রাখবে, এবং সেই সেটের রিপ্রেজেন্টিটিভ সে নিজেই!

প্রত্যেকবার u and v তে দুইটা সেটের রিপ্রেজেন্টিটিভ গুলা এসাইন হবে, দুইটা সেটের রিপ্রেজেন্টিটিভ একই হলে, গ্রাফে সাইকেল আছে, ভিন্ন হইলে সাইকেল নাই। আর যদি সাইকেল না থাকে তাহলে একটা সেটের লেজে আরেকটা সেটের মাথা লাগায় দিবো, এখন দুইটা মিলে একটা সেট 😛

এরপর প্রতিবার যেই এজটা আসতেসে, সেই এজ আগের যোগফলের সাথে যোগ হচ্ছে আর সেই এজ প্রিন্ট হচ্ছে।

মেইন ফাংশনে হুদাই টাইপের একটা অবজেক্ট নিলাম… সেই অবজেক্টে এবার মানগুলো এসাইন করলাম।শেষে পুরা অবজেক্ট টাকে কোপের মাঝে ভরে দিয়ে (!) ক্রুসকালকে কল করলাম!! এবং আমাদের কাজ শেষ 😀

Prims Algorithm Implementation

মিনিমাম স্প্যানিং ট্রী বের করার যে কয়টা এলগরিদম আছে, তার মাঝে প্রিমস এলগোরিদম অনেক জনপ্রিয়!

প্রিমস এলগরিদম কি সেইটা জানা না থাকলে এইখানে ঢু মেরে আসতে পারেন।এবার আমরা এলগরিদমটাকে ইম্পলিমেন্ট করবো।

#include<bits//stdc++.h>
using namespace std;
int visited[1000]={0};
vector<int>edge[1000];
vector<int>cost[1000];
struct data
{  int v,w;
    bool operator < ( data p ) const {
        return w > p.w;
    }
};
int Prims(int src,int n)
{
    priority_queue<data>pq;
    int i,u,v,sum=0,j,p;
    for(i=0;i<n-1;i++)
    {
        u=src;
        visited[src]=1;

        for(j=0;j<edge[u].size();j++)
        {
            v=edge[u][j];
            if(visited[v]==0)
            {
                data D; D.v=v;
                D.w=cost[u][j];
                pq.push(D);
            }
        }
        while(visited[src]){
        data T=pq.top();pq.pop();
        src=T.v;p=T.w;
        }
        sum+=p;
        }
        return sum;
}
int main()
{
    freopen("in.txt","r",stdin);
    int n,e,n1,n2,w,i;
    scanf("%d %d",&n,&e);
    for(i=0;i<e;i++)
    {
        scanf("%d %d %d",&n1,&n2,&w);
        edge[n1].push_back(n2);
        edge[n2].push_back(n1);
        cost[n1].push_back(w);
        cost[n2].push_back(w);
    }
    printf("%d\n",Prims(1,n));
    return 0;
}

এইবার কোডে কি হচ্ছে সেটা দেখা যাক। যারা উপরের হেডারফাইলটির এর সাথে পরিচিত নন, তারা জেনে রাখুন এইটা এমন একটা হেডার ফাইল যা দিলে অটোমেটিক্যালি c++ এর সব হেডার ফাইল ইনক্লুড হয়ে যায়।

এরপর আমরা ডাটা নামের একটা স্ট্রাকচার ক্রিয়েট করলাম, যার মাঝে ইন্টিজার টাইপের ভার্টেক্স(u) আর সেই ভার্টেক্সে কে নিয়ে যে যে এজ গঠিত হবে তাদের ওয়েট(w) থাকবে। এর পর এইখানে আমরা < অপারেটরকে ওভারলোড করে দিলাম। সি প্লাস প্লাসে ফাংশন ওভারলোডের মত অপারেটর ওভারলোডও করা যায়। ফাংশন ওভারলোডে যেমন একই নামের একাধিক ফাংশন থাকত, যাদের প্যারামিটার আলাদা…কারো ইন্টিজার, কারো ডাবল, এইখানেও আমরা অনেকটা একই কাজ করছি। ইন্টিজার টাইপের কিছু থাকলে সেটাকে < অপারেটর সহজেই তুলনা করে নিতে পারে।কিন্তু তা বাদে অন্য কোন টাইপের জিনিস আসলে?

এতখানি বুদ্ধি কম্পিউটারের থাকলে তো কোড করাই লাগত না ! আমাদের তাই বলে দিতে হবে কিসের বেসিসে আমরা তুলনা টা করবো!

আমরা তাই “data” টাইপের কোন অবজেক্ট যদি প্যারামিটার হিসেবে আসে তাহলে তাকে তার ওয়েটের ভ্যালু অনুসারে সাজাতে হবে- সেটাই বলে দিচ্ছি।

এবার “data” টাইপের কোন প্রায়োরিটি কিউ ডিক্লেয়ার করলে সেটা অটোমেটিক্যালি ওয়েট অনুসারে ভার্টেক্সকে সর্ট করে রাখবে।বিশাল ভুমিকা শেষ হলো। এইবার কোডটা কিভাবে কাজ করে দেখা যাক।

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

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

for loop টা n-1 পর্যন্ত ঘুরার কারন হলো, আমরা সোর্স বাদে বাকী সব নোড গুলোর জন্য কাজ করবো।

প্রথমে আমরা সোর্সকে u নামের একটা ভ্যারিয়েবলে রাখলাম।তারপর এইটাকে ভিজিটেড করে দিলাম। এইবার এই সোর্সের সাথে কানেক্টেড সবগুলো ভার্টেক্স আর তাদের ওয়েট কে কিউ তে পুশ করব।আমাদের ভার্টেক্স যদি হয় A,B,C এবং এদের ওয়েট যথাক্রমে 5,4,3 হয় তাহলে কিউ তে সেগুলো কি অনুসারে থাকবে?

হ্যা… প্রথমে C এর পর B এবং শেষে A!

এবার while লুপটা কিভাবে কাজ করি তা দেখা যাক, যতক্ষন না পর্যন্ত নতুন একটা ভার্টেক্স না আসবে, লুপ টা চলতে থাকবে।নতুন ভার্টেক্সে Visited[সেই ভার্টেক্স] এর মান শুন্য থাকবে। তাই লুপ ব্রেক হবে … কিন্তু লুপ ব্রেক করার আগে আমরা একটা ভ্যারিয়েবলে সেই নতুন ভার্টেক্স আর যেই এজ টা নিচ্ছি তার ওয়েট সেইভ করে রাখছি।

এইভাবে n-1 পর্যন্ত লুপ চললে আমরা মিনিমাম স্প্যানিং ট্রি এর ওয়েট টা পেয়ে যাব। এই কোডটা যদি বুঝে থাকেন, তাহলে আপনাদের কাজ হবে মিনিমাম স্প্যানিং ট্রি এর এজ গুলো ও প্রিন্ট করা। সে জন্য আমাদের স্ট্রাকচারে আরো একটা ভার্টেক্স রাখতে হবে !

আমি প্রোগ্রামিং এ ভালো নই, এইখানে কোন ভুল থাকলে ভুল ধরিয়ে দিলে খুশী হবো। কোন কিছু বুঝতে সমস্যা হলে নিচে কমেন্ট করুন অথবা ইনবক্সে ম্যাসেজ দিতে পারেন। ফেসবুকে আমি