Algoritmaların Tasarımı ve Analizi #15 | En Küçük Kapsayan Ağaç: Jarník (Prim) ve Kruskal

Açgözlü Algoritmalar (Greedy) ve Graflar

Eğitmen: Dr. Süleyman Burak ÇELİK

Sınavda şöyle gelir: Jarník (Prim) algoritması bir düğümden başlarsa kenarlar hangi sırayla eklenir, Kruskal hangi sırayla ekler? Bu derste iki algoritmayı öncelik kuyruğu ve birleşim-bul ile adım adım kuruyor, aynı çizgede ikisinin aynı ağacı farklı sırayla bulduğunu gösteriyor ve iki sınav tipi soruyu çözüyoruz. Bu derste: 1. Jarník (Prim): tek ağacı büyüt; ağaçtan dışarı çıkan en hafif kenarı ekle 2. Öncelik kuyruğu: kenarlar ağırlık sırasıyla; iki ucu ağaçta olan kenar atlanır 3. Jarník'in maliyeti ikili yığınla O(E log V) 4. Kruskal: kenarları hafiften ağıra tara; iki ayrı parçayı bağlayanı ekle, döngü kuranı atla 5. Birleşim-bul: küme kur, bul, birleştir; sıralama baskın, O(E log V) 6. Soru 1: yedi düğüm, on bir kenar; Jarník a'dan, kuyruk adım adım, beşinci eklenen kenar ve toplam 39 7. Soru 2: aynı çizgede Kruskal, kümelerle karar, dördüncü eklenen kenar; 'iki uç görüldü' tuzağı; iki algoritmanın karşılaştırması Bölümler: 0:00 Aynı Ağaç, Farklı Sıra 0:50 Kaynak Kitap ve Bugünkü Konu 1:03 Jarník (Prim) Algoritması 1:54 Öncelik Kuyruğu 2:33 Jarník'in Maliyeti 3:02 Kruskal Algoritması 3:52 Birleşim-Bul 4:46 Soru 1: Yedi Düğümlü Çizge 6:03 Soru 1: Jarník Adım Adım 8:05 Soru 1: Beşinci Kenar ve Sağlama 9:07 Soru 2: Kruskal 9:36 Soru 2: Kümelerle Karar 11:45 Soru 2: İki Algoritmanın Karşılaştırması 12:51 Bu Derste Öğrendiklerimiz 13:32 Akılda Kalan Kural ve Sıradaki Konu Bir sonraki derste en kısa yollara geçiyoruz; öncelik kuyruğu orada yeniden işimize yarayacak. Kaynak kitap: Jeff Erickson — Algorithms, 1. baskı (2019, CC BY 4.0), §7.4–7.5 (kitap s. 263–268; PDF s. 281–286). Kavram ve konu sırası kaynak kitaptan izlenir; anlatım, şemalar ve sayısal örnekler özgündür. Kitaptan metin, şekil veya problem kopyalanmamıştır. Kitap: https://jeffe.cs.illinois.edu/teaching/algorithms/ (yasal ve ücretsiz kaynak). Algoritmaların Tasarımı ve Analizi serisinin 15. dersi. Ön koşul: En Küçük Kapsayan Ağaç: Güvenli Kenar ve Borůvka. Hedef kitle: bilgisayar mühendisliği ve yazılım öğrencileri.