Kenar sıralama

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.

Ö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 sort_edges(edges):
    # Kenarları ağırlığa göre sırala
    return sorted(edges, key=lambda e: e[2])
print(sort_edges(init_edges()))

Kendini test et

sıralama kriteri

sorted(edges, key=lambda e: ____)

Cevabı göster

sorted(edges, key=lambda e: e[2])

Sıralama hangi yönde yapılır?
- Büyükten küçüğe
- Küçükten büyüğe
- Rastgele
- Düğüm numarasına göre
Cevabı göster

Küçükten büyüğe — Kenarlar küçükten büyüğe sıralanır.
Kenar sıralama: kavramları eşleştir

sorted

Sırala
lambda

Anahtar
e[2]

Ağırlık
edges

Kaynak

Sıradaki ders: Döngü kontrolü

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler