ন্যূনতম স্প্যানিং ট্রি (MST) কী?
একটি ন্যূনতম স্প্যানিং ট্রি (Minimum Spanning Tree - MST) বা ন্যূনতম ওজনযুক্ত স্প্যানিং ট্রি হল একটি সংযুক্ত, এজ-ওজনযুক্ত (un)directed গ্রাফের এজগুলির একটি উপসেট যা সাইকেল ছাড়াই সব শীর্ষবিন্দুকে সংযুক্ত করে এবং সম্ভাব্য ন্যূনতম মোট এজ ওজন সহ। অর্থাৎ, এটি একটি স্প্যানিং ট্রি যার এজ ওজনগুলোর যোগফল যতটা সম্ভব কম।
MST-এর মূল বৈশিষ্ট্যসমূহ
- সংযোগ: গ্রাফের সব নোড/শীর্ষবিন্দু সংযুক্ত থাকে
- চক্রবিহীন: কোনো সাইকেল বা লুপ থাকে না
- ন্যূনতম ওজন: সব এজের ওজন যোগফল ন্যূনতম
- স্প্যানিং: গ্রাফের সব শীর্ষবিন্দু কভার করে
প্রয়োগ ক্ষেত্র
MST নেটওয়ার্ক ডিজাইন, ক্লাস্টারিং, ইমেজ সেগমেন্টেশন, এবং অনুমান алгоритমে ব্যাপকভাবে ব্যবহৃত হয়।
প্রধান অ্যালগরিদম
- ক্রাস্কালের অ্যালগরিদম (Kruskal's Algorithm) - গ্রিডি পদ্ধতিতে এজ বাছাই করে
- প্রিমের অ্যালগরিদম (Prim's Algorithm) - একটি নোড থেকে শুরু করে বিস্তার করে
