Yığınla Prim'in MST'si
Ağacı bir köşeden büyütün.
Yığınla Prim'in MST'si, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 4. 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'ye Giden Farklı Bir Yol
Prim algoritması da bir minimum örten ağaç bulur; ancak önce tüm kenarları sıralamak yerine, bağlı tek bir parçayı dışa doğru büyütür. 🌱
Bir Düğümden Büyümeye Başlama
Herhangi bir başlangıç düğümü seçin ve onu ziyaret edildi olarak işaretleyin. Ağaç tek bir düğüm olarak başlar ve her seferinde bir kenar genişler.
visited = [False] * nSınır Fikri
Her adımda ağaçtan dışarıya geçen tüm kenarlara bakarsınız. Prim algoritması bu sınır kenarları arasından her zaman en ucuz olanı seçer.
En Küçüğü Bir Yığın Seçer
Bir minimum yığın, en ucuz sınır kenarını hızlıca bulmanızı sağlar. Aday kenarları yığına eklersiniz ve her turda en küçük ağırlığı çıkarırsınız.
import heapq
heap = [(0, start)]En Ucuz Kenarı Çıkarma
Yığındaki en küçük girdiyi çıkarın. Bu girdi size ağırlığı ve büyüyen ağaca eklenmesi en ucuz olan sonraki düğümü verir.
w, u = heapq.heappop(heap)Güncelliğini Yitirmiş Girdileri Atlama
Bir düğüm yığında birden fazla kez bulunabilir. Zaten ziyaret edilmiş olan bir düğümü çıkarırsanız onu yok sayın ve bir sonrakini çıkarın.
if visited[u]:
continueEkleme ve Genişletme
Çıkardığınız düğümü ziyaret edilmiş olarak işaretleyin ve ağırlığını toplama ekleyin. Ardından gelecekteki adımlar için bu düğümden çıkan her kenarı yığına ekleyin.
visited[u] = True
total += w
for wt, v in adj[u]:
heapq.heappush(heap, (wt, v))Tamamlanana Kadar Yineleme
Her düğüm ziyaret edilene kadar düğümleri çıkarmaya ve ağacı genişletmeye devam edin. Bu noktada biriken toplam, minimum örten ağacın ağırlığıdır.
Çalışma Süresi
Her kenar bir kez yığına eklenip bir kez çıkarılabildiğinden, yığın tabanlı Prim algoritması O(E log V) zamanda çalışır; bu, Kruskal algoritmasıyla karşılaştırılabilir bir süredir.
Prim ve Kruskal Karşılaştırması
Komşuluk listesiyle gösterilen yoğun çizgelerde Prim'i, elinizde zaten yalın bir kenar listesi varsa Kruskal'ı kullanın. İkisi de aynı MST ağırlığını verir.
Dijkstra'ya Benziyor
Yığın döngüsü Dijkstra algoritmasını andırır; ancak yol uzaklıklarını değil, ham kenar ağırlıklarını karşılaştırırsınız. Bu örüntüyü tanımak kodlama süresinden tasarruf etmenizi sağlar. ⚡
Hızlı Kontrol
Prim algoritmasının her turda sonraki kenarı nasıl seçtiğini hatırlayın.
Özet
Prim ile bir MST oluşturdunuz: herhangi bir yerden başlayıp bir minimum yığın kullanarak en ucuz sınır kenarını eklediniz ve güncelliğini yitirmiş ziyaretleri atladınız. Harika iş! 🎉
Sıkça Sorulan Sorular
“Yığınla Prim'in MST'si” dersi ücretsiz mi?
Evet — “Yığınla Prim'in MST'si” 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.
“Yığınla Prim'in MST'si” dersinde ne öğreneceğim?
Ağacı bir köşeden büyütün. 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 4. dersidir.
“Yığınla Prim'in MST'si” 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
- Yol Sıkıştırmalı DSU
- Rütbeye Göre Birleştirme ve Bileşenler
- Kruskal'ın Minimum Örtücü Ağacı
- Yığınla Prim'in MST'si