Kif Kruskal u Prim jibnu minimal spanning tree?

Question

Accepted Answer

**Minimal spanning tree (MST)** tuħħal il-vertiċi kollha ta' graff peżat u konnessi bi **peż ta' xtara minim** u mingħajr ċikli. **Kruskal** u **Prim** huma ż-żewġ algoritmi greedy klassiċi.

## Kruskal (issortja l-ħruf, union-find)

Issortja l-ħruf kollha skond il-peż; żid il-ħruf iċċap li ma jifformaz ċiklu.

```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 (tkabbir siġra bi min-heap)

Ibda minn kwalunkwe vertiċi; ripetutament żid il-ħruf iċċap li jitlaq mill-istruttura preżenti.

## Tqabbil

| | Kruskal | Prim |
|---|--------|------|
| Approċċ | issortja l-ħruf + union-find | tkabbir minn node + heap |
| Ħin | O(E log E) | O(E log V) |
| Aħjar għal | graffs skarsi | graffs densi |

## Meta tuża / ħtrappel

Uża MST għal **disinn tal-network** — tqiegħed il-kejbils, tubazzjonijiet tal-ilma, clustering. Iż-żewġ huma greedy u pruvat ottimali hawnhekk. Kruskal iħtieġ union-find biex tiġi evitata ċ-ċikli b'mod effiċjenti.

## Għaliex huwa importanti

MST iminimizza l-ispiża ta' konnessjoni ta' kollox — direttament applikabbli għall-infrastruttura u layout tal-network.

Di każ nadif fejn greedy huwa pruvat ottimali, li turinforza r-raġunament tal-għażla greedy.

Kruskal jinvolvi wkoll union-find, struttura b'firxa algoritmica wiesgħa.

	Kruskal	Prim
Approċċ	issortja l-ħruf + union-find	tkabbir minn node + heap
Ħin	O(E log E)	O(E log V)
Aħjar għal	graffs skarsi	graffs densi