এই পোস্টে আমরা প্রিমস (Prim's) এবং ক্রুস্কালস (Kruskal's) অ্যালগরিদমের পার্থক্য বুঝব।
ক্রুস্কালস অ্যালগরিদম মিনিমাম স্প্যানিং ট্রি (MST) জন্য
- যদি একটি কানেক্টেড এবং আনডাইরেক্টেড গ্রাফ দেওয়া থাকে, তবে সে গ্রাফের একটি স্প্যানিং ট্রি হলো সাবগ্রাফ যা একটি ট্রি যা সকল ভার্টেক্স কানেক্ট করে।
- একটি সিঙ্গল গ্রাফের একাধিক স্প্যানিং ট্রি থাকতে পারে।
- একটি ভ্যারিয়েটেড, কানেক্টেড এবং আনডাইরেক্টেড গ্রাফের জন্য একটি মিনিমাম স্প্যানিং ট্রি (MST) (একেও মিনিমাম ওয়েইট স্প্যানিং ট্রি বলা হয়) হলো একটি স্প্যানিং ট্রি যার ওয়েইট অন্যান্য সকল স্প্যানিং ট্রির চেয়ে কম বা সমান।
- একটি স্প্যানিং ট্রির ওয়েইট নির্ধারণ করা হয় স্প্যানিং ট্রির প্রতিটি এজের সাথে জড়িত ওয়েইট যোগ করে।
- মিনিমাম স্প্যানিং ট্রি গ্রাফের সাবচেয়ে কম ওয়েইট والے ভার্টেক্স থেকে বিল্ড করা যায়।
- এক নোড শুধু একবার ট্রাভার্স করা হয়।
- এটি স্পার্স গ্রাফে (sparse graphs) দ্রুত চলে।
- টাইম কমপ্লেক্সিটি O(E log V), যেখানে V হলো ভার্টেক্সের সংখ্যা।
- এটি ডিসকানেক্টেড কম্পোনেন্টের সাথে ও কাজ করতে পারে।
ক্রুস্কালস অ্যালগরিদম দিয়ে MST খুঁজার স্টেপস:
- এজগুলো তাদের জড়িত ওয়েইটের অর্ডারে সর্ট করুন।
- সাবচেয়ে ছোট এজটি সিলেক্ট করুন।
- চেক করুন এটি স্প্যানিং ট্রির সাথে সাইকেল ফর্ম করে কিনা যা সেই পয়েন্ট পর্যন্ত ফর্ম করা হয়েছে।
- যদি সাইকেল ফর্ম না হয়, তবে এই এজটি ইনক্লুড করতে হবে।
- অন্যথায়, এটিকে ডিসকার্ড করা যায়।
- স্টেপ ২, ৩, ৪ রিপিট করুন যতক্ষণ না স্প্যানিং ট্রিতে V-1 টি এজ থাকে।
প্রিমস অ্যালগরিদম মিনিমাম স্প্যানিং ট্রি (MST) জন্য
- এটি ক্রুস্কালস অ্যালগরিদমের মতো, অর্থাৎ এটি একটি লালচী অ্যালগরিদম (greedy algorithm)।
- এটি একটি খালি স্প্যানিং ট্রি দিয়ে শুরু হয়। দুটি সেট ভার্টেক্স মেইনটেইন করা হয়।
- প্রথম সেটে হবে সেই ভার্টেক্সগুলো যা ইতিমধ্যে MST-এ ইনক্লুডেড, আর দ্বিতীয় সেটে হবে সেগুলো যা এখনো ইনক্লুডেড নয়।
- প্রতিটি স্টেপে, অ্যালগরিদম সকল এজ কনসিডার করে যেগুলো দুটি সেট কানেক্ট করবে। এখান থেকে মিনিমাম ওয়েইট এজটি পিক করে।
- এই স্টেপের পর, অ্যালগরিদম MST-वाले সেটের এজের অদর এন্ডপয়েন্টে মুভ করে।
- মিনিমাম স্প্যানিং ট্রি গ্রাফের যেকোনো ভার্টেক্স থেকে বিল্ড করা যায়।
- এক নোড মাল্টিপল বার ট্রাভার্স করা হয় মিনিমাম ডিস্ট্যান্স ভ্যালু পাওয়ার জন্য।
- এটির টাইম কমপ্লেক্সিটি O(V²), যেখানে V হলো ভার্টেক্সের সংখ্যা। এই টাইম কমপ্লেক্সিটি ফিবোনাচ্চি হিপ (Fibonacci heaps) ব্যবহার করে O(E + log V) এ আপগ্রেড করা যায়।
- ডেন্স গ্রাফে (dense graphs) এটি দ্রুত চলে।
- এটি কানেক্টেড কম্পোনেন্ট দেয়, এবং শুধু কানেক্টেড গ্রাফের সাথে কাজ করে।
প্রিমস অ্যালগরিদম দিয়ে MST খুঁজার স্টেপস:
- একটি mstSet তৈরি করা হয়, যা MST-এ ইতিমধ্যে ইনক্লুডেড ভার্টেক্স ট্র্যাক করে।
- ইনপুট গ্রাফের সকল ভার্টেক্সের একটি কি ভ্যালু অ্যাসাইন করা হয়।
- কি ভ্যালুগুলো প্রাথমিকভাবে 'INFINITE' হিসেবে অ্যাসাইন করা হয়।
- প্রথম ভার্টেক্সের কি ভ্যালু ০ অ্যাসাইন করা হয় যাতে সেটি প্রথমে পিক করা যায়।
- যখন mstSet সকল ভার্টেক্স ইনক্লুড করে না, তখন নিচের স্টেপগুলো ফলো করা হয়:
- একটি ভার্টেক্স 'u' চয়ন করা হয় যা mstSet-এ নেই এবং যার মিনিমাম কি ভ্যালু আছে।
- এই 'u' কে এখন mstSet-এ ইনক্লুড করা হয়।
- 'u'-র সকল এডজাসেন্ট ভার্টেক্সের কি ভ্যালু আপডেট করা হয়।
- এটি করা যায় সকল এডজাসেন্ট ভার্টেক্সের মাধ্যমে ইটারেট করে।
- প্রতিটি এডজাসেন্ট ভার্টেক্স 'v'-র জন্য, যদি এজ 'u'-'v'-র ওয়েইট 'v'-র পূর্বের কি ভ্যালু থেকে কম হয়, তবে কি ভ্যালু আপডেট করা হয় 'u-v'-র ওয়েইট হিসেবে।
