Si Kruskal dhe Prim ndërtojnë një pemë përfaqësuese minimale?

Question

Accepted Answer

**Pema përfaqësuese minimale (MST)** lidh të gjitha kulmet e një grafi të ponderuar dhe të lidhur me **peshën minimale totale të ribeve** dhe pa cikle. **Kruskal** dhe **Prim** janë dy algoritme klasike greedy.

## Kruskal (rendimit ribesh, union-find)

Renditni të gjitha ribët sipas peshës; shtoni ribën më lirë që nuk formon një cikël.

```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 (rritja e një peme me min-heap)

Filloni nga çdo kulm; përsëritni shtimin e ribës më lirë që largohet nga pema aktuale.

## Krahasimi

| | Kruskal | Prim |
|---|--------|------|
| Qasja | rendim ribesh + union-find | rritja nga një nyje + heap |
| Koha | O(E log E) | O(E log V) |
| Më mirë për | grafikë të rrallë | grafikë të dendur |

## Kur ta përdorni / kurthe

Përdorni MST për **projektimin e rrjetit** — vendosja e kablit, tubave të ujit, grupimi. Të dyja janë greedy dhe provueshëm optimale këtu. Kruskal kërkon union-find për të shmangur ciklet në mënyrë efikase.

## Përse ka rëndësi

MST minimizon koston e lidhjes së gjithçkaje — drejtpërsëdrejti i zbatueshëm në infrastrukturë dhe paraqitje rrjeti.

Êshtë një rast i pastër ku greedy është provueshëm optimal, duke përforcuar arsyetimin e zgjedhjes greedy.

Kruskal gjithashtu paraqet union-find, një strukturë me arritje të gjerë algoritmike.

	Kruskal	Prim
Qasja	rendim ribesh + union-find	rritja nga një nyje + heap
Koha	O(E log E)	O(E log V)
Më mirë për	grafikë të rrallë	grafikë të dendur