Kruskal Algoritması

#Nasıl çalışır?

Minimum kapsayan ağaç (Minimum Spanning Tree, MST), ağırlıklı ve bağlı bir graftaki tüm düğümleri birbirine bağlayan, döngü içermeyen ve toplam ağırlığı en küçük olan kenar kümesidir. V düğümlü bir grafta MST tam olarak V − 1 kenardan oluşur.

Kruskal algoritması (1956) kenarları ağırlığa göre sıralar ve en hafiften başlayarak dener. Bir kenar, uçları henüz bağlı değilse ağaca alınır; zaten bağlıysa döngü oluşturacağı için atlanır.

"Uçlar zaten bağlı mı?" sorusunu hızlıca yanıtlamak için Union-Find (ayrık kümeler) kullanılır: her kabul edilen kenar iki kümeyi birleştirir. Böylece algoritma ormandaki parçaları adım adım tek bir ağaca dönüştürür.

#Kendin dene

#Adım adım

1. 01Tüm kenarları ağırlığa göre küçükten büyüğe sırala.
2. 02Her düğüm kendi başına bir küme olsun.
3. 03Sıradaki kenarın (u, v) uçları farklı kümelerdeyse kenarı al ve kümeleri birleştir; aynı kümedeyse atla.
4. 04Ağaçta V − 1 kenar olunca dur.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

EDGES = [(1, 2, 4), (1, 3, 1), (2, 4, 5), (2, 5, 2), (3, 5, 2), (3, 6, 4), (4, 7, 3), (5, 7, 6), (6, 7, 1)]
N = 7

parent = list(range(N + 1))  # union-find over nodes 1..7


def find(x: int) -> int:
    while parent[x] != x:
        parent[x] = parent[parent[x]]  # path halving
        x = parent[x]
    return x


tree, total = [], 0
for a, b, w in sorted(EDGES, key=lambda e: (e[2], e[0], e[1])):  # lightest first
    ra, rb = find(a), find(b)
    if ra == rb:
        continue  # already connected: this edge would close a cycle
    parent[ra] = rb
    tree.append(f"{a}-{b}")
    total += w
    if len(tree) == N - 1:
        break

print(" ".join(tree))  # edges in the order they were taken
print(total)

#Karmaşıklık

Süreyi sıralama belirler; union-find işlemleri pratikte sabit sürelidir. Kenarlar zaten sıralıysa ya da ağırlıklar küçük tamsayılarsa (counting sort) Kruskal neredeyse doğrusal çalışır. Seyrek graflarda (E ≈ V) çok verimlidir.

#Ne zaman kullanılır?

Ağ kablolaması, elektrik ve boru hattı tasarımı gibi "her noktayı en az maliyetle bağla" problemleri, kümeleme (en ağır MST kenarlarını silerek gruplar elde etmek), görüntü bölütleme ve Gezgin Satıcı problemi için yaklaşık çözümler MST kullanır.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.