Kaip Kruskal ir Prim sukonstravo minimalų apimantį medį?

Question

Accepted Answer

**Minimalus apimantis medis (MST)** jungia visas svorinės, susijungusios grafiko viršūnes su **minimalia bendra briauno mase** ir be ciklų. **Kruskal** ir **Prim** yra du klasikiniai godūs algoritmai.

## Kruskal (rūšiuoti briaunas, union-find)

Rūšiuokite visas briaunas pagal svorį; pridėkite pigiausią briauną, kuri nesudaro ciklo.

```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 (auginti medį su min-heap)

Pradėkite nuo bet kurios viršūnės; pakartotinai pridėkite pigiausią briauną, paliekančią esamą medį.

## Palyginimas

| | Kruskal | Prim |
|---|--------|------|
| Metodas | rūšiuoti briaunas + union-find | augti iš mazgo + heap |
| Laikas | O(E log E) | O(E log V) |
| Geriausias | retai susijungę grafikai | tankūs grafikai |

## Kada naudoti / spąstai

Naudokite MST **tinklo projektavimui** — kabelio klojimas, vandens vamzdžiai, klasterizacija. Abu yra godūs ir čia įrodytai optimalūs. Kruskal reikalingas union-find, kad efektyviai išvengtų ciklų.

## Kodėl tai svarbu

MST sumažina viško sujungimo išlaidas — tiesiogiai taikoma infrastruktūrai ir tinklo išdėstymui.

Tai švarus atvejis, kai godumas įrodytai optimalus, sustiprinantis godaus pasirinkimo samprotavimą.

Kruskal taip pat parodo union-find, struktūrą su plačia algoritmine sritimi.

	Kruskal	Prim
Metodas	rūšiuoti briaunas + union-find	augti iš mazgo + heap
Laikas	O(E log E)	O(E log V)
Geriausias	retai susijungę grafikai	tankūs grafikai