এই পোস্টে, আমরা Prim's এবং Kruskal এর অ্যালগরিদমের মধ্যে পার্থক্য বুঝতে পারব।
মিনিমাম স্প্যানিং ট্রি (MST) এর জন্য Kruskal এর অ্যালগরিদম
- যখন একটি সংযুক্ত এবং অনির্দেশিত গ্রাফ দেওয়া হয়, তখন এই ধরনের গ্রাফের একটি স্প্যানিং ট্রি হল সাবগ্রাফ যা একটি গাছ যা সমস্ত শীর্ষবিন্দুকে সংযুক্ত করে৷
- একটি একক গ্রাফে একাধিক বিস্তৃত গাছ থাকতে পারে৷
- একটি ওজনযুক্ত, সংযুক্ত এবং অনির্দেশিত গ্রাফের জন্য একটি সর্বনিম্ন স্প্যানিং ট্রি (MST) (ন্যূনতম ওজন স্প্যানিং ট্রি হিসাবেও পরিচিত) হল একটি স্প্যানিং ট্রি যার ওজন অন্য প্রতিটি স্প্যানিং গাছের ওজনের চেয়ে কম বা সমান।
- স্প্যানিং গাছের প্রতিটি প্রান্তের সাথে যুক্ত ওজন যোগ করে একটি স্প্যানিং গাছের ওজন নির্ধারণ করা হয়।
- গ্রাফে সর্বনিম্ন ওজনের শীর্ষবিন্দু থেকে ন্যূনতম স্প্যানিং ট্রি তৈরি করা যেতে পারে৷
- একটি নোড শুধুমাত্র একবার অতিক্রম করা হয়।
- এটি বিরল গ্রাফে দ্রুত চলে।
- সময়ের জটিলতা হল O(E লগ V), যেখানে V হল শীর্ষবিন্দুর সংখ্যা।
- এটি সংযোগ বিচ্ছিন্ন উপাদানগুলির সাথেও কাজ করতে পারে৷
ক্রুসকালের অ্যালগরিদম ব্যবহার করে MST খোঁজার ধাপ:
- প্রান্তগুলিকে তাদের সম্পর্কিত ওজনের ক্রমবর্ধমান ক্রমে সাজান৷ ৷
- সবচেয়ে ছোট প্রান্তটি নির্বাচন করুন৷ ৷
- সেই সময় পর্যন্ত তৈরি হওয়া স্প্যানিং-ট্রির সাথে এটি একটি চক্র গঠন করে কিনা তা পরীক্ষা করে দেখুন।
- চক্রটি গঠিত না হলে, এই প্রান্তটি অন্তর্ভুক্ত করতে হবে।
- অন্যথায়, এটি বাতিল করা যেতে পারে।
- পদক্ষেপ 2,3,4 পুনরাবৃত্তি করা হয় যতক্ষণ না বিস্তৃত গাছটিতে V-1 প্রান্ত থাকে৷
প্রিমের অ্যালগরিদম মিনিমাম স্প্যানিং ট্রি (MST)
- এটি ক্রুসকালের অ্যালগরিদমের মতো, অর্থাৎ এটি একটি লোভী অ্যালগরিদম৷
- এটি একটি খালি বিস্তৃত গাছ দিয়ে শুরু হয়৷ শীর্ষবিন্দুর দুটি সেট বজায় রাখা হয়।
- প্রথম সেটে শীর্ষবিন্দুগুলি থাকবে যা ইতিমধ্যেই MST-তে অন্তর্ভুক্ত রয়েছে, যেখানে অন্য সেটে শীর্ষবিন্দুগুলি রয়েছে যা এখনও অন্তর্ভুক্ত করা হয়নি৷
- প্রতিটি ধাপে, অ্যালগরিদম সমস্ত প্রান্ত বিবেচনা করে যা দুটি সেটকে সংযুক্ত করবে। এটি তারপরে এই প্রান্তগুলির মধ্যে সর্বনিম্ন ওজন প্রান্তটি বেছে নেয়৷
- এই ধাপের পরে, অ্যালগরিদম MST ধারণ করে সেটের প্রান্তের অন্য প্রান্তে চলে যায়।
- গ্রাফের যেকোনো শীর্ষ থেকে ন্যূনতম স্প্যানিং ট্রি তৈরি করা যেতে পারে।
- সর্বনিম্ন দূরত্বের মান পেতে একটি নোড একাধিকবার ভ্রমণ করা হয়।
- এটির একটি সময় জটিলতা রয়েছে O(V2), যেখানে V হল শীর্ষবিন্দুর সংখ্যা। এই সময় জটিলতা ফিবোনাচি হিপস ব্যবহার করে O(E + log V) তে বাড়ানো যেতে পারে।
- এটি ঘন গ্রাফে দ্রুত চলে।
- এটি সংযুক্ত উপাদান দেয়, এবং শুধুমাত্র সংযুক্ত গ্রাফের সাথে কাজ করে।
প্রিমের অ্যালগরিদম ব্যবহার করে MST খোঁজার ধাপ:
- একটি mstSet তৈরি করা হয়েছে, যা ইতিমধ্যে MST-তে অন্তর্ভুক্ত শীর্ষবিন্দুগুলির ট্র্যাক রাখে৷
- ইনপুট গ্রাফের সমস্ত শীর্ষবিন্দুতে একটি মূল মান বরাদ্দ করা হয়।
- প্রাথমিকভাবে মূল মানগুলি 'INFINITE' হিসাবে বরাদ্দ করা হয়৷ ৷
- প্রথম শীর্ষবিন্দুতে মূল মান 0 বরাদ্দ করা হয়েছে যাতে এটি প্রথমে বাছাই করা যায়।
- যখন mstSet-এ সমস্ত শীর্ষবিন্দু অন্তর্ভুক্ত করা হয় না, তখন নিচের ধাপগুলি অনুসরণ করা হয়।
- একটি শীর্ষবিন্দু 'u' বেছে নেওয়া হয়েছে যা mstSet-এ উপস্থিত নয় এবং ন্যূনতম কী মানও রয়েছে৷
- এই 'u' এখন mstSet-এ অন্তর্ভুক্ত।
- 'u'-এর সমস্ত সন্নিহিত শীর্ষবিন্দুর মূল মান আপডেট করা হয়েছে।
- এটি সমস্ত সংলগ্ন শীর্ষবিন্দুর মাধ্যমে পুনরাবৃত্তি করে করা যেতে পারে।
- প্রতিটি সন্নিহিত শীর্ষবিন্দু 'v'-এর জন্য, যদি প্রান্ত 'u'-'v'-এর ওজন 'v'-এর পূর্ববর্তী কী মানের চেয়ে কম হয়, তাহলে কী মান 'u-v'-এর ওজন হিসাবে আপডেট করা হয় '।
