একটি ন্যূনতম স্প্যানিং গাছ (MST) ওজনযুক্ত, সংযুক্ত গ্রাফের সমস্ত শীর্ষবিন্দুকে ন্যূনতম মোট প্রান্ত ওজন এবং কোনো চক্র ছাড়াই সংযুক্ত করে। ক্রুসকাল এবং প্রিম দুটি ক্লাসিক লোভী অ্যালগরিদম।
সমস্ত প্রান্তকে ওজন অনুযায়ী সাজান; সবচেয়ে সস্তা প্রান্ত যোগ করুন যা চক্র তৈরি করে না।
def kruskal(n, edges): # edges: (weight, u, v)
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path compression
x = parent[x]
return x
mst, total = [], 0
for w, u, v in sorted(edges): # cheapest first
ru, rv = find(u), find(v)
if ru != rv: # no cycle -> take it
parent[ru] = rv
mst.append((u, v, w)); total += w
return mst, total
কোনো শীর্ষবিন্দু থেকে শুরু করুন; বর্তমান গাছ ছেড়ে যাওয়া সবচেয়ে সস্তা প্রান্ত বারবার যোগ করুন।
| | ক্রুসকাল | প্রিম | |---|--------|------|| | পদ্ধতি | প্রান্ত সাজান + union-find | নোড থেকে বৃদ্ধি + heap | | সময় | O(E log E) | O(E log V) | | সেরা | বিরল গ্রাফ | ঘন গ্রাফ |
একটি MST ব্যবহার করুন নেটওয়ার্ক ডিজাইনের জন্য — কেবল বিছানো, জল পাইপ, ক্লাস্টারিং। উভয়ই লোভী এবং এখানে প্রমাণিতভাবে সর্বোত্তম। ক্রুসকালের চক্র দক্ষতার সাথে এড়াতে union-find প্রয়োজন।
MST সবকিছু সংযুক্ত করার খরচ কমায় — অবকাঠামো এবং নেটওয়ার্ক লেআউটে সরাসরি প্রযোজ্য।
এটি একটি পরিষ্কার কেস যেখানে লোভ প্রমাণিতভাবে সর্বোত্তম, লোভী-পছন্দ যুক্তি শক্তিশালী করে।
ক্রুসকাল union-find প্রদর্শন করে, একটি কাঠামো যার বিস্তৃত অ্যালগরিদমিক পৌঁছানো রয়েছে।
বিস্তারিত উত্তরসহ IT ইন্টারভিউ প্রশ্নের একটি লাইব্রেরি — জুনিয়র থেকে সিনিয়র পর্যন্ত।
দান করুন