Kruskal र Prim न्यूनतम फैलिङ गाछ कसरी बनाउँछन्?

Question

Accepted Answer

एक **न्यूनतम फैलिङ गाछ (MST)** भारित, जुडिएको ग्राफको सबै शिर्षहरूलाई **न्यूनतम कुल किनारा तौल** र कुनै चक्र नभएर जोड्छ। **Kruskal** र **Prim** दुई क्लासिक लोभी एल्गोरिदम हुन्।

## Kruskal (किनारा क्रमबद्ध गर्नुहोस्, union-find)

सबै किनारहरूलाई तौल अनुसार क्रमबद्ध गर्नुहोस्; सबैभन्दा सस्तो किनारा थप्नुहोस् जसले चक्र बनाउँदैन।

```python
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
```

## Prim (min-heap सहित गाछ बढाउनुहोस्)

कुनै पनि शिर्षबाट सुरु गर्नुहोस्; वर्तमान गाछ छोड्ने सबैभन्दा सस्तो किनारा बारम्बार थप्नुहोस्।

## तुलना

| | Kruskal | Prim |
|---|--------|------|
| दृष्टिकोण | किनारा क्रमबद्ध गर्नुहोस् + union-find | नोडबाट बढाउनुहोस् + heap |
| समय | O(E log E) | O(E log V) |
| सबैभन्दा राम्रो | विरल ग्राफ | घना ग्राफ |

## कहिले प्रयोग गर्ने / समस्याहरू

**नेटवर्क डिजाइन** को लागि MST प्रयोग गर्नुहोस् — केबल, पानी पाइप, क्लस्टरिङ। दुबै लोभी हुन् र यहाँ साबित गरिएको इष्टतम हुन्। Kruskal लाई चक्रहरू कुशलतापूर्वक बेवास्ता गर्न union-find चाहिन्छ।

## यो किन महत्त्वपूर्ण छ

MST सबै कुराहरूलाई जोड्ने लागतलाई कम गर्छ — अवस्थापना र नेटवर्क लेआउटमा सीधै लागू हुन्छ।

यो एक स्वच्छ केस हो जहाँ लोभी साबित गरिएको इष्टतम हो, लोभी-विकल्प तर्कलाई सुदृढ गर्छ।

Kruskal ले union-find पनि प्रदर्शन गर्छ, एक संरचना जसको व्यापक एल्गोरिदमिक पहुँच छ।

	Kruskal	Prim
दृष्टिकोण	किनारा क्रमबद्ध गर्नुहोस् + union-find	नोडबाट बढाउनुहोस् + heap
समय	O(E log E)	O(E log V)
सबैभन्दा राम्रो	विरल ग्राफ	घना ग्राफ