एक न्यूनतम फैली हुई पेड़ी (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 भी दिखाता है, एक संरचना जिसकी व्यापक एल्गोरिदमिक पहुँच है।