একটি ন্যূনতম স্প্যানিং গাছ (MST) ওজনযুক্ত, সংযুক্ত গ্রাফের সমস্ত শীর্ষবিন্দুকে ন্যূনতম মোট প্রান্ত ওজন এবং কোনো চক্র ছাড়াই সংযুক্ত করে। ক্রুসকাল এবং প্রিম দুটি ক্লাসিক লোভী অ্যালগরিদম।
ক্রুসকাল (প্রান্ত সাজান, union-find)
সমস্ত প্রান্তকে ওজন অনুযায়ী সাজান; সবচেয়ে সস্তা প্রান্ত যোগ করুন যা চক্র তৈরি করে না।
():
parent = ((n))
():
parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
x
mst, total = [],
w, u, v (edges):
ru, rv = find(u), find(v)
ru != rv:
parent[ru] = rv
mst.append((u, v, w)); total += w
mst, total
