एक न्यूनतम फैलिङ गाछ (MST) भारित, जुडिएको ग्राफको सबै शिर्षहरूलाई न्यूनतम कुल किनारा तौल र कुनै चक्र नभएर जोड्छ। Kruskal र Prim दुई क्लासिक लोभी एल्गोरिदम हुन्।
सबै किनारहरूलाई तौल अनुसार क्रमबद्ध गर्नुहोस्; सबैभन्दा सस्तो किनारा थप्नुहोस् जसले चक्र बनाउँदैन।
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
कुनै पनि शिर्षबाट सुरु गर्नुहोस्; वर्तमान गाछ छोड्ने सबैभन्दा सस्तो किनारा बारम्बार थप्नुहोस्।
| Kruskal | Prim | |
|---|---|---|
| दृष्टिकोण | किनारा क्रमबद्ध गर्नुहोस् + union-find | नोडबाट बढाउनुहोस् + heap |
| समय | O(E log E) | O(E log V) |
| सबैभन्दा राम्रो | विरल ग्राफ | घना ग्राफ |
नेटवर्क डिजाइन को लागि MST प्रयोग गर्नुहोस् — केबल, पानी पाइप, क्लस्टरिङ। दुबै लोभी हुन् र यहाँ साबित गरिएको इष्टतम हुन्। Kruskal लाई चक्रहरू कुशलतापूर्वक बेवास्ता गर्न union-find चाहिन्छ।
MST सबै कुराहरूलाई जोड्ने लागतलाई कम गर्छ — अवस्थापना र नेटवर्क लेआउटमा सीधै लागू हुन्छ।
यो एक स्वच्छ केस हो जहाँ लोभी साबित गरिएको इष्टतम हो, लोभी-विकल्प तर्कलाई सुदृढ गर्छ।
Kruskal ले union-find पनि प्रदर्शन गर्छ, एक संरचना जसको व्यापक एल्गोरिदमिक पहुँच छ।
विस्तृत उत्तरसहित IT अन्तर्वार्ता प्रश्नहरूको पुस्तकालय — जुनियरदेखि सिनियरसम्म।
दान गर्नुहोस्