ক্রুসকাল অ্যালগরিদম

Spanning Tree হল এমন একটি  সাবগ্রাফ যেখানে মূলগ্রাফের সবগুলো নোড থাকে এবং n-1 সংখ্যক এজ থাকে কিন্তু কোন সাইকেল থাকে না। n যেখানে হল নোডসংখ্যা।একটা গ্রাফের অনেকগুলো Spanning Tree হতে পারে,কিন্তু তাদের মধ্যে যে Spanning Tree এর এজগুলোর কস্ট/ওয়েট এর যোগফল সবচেয়ে কম সেটিই হল  Minimum Spanning Tree(MST)/Minimum Weight Spanning Tree.

Minimum Spanning Tree(MST) বের করার দুইটা অ্যালগরিদম আছে, ক্রুসকাল এবং প্রিমস অ্যালগরিদম।এখানে আমরা দেখব ক্রুসকাল অ্যালগরিদম দিয়ে কিভাবে Minimum Spanning Tree(MST) বের করা যায়। এ সম্পর্কে বিশদভাবে জানার জন্য শাফায়েত ভাইয়ের ব্লগের বিকল্প নাই।