Döngü kontrolü

Eklenen kenar döngü oluşturursa atlamayı öğrenirsin.

Döngü kontrolü

Bir kenar ekleneceği zaman uçları aynı kümede mi diye denetlenir. Aynı kümedeyse kenar döngü oluşturur ve atlanır.

Bu denetim, union-find veri yapısıyla yapılır. Her düğüm bir küme olarak başlar; kenar eklendikçe kümeler birleşir.

Toplam ağırlık

Her eklenen kenarın ağırlığı toplama eklenir. n-1 kenar eklenince MST tamamlanır ve toplam ağırlık döndürülür.

Kruskal'ın çıktısı tek bir sayıdır: MST'nin toplam ağırlığı. Bu, ağacı oluşturmanın en düşük maliyetidir.

Uygulama kruskal fonksiyonu

kruskal(edges, n) yaz. find ve union hazır; kenarları sırala, döngü oluşturmayanları ekle, toplamı döndür. print(kruskal(init_edges(), 4)) ile 19 yazdır.

Örnek çözümü göster

def init_edges():
    # Kenar listesini döndür
    return [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
def find(parent, x):
    while parent[x] != x:
        x = parent[x]
    return x
def union(parent, x, y):
    px, py = find(parent, x), find(parent, y)
    if px != py:
        parent[px] = py
def kruskal(edges, n):
    # MST ağırlığını bul
    edges = sorted(edges, key=lambda e: e[2])
    parent = list(range(n))
    total = 0
    for u, v, w in edges:
        if find(parent, u) != find(parent, v):
            union(parent, u, v)
            total += w
    return total
print(kruskal(init_edges(), 4))

Kendini test et

Döngü kontrolü: kavramları eşleştir

find

Kök bul
union

Kümeleri birleştir
parent

Ata dizisi
döngü

Atla
Örnek grafta MST'nin toplam ağırlığı nedir?
- 15
- 20
- 19
- 25
Cevabı göster

19 — 4+5+10=19.

döngü koşulu

if find(parent, u) ____ find(parent, v):

Cevabı göster

if find(parent, u) != find(parent, v):

Sıradaki ders: Özet - Kruskal

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler