Prim Algoritması Nedir?

Prim Algoritması, bağlantılı, ağırlıklı bir grafın minimum yay ağacını (Minimum Spanning Tree - MST) bulmak için kullanılan açgözlü bir algoritmadır. Kruskal algoritması gibi, bu algoritma da grafın tüm köşelerini birbirine bağlayan ve toplam ağırlığı en az olan bir ağaç yapısı oluşturmayı hedefler.

Kısa cevap

Prim algoritması, başlangıçta tek bir köşe ile başlar ve her adımda, henüz ağaca dahil edilmemiş köşelerden birini, mevcut ağaca en düşük ağırlıklı kenar ile bağlayarak büyütür.

Adım adım çözümlü örnekler

Aşağıdaki graf için Prim Algoritmasını kullanarak bir MST bulunuz.

1. Rastgele bir köşe seçin (örneğin A). Ağaca dahil edilen köşeler: {A}. Kenarlar: {}.
2. A'dan çıkıp henüz ağaçta olmayan köşelere giden en kısa kenarı bulun. Bu (A, B) kenarıdır (ağırlık 2). Ağaca dahil edilen köşeler: {A, B}. Kenarlar: {(A, B)}.
3. {A, B} kümelerinden çıkıp henüz ağaçta olmayan köşelere giden en kısa kenarı bulun. Bu (B, C) kenarıdır (ağırlık 3). Ağaca dahil edilen köşeler: {A, B, C}. Kenarlar: {(A, B), (B, C)}.
4. {A, B, C} kümelerinden çıkıp henüz ağaçta olmayan köşelere giden en kısa kenarı bulun. Bu (C, D) kenarıdır (ağırlık 4). Ağaca dahil edilen köşeler: {A, B, C, D}. Kenarlar: {(A, B), (B, C), (C, D)}.
5. Tüm köşeler ağaca dahil edildi. MST'nin toplam ağırlığı: 2 + 3 + 4 = 9.

Prim Algoritmasının Adım Adım Uygulanışı

1. Boş bir küme (MST kenarları için) ve başlangıç köşesi seçilir.
2. Başlangıç köşesi 'ziyaret edildi' olarak işaretlenir.
3. Tüm komşu kenarların öncelik kuyruğuna eklenmesi.
4. Kuyruktan en düşük ağırlıklı kenarın çekilmesi.
5. Eğer kenarın hedef köşesi henüz ziyaret edilmediyse:
   a. Kenarın MST'ye eklenmesi.
   b. Hedef köşenin 'ziyaret edildi' olarak işaretlenmesi.
   c. Hedef köşenin komşularından çıkan ve henüz ziyaret edilmemiş köşelere giden kenarların kuyruğa eklenmesi.
6. Tüm köşeler ziyaret edilene kadar 4. adımdan devam edilir.

Bilgi kartları

Mini test

S1.Prim Algoritması, minimum yay ağacını bulurken hangi stratejiyi izler?

Doğru cevap: B. Prim Algoritması, başlangıçta tek bir köşe ile başlar ve her adımda, henüz ağaca dahil edilmemiş köşelerden birini, mevcut ağaca en düşük ağırlıklı kenar ile bağlayarak büyütür.

S2.Prim Algoritması'nın açgözlü olmasının anlamı nedir?

Doğru cevap: B. Açgözlü algoritmalar, her adımda o an için en iyi görünen seçimi yaparak ilerlerler. Prim Algoritması da her adımda mevcut ağaca en yakın köşeyi ekleyerek bu stratejiyi izler.

S3.Aşağıdakilerden hangisi Prim Algoritması için bir ön koşuldur?

Doğru cevap: C. Prim Algoritması, minimum yay ağacını bulmak için grafın bağlantılı olmasını gerektirir. Eğer graf bağlantılı değilse, her bir bağlantılı bileşen için ayrı ayrı MST'ler bulunur.

📄Bu konuyu PDF çalışma kağıdı olarak indirKonu özeti + 10 soru + cevap anahtarı — sınıfta paylaş, yazdır.↓

Sık yapılan hatalar

✗

Prim Algoritması, her adımda grafın en kısa kenarını seçer. — Doğrusu: Prim Algoritması, her adımda henüz ağaçta olmayan bir köşeyi, mevcut ağaca en düşük ağırlıklı kenar ile bağlar.

✗

Prim Algoritması, Kruskal gibi kenarları sıralar. — Doğrusu: Prim Algoritması, köşeleri ve onlara bağlı kenarları dikkate alarak büyür, kenarları global olarak sıralamaz.

Sıkça sorulan sorular

Prim Algoritması nerede kullanılır?

Ağ tasarımı, kümeleme problemleri, devre tasarımı gibi alanlarda minimum maliyetli bağlantılar kurmak için kullanılır.

Prim Algoritması'nın avantajları nelerdir?

Uygulaması nispeten kolaydır ve yoğun (dense) graflarda (E yaklaşık V^2 iken) Kruskal'a göre daha verimli olabilir (özellikle Fibonacci yığını ile).

Prim Algoritması'nın dezavantajı nedir?

Seyrek (sparse) graflarda (E yaklaşık V iken) Kruskal algoritması genellikle daha iyi performans gösterir. Ayrıca, grafın bağlantılı olması gerekliliği vardır.

İlgili konular