ক্রসকাল বনাম প্রাইম
কম্পিউটার বিজ্ঞানে, Prim's এবং Kruskal এর অ্যালগরিদম হল একটি লোভী অ্যালগরিদম যা একটি সংযুক্ত ওজনযুক্ত অনির্দেশিত গ্রাফের জন্য একটি ন্যূনতম স্প্যানিং ট্রি খুঁজে পায়। একটি স্প্যানিং ট্রি হল একটি গ্রাফের একটি সাবগ্রাফ যাতে গ্রাফের প্রতিটি নোড একটি পথ দ্বারা সংযুক্ত থাকে, যা একটি গাছ। প্রতিটি বিস্তৃত গাছের একটি ওজন আছে, এবং সমস্ত বিস্তৃত গাছের ন্যূনতম সম্ভাব্য ওজন/মূল্য হল ন্যূনতম স্প্যানিং ট্রি (MST)।
প্রিমের অ্যালগরিদম সম্পর্কে আরও
অ্যালগরিদমটি চেক গণিতবিদ Vojtěch Jarník দ্বারা 1930 সালে এবং পরে স্বাধীনভাবে 1957 সালে কম্পিউটার বিজ্ঞানী রবার্ট সি. প্রিম দ্বারা তৈরি করা হয়েছিল। এটি 1959 সালে এডজার ডিজকস্ট্রা দ্বারা পুনঃআবিষ্কৃত হয়েছিল। অ্যালগরিদমটিকে তিনটি মূল ধাপে বলা যেতে পারে;
ন নোড সহ সংযুক্ত গ্রাফ দেওয়া হয়েছে এবং প্রতিটি প্রান্তের নিজ নিজ ওজন আছে, 1. গ্রাফ থেকে একটি স্বেচ্ছাচারী নোড নির্বাচন করুন এবং এটিকে ট্রি T-এ যোগ করুন (যা প্রথম নোড হবে)
2. গাছের নোডের সাথে সংযুক্ত প্রতিটি প্রান্তের ওজন বিবেচনা করুন এবং সর্বনিম্ন নির্বাচন করুন। T গাছের অন্য প্রান্তে প্রান্ত এবং নোড যোগ করুন এবং গ্রাফ থেকে প্রান্তটি সরান। (দুই বা ততোধিক ন্যূনতম বিদ্যমান থাকলে যেকোনো নির্বাচন করুন)
৩. ধাপ 2 পুনরাবৃত্তি করুন, যতক্ষণ না গাছে n-1 প্রান্ত যোগ করা হয়।
এই পদ্ধতিতে, গাছটি একটি একক আরবিট্রারি নোড দিয়ে শুরু হয় এবং প্রতিটি চক্রের সাথে সেই নোড থেকে প্রসারিত হয়। তাই, অ্যালগরিদম সঠিকভাবে কাজ করার জন্য, গ্রাফটিকে একটি সংযুক্ত গ্রাফ হতে হবে। প্রাইমের অ্যালগরিদমের মৌলিক রূপের সময় জটিলতা রয়েছে O(V2)।
ক্রসকালের অ্যালগরিদম সম্পর্কে আরও
জোসেফ ক্রুস্কালের তৈরি অ্যালগরিদমটি 1956 সালে আমেরিকান ম্যাথমেটিকাল সোসাইটির কার্যপ্রণালীতে উপস্থিত হয়েছিল। ক্রুসকালের অ্যালগরিদম তিনটি সহজ ধাপেও প্রকাশ করা যেতে পারে।
ন নোড এবং প্রতিটি প্রান্তের নিজ নিজ ওজন সহ গ্রাফ দেওয়া হয়েছে, 1. পুরো গ্রাফের সর্বনিম্ন ওজন সহ চাপ নির্বাচন করুন এবং গাছে যোগ করুন এবং গ্রাফ থেকে মুছুন।
2. অবশিষ্টগুলির মধ্যে সর্বনিম্ন ওজনযুক্ত প্রান্ত নির্বাচন করুন, এমনভাবে যাতে একটি চক্র তৈরি না হয়। গাছের প্রান্তটি যোগ করুন এবং গ্রাফ থেকে মুছুন। (দুই বা ততোধিক ন্যূনতম বিদ্যমান থাকলে যেকোনো নির্বাচন করুন)
৩. ধাপ 2 এ প্রক্রিয়াটি পুনরাবৃত্তি করুন।
এই পদ্ধতিতে, অ্যালগরিদম সর্বনিম্ন ওজনযুক্ত প্রান্ত দিয়ে শুরু হয় এবং প্রতিটি চক্রে প্রতিটি প্রান্ত নির্বাচন করা চালিয়ে যায়। অতএব, অ্যালগরিদমে গ্রাফটি সংযুক্ত করার প্রয়োজন নেই। ক্রুসকালের অ্যালগরিদমের একটি সময় জটিলতা রয়েছে O(logV)
Kruskal's এবং Prim's Algorithm এর মধ্যে পার্থক্য কি?
• Prim-এর অ্যালগরিদম একটি নোড দিয়ে শুরু হয়, যেখানে Kruskal-এর অ্যালগরিদম একটি প্রান্ত দিয়ে শুরু হয়৷
• প্রিমের অ্যালগরিদমগুলি এক নোড থেকে অন্য নোড পর্যন্ত বিস্তৃত থাকে যখন ক্রুসকালের অ্যালগরিদম প্রান্তগুলি এমনভাবে নির্বাচন করে যাতে প্রান্তের অবস্থান শেষ ধাপের উপর ভিত্তি করে না হয়৷
• প্রাইমের অ্যালগরিদমে, গ্রাফটি অবশ্যই একটি সংযুক্ত গ্রাফ হতে হবে যখন ক্রুস্কালগুলি সংযোগ বিচ্ছিন্ন গ্রাফগুলিতেও কাজ করতে পারে৷
• প্রিমের অ্যালগরিদমের সময় জটিলতা রয়েছে O(V2), এবং ক্রুসকালের সময় জটিলতা হল O(logV)।
