Kruskal এবং প্রাইম মধ্যে পার্থক্য: Kruskal বনাম প্রিমিয়াম
Kruskal বনাম প্রিম
কম্পিউটার বিজ্ঞান, প্রিম এবং Kruskal এর অ্যালগরিদম একটি লোভী এলগরিদম যা একটি সংযুক্ত ওজনযুক্ত undirected গ্রাফ জন্য একটি সর্বনিম্ন spanning গাছ খুঁজে একটি প্রসারিত গাছ একটি গ্রাফ একটি subgraph হয় যেমন গ্রাফ প্রতিটি নোড একটি পাথ দ্বারা সংযুক্ত করা হয়, যা একটি বৃক্ষ প্রতিটি স্প্যানিং গাছের একটি ওজন থাকে এবং সর্বনিম্ন সম্ভাব্য ওজন / ব্যাসের সমস্ত গাছের মূল্য হল ন্যূনতম মাপের গাছ (এমএসটি)।
প্রাইম এর অ্যালগরিদম সম্পর্কে আরোঅ্যালগরিদম 1930 সালে চেক গণিতবিদ ভিজিটার্নিক জার্নালিক দ্বারা এবং পরে স্বাধীনভাবে কম্পিউটার বিজ্ঞানী রবার্ট সি। প্রাইম দ্বারা 1957 সালে এটি তৈরি করা হয়েছিল। এটি 1 9 5 9 সালে এড্সার দ্বিজকস্টোর দ্বারা পুনরায় আবিষ্কৃত হয়। অ্যালগরিদম তিনটি প্রধান ধাপে উল্লেখ করা যেতে পারে;
এন নোড এবং প্রতিটি প্রান্তের সংশ্লিষ্ট ওজনযুক্ত সংযুক্ত গ্রাফ, 1 গ্রাফ থেকে একটি নির্বিচারে নোড নির্বাচন করুন এবং এটি টি টিতে যোগ করুন (যা প্রথম নোড হবে)
3 ক্রম 2 পুনরাবৃত্তি, যতক্ষণ না এন -1 প্রান্ত গাছ যোগ করা হয়।
এই পদ্ধতিতে, বৃক্ষটি একক নির্বিচারে নোড দিয়ে শুরু হয় এবং প্রতিটি চক্রের সাথে সেই নোড থেকে প্রসারিত হয়। অতএব, অ্যালগরিদম সঠিকভাবে কাজ করার জন্য, গ্রাফ একটি সংযুক্ত গ্রাফ হতে হবে। প্রাইম এর অ্যালগরিদম মৌলিক ফর্ম হে (ভি
2 ) সময় একটি জটিলতা আছে।
জোসেফ Kruskal দ্বারা নির্মিত অ্যালগরিদম আমেরিকান গণিত সমিতি 1 9 56 সালে কার্যধারা হাজির। Kruskal এর অ্যালগরিদম এছাড়াও তিনটি সহজ ধাপে প্রকাশ করা যেতে পারে।
গ্রিডটি n নোড এবং প্রতিটি প্রান্তের নিজ নিজ ওজনের, 1। পুরো গ্রাফের সর্বনিম্ন ওজন সহ বৃত্তচাপ নির্বাচন করুন এবং বৃত্তকে যুক্ত করুন এবং গ্রাফ থেকে মুছে দিন।
2। বাকি অংশটি কম চওড়া প্রান্ত নির্বাচন করুন, একটি চক্র তৈরি না করে এমন ভাবে বৃক্ষের প্রান্তটি জুড়ুন এবং গ্রাফ থেকে মুছে দিন। (দুই বা ততোধিক মিনিমাম বিদ্যমান থাকলে তা নির্বাচন করুন)
3 পদক্ষেপ 2 এ প্রক্রিয়াটি পুনরাবৃত্তি করুন।
এই পদ্ধতিতে, আলগোরিদিম কমপক্ষে ওজনযুক্ত প্রান্ত দিয়ে শুরু হয় এবং প্রতিটি চক্রের প্রতিটি প্রান্ত নির্বাচন করে চলতে থাকে। অতএব, অ্যালগরিদম মধ্যে গ্রাফ সংযুক্ত করা প্রয়োজন হবে না। Kruskal এর অ্যালগরিদম একটি সময় জটিলতা আছে (logV)
Kruskal এবং প্রাইম এর অ্যালগরিদম মধ্যে পার্থক্য কি?
• প্রাইম এর অ্যালগরিদম একটি নোডের সাথে সূচনা করে, তবে Kruskal এর অ্যালগরিদম একটি প্রান্ত সঙ্গে শুরু।
• প্রাইম এর অ্যালগরিদম একটি নোড থেকে অন্য একটি স্প্যান করা হয় যখন Kruskal এর অ্যালগরিদম একটি উপায় প্রান্ত নির্বাচন করুন যে প্রান্ত অবস্থান শেষ ধাপ উপর ভিত্তি করে না।
• প্রাইম এর অ্যালগরিদম ইন, গ্রাফ একটি সংযুক্ত গ্রাফ হতে হবে যখন Kruskal এর সংযোগ বিচ্ছিন্ন গ্রাফগুলিতেও কাজ করতে পারে।
• প্রাইম এর অ্যালগরিদমের একটি সময় জটিলতার (ভি
২ ) আছে, এবং ক্রাস্কালের সময় জটিলতাটি ও (লগভি)।
