Kruskal’s Algorithm [ Minimum Spanning Tree ]

আজ আমরা মিনিমাম স্প্যানিং ট্রি বের করার এলগরিদম শিখবো । মিনিমাম স্প্যানিং ট্রি বের করার দুইটা এলগরিদম আছে । Kruskal’s এবং Prim’s এলগরিদম । দুইটাই Greedy এলগরিদম । তবে আজ আমরা Kruskal’s এলগরিদম নিয়ে আলোচনা করবো।

স্প্যানিং ট্রিঃ স্প্যানিং ট্রি হচ্ছে এমন একটি সাবগ্রাফ যেখানে মূল গ্রাফের সবগুলো নোড বিদ্যমান থাকবে এবং গ্রাফে এজ সংখ্যা হবে নোড সংখ্যা থেকে এক কম। তার মানে মূল গ্রাফের নোড সংখ্যা যদি n হয় তাহলে স্প্যানিং ট্রি এর নোড সংখ্যাও হবে n এবং এজ সংখ্যা হবে n-1 টি।

কোন গ্রাফের যদি n টি নোড এবং n-1 টি এজ থাকে তাহলে তাকে ট্রি বলে । ট্রিতে কোন সাইকেল থাকে না ।

এখন একটি গ্রাফের অনেকগুলো স্প্যানিং ট্রি থাকতে পারে তাই যে স্প্যানিং ট্রি এর এজগুলোর কস্ট/ওয়েটের যোগফল মিনিমাম সেই স্প্যানিং ট্রিকে মিনিমাম স্প্যানিং ট্রি বলে।

Kruskal’s Algorithm : এখন আমরা Kruskal’s Algorithm এর মাধ্যেমে মিনিমাম স্প্যানিং ট্রি বের করবো। আমি আগেই বলেছি Kruskal’s একটি Greedy এলগরিদম । Greedy মানে হচ্ছে লোভি । আর লোভিরা কি করেন?যেভাবে তার লাভ বেশী হবে সেই উপায় কাজ করেন । আমরাও তাই করবো ।

আমরা যেহেতু Greedy এলগরিদম করছি , তার মানে আমাদের প্রতিটা স্টেপের চয়েজ ওই সময়ের জন্য বেষ্ট হতে হবে। এবং তারপর সবগুলো স্টেপের পর আমরা আমাদের বেষ্ট উত্তর পাবো । মূলত এটাই গ্রিডির মূলনীত ।

যেহেতু আমরা একটি গ্রাফ থেকে মিনিমাম স্প্যানিং ট্রি বিল্ড করবো । তারমানে আমরা মিনিমাম কস্টের/ওয়েটের এজগুলো কে নিয়ে একটি ট্রি বিল্ড করবো যেখানে আমরা খেয়াল করবো যাতে ট্রিতে কোন লুপ / সাইকেল তৈরি হয়ে না যায়।

এতক্ষণ বকবক এর পর এখন আসি আমরা এলগরিদমেঃ

১। প্রথমে মূল গ্রাফের এজগুলোকে কস্টের/ ওয়েটের ভিত্তিতে ইনক্রিজিং অর্ডারে সর্ট করবো । যাতে করে আমরা মিনিমাম কস্টের / ওয়েটের এজকে পেতে পারি।

২। তারপর আমরা চেক করবো এই মিনিমাম কস্টের / ওয়েটের এজটি নেওয়ার ফলে আমাদের ট্রিতে কোন সাইকেল/লুপ তৈরি হয়ে যাচ্ছে কিনা । যদি লুপ/সাইকেল তৈরি হয় তাহলে সেই এজটা নিবোনা । অন্যথায় সেই এজটি আমাদের মিনিমাম স্প্যানিং ট্রিতে যুক্ত করবো।

এই লুপ/সাইকেল আছে কিনা সেটা আমরা খুব সহজেই চেক করতে পারি Union Find ডাটা স্ট্রাকচার ব্যাবহার করে । যদি Union Find সম্পর্কে আগে না জেনে থাকো তাহলে এখানে গিয়ে জেনে আসতে হবে।

৩। ট্রি এর সংজ্ঞা অনুসারে যতক্ষন না n-1 পরিমান এজ আমাদের মিনিমাম স্প্যানিং ট্রিতে যুক্ত হচ্ছে ততক্ষন আমরা একই ভাবে আগাতে থাকবো।

এভাবে আমরা একটি গ্রাফ থেকে মিনিমাম স্প্যানিং ট্রি পেতে পারি।

উদাহরণঃ ( আমি অলস তাই নিজে কষ্ট করে চিত্র না একে geeksforgeeks থেকে উদাহরণ এবং চিত্র নিলাম)

মনে করি আমাদের একটি গ্রাফ দেওয়া আছে এমনঃ

এখন এই গ্রাফ থেকে আমরা মিনিমাম স্পেনিং ট্রি বিল্ড করবো । তাই আমাদের এলগরিদমের স্টেপ অনুযায়ী প্রথমেই সবগুলো এজকে কস্টের/ ওয়েটের ভিত্তিতে সর্ট করে নেই ।

After sorting:
Src    Dest    Weight
7      6        1
8      2        2
6      5        2
0      1        4
2      5        4
8      6        6
2      3        7
7      8        7
0      7        8
1      2        8
3      4        9
5      4       10
1      7       11
3      5       14

• এখন আমরা মিনিমাম ওয়েটের এজ 7← → 6 কে নিয়ে নিলাম । যা কোন সাইকেল তৈরি করে না , তাই এটা নিবো আমরা ।

• তারপর আমরা মিনিমাম ওয়েটের এজ 8← → 2 কে নিয়ে নিলাম । যা কোন সাইকেল তৈরি করে না , তাই এটাও নিবো আমরা ।

• তারপর আমরা মিনিমাম ওয়েটের এজ 6← → 5 কে নিয়ে নিলাম । যা কোন সাইকেল তৈরি করে না , তাই এটাও নিবো।

• তারপর আমরা মিনিমাম ওয়েটের এজ 0← → 1 কে নিয়ে নিলাম । যা কোন সাইকেল তৈরি করে না , তাই এটাও নিবো।

• তারপর আমরা মিনিমাম ওয়েটের এজ 2← → 5 কে নিয়ে নিলাম । যা কোন সাইকেল তৈরি করে না , তাই এটাও নিবো।

• এই মুহুর্তে আমাদের হাতে মিনিমাম ওয়েটের এজ হচ্ছে 8← → 6 যার ওয়েট 6 কিন্তু এই এজটা আমরা নিবোনা । কেননা, এই এজটাকে নিলে আমাদের গ্রাফে সাইকেল ক্রিয়েট হচ্ছে তাই আমরা এই এজটা স্কিপ করে পরের এজে চলে যাবো।
• এখন আমরা মিনিমাম ওয়েটের এজ 2← → 3 কে নিয়ে নিলাম । যা কোন সাইকেল তৈরি করে না , তাই এটাও নিবো।

• এখন আমাদের হাতে থাকা মিনিমাম ওয়েটের এজ 7← → 8 হলেও তা সাইকেল ক্রিয়েট করে তাই এটাকেও স্কিপ করবো আমরা।
• এখন আমরা মিনিমাম ওয়েটের এজ 0← → 7যার ওয়েট 8কে নিয়ে নিলাম । যা কোন সাইকেল তৈরি করে না , তাই এটাও নিবো।

• এখন আমরা মিনিমাম ওয়েটের এজ 3← → 4 কে নিয়ে নিলাম । যা কোন সাইকেল তৈরি করে না , তাই এটাও নিবো।

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

এখন যে স্প্যানিং ট্রি আমরা পেয়েছি তার সবগুলো এজ এর যোগফল 37 যা মিনিমাম।

তাই এটিই আমাদের কাঙ্ক্ষিত মিনিমাম স্প্যানিং ট্রি । :)

আশাকরি সবার এতক্ষণে সম্পুর্ন এলগরিদম কিলিয়ার হয়ে গেছে । যদি সমস্যা হয় তাহলে খাতা-কলমে আঁকা আঁকি করে দেখতে পারো।

Code Implementation:

• ** প্রথমে গ্রাফ ইনপুট নিয়ে এজগুলো সর্ট করে নিবো । তারপর Union Find এর মাধ্যমে দেখবো এটা নিলে কি MST তে সাইকেল/লুপ হয়ে যাচ্ছে কিনা । কোডে কমেন্টে করে ইনফরমেশন এড করে দিয়েছি তাই আশাকরি সমস্যা হবে না।

CODE:

Kruskal’s Algorithm Complexity :

সবগুলো এজ সর্ট করতে Complexity O(E log E) + প্রতিটা এজ নিয়ে নিয়ে চেক করছি তার Complexity O(E).

Total : O(E log E)+O(E) = O(E log E).

আজকে এই পর্যন্তই । সামনে দেখা হবে Prim’s এলগরিদম নিয়ে । এবং দুইটা এলগরিদম এর মধ্যে পার্থক্য এবং কখন কোন এলগরিদম ব্যাবহার করবো তা নিয়ে লিখবো।

হ্যাপি কোডিং :)