Kruskal da Prim suna gina takaiciyar itace na yafi lushi?

Question

Accepted Answer

**Takaiciyar itace na yafi lushi (MST)** yana haɗa jerin gida na gijaɗi da nauyi tare da **mafi ƙanane jimillar nauyi na gida** kuma babu zagaye. **Kruskal** da **Prim** su ne gida biyu na gida na kaɗai.

## Kruskal (rarraba gida, union-find)

Rarraba duk gida ta nauyi; ƙara mafi janguwa gida wanda ba ya kirkira zagaye.

```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 (girma itace tare da min-heap)

Fara daga kowane gida; a maimaita ƙara mafi janguwa gida da ya tashi daga itace na yanzu.

## Kwatantawa

| | Kruskal | Prim |
|---|---------|------|
| Hanya | rarraba gida + union-find | girma daga gida + heap |
| Lokaci | O(E log E) | O(E log V) |
| Mafi kyau ga | gijaɗi marar yawa | gijaɗi masu yawa |

## Yaushe ake buɗe / abubuwan damama

Buɗe MST don **zane-zanen sadarwa** — shimfiɗa igiya, bututun ruwa, taron. Dukansu sune kaɗai kuma an tabbatarwa su ne masu sauƙi a nan. Kruskal yana bukatun union-find don kauce wa zagaye da sauki.

## Me ya sa ya zama mahimmanci

MST ya rage faɗin haɗa komai — ana amfani da shi kai tsaye akan gini da shimfiɗar sadarwa.

Haƙuri ne wanda kaɗai ya kasance kaɗai kuma an tabbatarwa ya kasance kaɗai, ƙarfafawa kaɗai-zabwe tunani.

Kruskal kuma ya nuna union-find, tsari mai kaɓe algorithmanci.

	Kruskal	Prim
Hanya	rarraba gida + union-find	girma daga gida + heap
Lokaci	O(E log E)	O(E log V)
Mafi kyau ga	gijaɗi marar yawa	gijaɗi masu yawa