Kenar sıralama
- Algoritmalar kursu
- İleri seviye
- Ders 38/56
- 4 dk
Kenarları ağırlığa göre sıralayıp eklemeyi öğrenirsin.
Kenar sıralama
Kruskal'ın ilk adımı kenarları ağırlığa göre küçükten büyüğe sıralamaktır. Böylece en düşük ağırlıklı kenarlar önce denenir.
Sıralama, açgözlü (greedy) yaklaşımın temelidir. Her adımda en düşük ağırlıklı kullanılabilir kenar seçilir.
Açgözlü seçim
Sıralı kenar listesinde baştan gidilir ve her kenar MST'ye eklenir; yalnızca döngü oluşturmuyorsa. Döngü denetimi için union-find kullanılır.
Bu açgözlü yaklaşım, MST'nin optimal olduğunu garantiler. Her adımda yerel en iyi seçim yapılır.
Uygulama sort_edges fonksiyonu
sort_edges(edges) yaz. Kenarları ağırlığa göre küçükten büyüğe sırala, döndür. print(sort_edges(init_edges())) ile yazdır.
Başlangıç kodu
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 sort_edges(edges):
# Kenarları ağırlığa göre sıralaÖrnek çözüm
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 sort_edges(edges):
# Kenarları ağırlığa göre sırala
return sorted(edges, key=lambda e: e[2])
print(sort_edges(init_edges()))Beklenen çıktı
[(2, 3, 4), (0, 3, 5), (0, 2, 6), (0, 1, 10), (1, 3, 15)]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 sıralama kriteri
sorted(edges, key=lambda e: ____)sorted(edges, key=lambda e: e[2])Açıklama: e[2] doğru.
2 Sıralama hangi yönde yapılır?
- Büyükten küçüğe
- Küçükten büyüğe Doğru cevap
- Rastgele
- Düğüm numarasına göre
Açıklama: Kenarlar küçükten büyüğe sıralanır.
3 Kenar sıralama: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
sorted |
Sırala |
lambda |
Anahtar |
e[2] |
Ağırlık |
edges |
Kaynak |