Kruskal ve Prim en düşük kapsayan ağacı nasıl oluştururlar?

Question

Accepted Answer

**En düşük kapsayan ağaç (MST)**, ağırlıklı ve bağlantılı bir grafın tüm köşelerini **en düşük toplam kenar ağırlığıyla** bağlar ve döngü içermez. **Kruskal** ve **Prim**, iki klasik açgözlü algoritmadır.

## Kruskal (kenarları sırala, union-find)

Tüm kenarları ağırlığa göre sırala; döngü oluşturmayan en ucuz kenarı ekle.

```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 ile bir ağaç büyüt)

Herhangi bir köşeden başla; geçerli ağacı terk eden en ucuz kenarı tekrar tekrar ekle.

## Karşılaştırma

| | Kruskal | Prim |
|---|--------|------|
| Yaklaşım | kenarları sırala + union-find | bir düğümden büyüt + heap |
| Zaman | O(E log E) | O(E log V) |
| En iyi | seyrek grafikler | yoğun grafikler |

## Ne zaman kullanılır / tuzaklar

MST'yi **ağ tasarımı** için kullan — kablo döşeme, su boruları, kümeleme. Her ikisi de açgözlü ve burada kanıtlanmış optimaldir. Kruskal, döngüleri verimli bir şekilde önlemek için union-find gereklidir.

## Neden önemli

MST, her şeyi bağlama maliyetini en aza indirir — altyapı ve ağ düzeni için doğrudan uygulanabilir.

Açgözlünün kanıtlanmış optimal olduğu temiz bir durumdur ve açgözlü seçim mantığını pekiştirir.

Kruskal ayrıca union-find'i gösterir; geniş algoritmik erişime sahip bir yapı.

	Kruskal	Prim
Yaklaşım	kenarları sırala + union-find	bir düğümden büyüt + heap
Zaman	O(E log E)	O(E log V)
En iyi	seyrek grafikler	yoğun grafikler