ایک کم سے کم فیلتھ والا درخت (MST) ایک وزن والے، منسلک گراف کے تمام vertices کو کم سے کم کل edge وزن کے ساتھ اور کوئی cycles کے بغیر جوڑتا ہے۔ Kruskal اور Prim دونوں کلاسی greedy الگورتھم ہیں۔
تمام edges کو وزن کے لحاظ سے ترتیب دیں؛ سب سے سستی edge شامل کریں جو ایک cycle نہیں بناتی۔
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
کسی بھی vertex سے شروع کریں؛ بار بار سب سے سستی edge شامل کریں جو موجودہ درخت سے نکلتی ہے۔
| Kruskal | Prim | |
|---|---|---|
| طریقہ | edges کی ترتیب + union-find | ایک node سے بڑھائیں + heap |
| وقت | O(E log E) | O(E log V) |
| بہترین ہے | sparse graphs کے لیے | dense graphs کے لیے |
MST کو نیٹ ورک ڈیزائن کے لیے استعمال کریں — کیبل بچھانا، پانی کی پائپ، clustering۔ دونوں greedy ہیں اور یہاں ثابت طور پر بہترین ہیں۔ Kruskal کو cycles سے بچنے کے لیے union-find کی ضرورت ہے۔
MST ہر چیز کو جوڑنے کی لاگت کو کم سے کم کرتا ہے — براہ راست بنیادی ڈھانچے اور نیٹ ورک layout پر لاگو ہوتا ہے۔
یہ ایک صاف معاملہ ہے جہاں greedy ثابت طور پر بہترین ہے، greedy-choice reasoning کو مضبوط کرتا ہے۔
Kruskal union-find کو بھی نمایاں کرتا ہے، ایک ڈھانچہ جس کی وسیع الگورتھمی رسائی ہے۔