0Pricing
Coding Interview Prep · Ders

Kruskal'ın Minimum Örtücü Ağacı

Döngü oluşturmadan en ucuz kenarları ekleyin.

Kruskal'ın Minimum Örtücü Ağacı, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 3. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.

MST Nedir

Minimum örten ağaç, hiçbir döngü oluşturmadan her düğümü toplam kenar ağırlığı en düşük olacak şekilde bağlar. Bir kasabayı en düşük maliyetle kablolarla donattığınızı düşünün. 🌲

Kruskal'ın Temel Fikri

Kruskal algoritması tamamen açgözlüdür: bir döngü oluşturmadığı sürece en ucuz kenarı eklemeye, tüm çizge birleşene kadar devam eder.

Birinci Adım: Kenarları Sıralama

Önce her kenarı ağırlığına göre, en küçükten başlayacak şekilde sıralayın. Ucuz kenarları açgözlü biçimde tercih etmek, son toplamın en küçük olmasını sağlar.

edges.sort()  # (weight, u, v)

DSU Neden Mükemmel Uyar

Bir kenar ancak iki ucu zaten bağlıysa döngü oluşturur. DSU, bu bağlantılılık testini neredeyse sabit zamanda yanıtlar. 🤝

Sıralanmış Kenarları İnceleme

Kenarları en ucuzdan en pahalıya doğru inceleyin. Her kenar için, iki ucunun DSU'da aynı köke sahip olup olmadığını kontrol edin.

for w, u, v in edges:
    ru, rv = find(u), find(v)

Kabul Etme veya Reddetme

Kökler farklıysa kenar iki ayrı parçayı birleştirir; bu nedenle onu kabul edin ve bu parçaları birleştirin. Kökler aynıysa döngüyü önlemek için kenarı atlayın.

if ru != rv:
    union(u, v)
    total += w

Ne Zaman Duracağınızı Bilin

n düğümlü bir örten ağaç tam olarak n eksi 1 kenara sahiptir. Bu sayıda kenarı kabul ettiğinizde erkenden durabilirsiniz.

Bağlantısızlığı Belirleme

Tüm kenarları incelediğinizde kabul edilen kenar sayısı n eksi 1'den azsa çizge bağlantısızdır ve hiçbir örten ağaç yoktur.

Zaman Maliyeti

Sıralama işlemi baskın olduğundan Kruskal algoritması O(E log E) zamanda çalışır. DSU işlemleri o kadar ucuzdur ki toplam süreyi neredeyse hiç artırmaz.

Açgözlü Yaklaşım Neden Doğru

Kesme özelliği, herhangi bir bölünmeyi kesen en hafif kenarın güvenle eklenebileceğini garanti eder; en ucuz kenardan başlamanın hiçbir zaman yanlış sonuç vermemesinin nedeni tam olarak budur.

Kruskal'ı Ne Zaman Tercih Etmeli

Kruskal algoritması, doğrudan verilen kenar listesi biçimindeki seyrek çizgelerde özellikle etkilidir; yarışma soruları size çoğunlukla bu biçimi sunar. ⚡

Hızlı Kontrol

Kruskal algoritmasına bir kenarı reddettiren durumu belirleyin.

Özet

Kruskal MST'sini oluşturdunuz: kenarları sıraladınız, DSU aracılığıyla iki bileşeni birleştiren en ucuz kenarı eklediniz ve n eksi 1 kenara ulaştığınızda durdunuz. 🎉

Sıkça Sorulan Sorular

“Kruskal'ın Minimum Örtücü Ağacı” dersi ücretsiz mi?

Evet — “Kruskal'ın Minimum Örtücü Ağacı” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.

“Kruskal'ın Minimum Örtücü Ağacı” dersinde ne öğreneceğim?

Döngü oluşturmadan en ucuz kenarları ekleyin. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.

Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?

Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 3. dersidir.

“Kruskal'ın Minimum Örtücü Ağacı” dersi ne kadar sürer?

Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.

Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?

Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.

Bu kursun tüm dersleri

  1. Yol Sıkıştırmalı DSU
  2. Rütbeye Göre Birleştirme ve Bileşenler
  3. Kruskal'ın Minimum Örtücü Ağacı
  4. Yığınla Prim'in MST'si
← Coding Interview Prep Sayfasına Dön