Öncelikli kuyruk
- Algoritmalar kursu
- İleri seviye
- Ders 42/56
- 4 dk
Prim'in öncelikli kuyrukla verimli çalıştığını öğrenirsin.
En düşük anahtar
Prim'de her düğümün bir keys değeri vardır: ağaca bağlanmanın en düşük maliyeti. Her adımda en düşük keys'e sahip ziyaret edilmemiş düğüm seçilir.
Bu seçim, doğrusal arama ile yapılabilir. min_key(keys, visited) fonksiyonu bu seçimi yapar.
Başlangıç durumu
keys başlangıçta tüm düğümler için inf'tir; yalnızca başlangıç düğümü keys[0] = 0 olur. Böylece ilk seçim başlangıç düğümüdür.
Ziyaret dizisi tüm düğümler için False ile başlar. Ağaç tek düğümden büyümeye başlar.
Uygulama min_key fonksiyonu
min_key(keys, visited) yaz. Ziyaret edilmemiş ve en küçük keys'e sahip indeksi döndür. print(min_key([0, float('inf'), float('inf'), float('inf')], [False, False, False, False])) ile 0 yazdır.
Başlangıç kodu
def min_key(keys, visited):
# En küçük keys'e sahip ziyaret edilmemiş indeksi bulÖrnek çözüm
def min_key(keys, visited):
# En küçük keys'e sahip ziyaret edilmemiş indeksi bul
best = float('inf')
idx = -1
for i in range(len(keys)):
if not visited[i] and keys[i] < best:
best = keys[i]
idx = i
return idx
print(min_key([0, float('inf'), float('inf'), float('inf')], [False, False, False, False]))Beklenen çıktı
0
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 min seçimi
if not visited[i] and keys[i] ____ best:if not visited[i] and keys[i] < best:Açıklama: < doğru.
2 min_key hangi düğümü döndürür?
- En büyük keys'i
- En küçük keys'i Doğru cevap
- Rastgele düğümü
- İlk ziyaret edilmişi
Açıklama: min_key en küçük keys'e sahip düğümü döndürür.
3 Öncelikli kuyruk: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
keys |
Maliyet |
visited |
Ziyaret |
min_key |
Seçim |
inf |
Sonsuz |