Prim algoritması

Bir elektrik santralinden kablo döşediğinizi düşünün: önce en yakın kasabayı bağlarsınız, sonra zaten bağlı olan herhangi bir yere en yakın kasabayı, ve böyle devam edersiniz. Prim algoritması budur ve her zaman mümkün olan en ucuz ağla biter.

Tek bir düğümden büyüyen bir ağaç, çevresinde en iyi kenarları kesik çizgiyle çizilmiş bekleyen düğümler ve altta bekleyen düğümlerin listesi bulunan bir graf
Tek bir düğümden büyüyen bir ağaç, çevresinde en iyi kenarları kesik çizgiyle çizilmiş bekleyen düğümler ve altta bekleyen düğümlerin listesi bulunan bir graf

Fikir

Minimum kapsayan ağaç, ağırlıklı bir grafın tüm düğümlerini mümkün olan en küçük toplam kenar uzunluğuyla bağlar. Prim algoritması onu, bir başlangıçtan dışa doğru tek bir ağaç büyüterek kurar. Ağaç hiçbir zaman parçalara ayrılmaz: her adımda, ağaçtan dışarı çıkan en kısa kenarla tam olarak bir yeni düğüm katılır.

Adım adım

Başlangıcı ağaca koyun. Ağacın dışındaki her düğüm için en iyi kenarını tutun: ağaçtaki herhangi bir düğüme giden en kısa kenarını. Sonra tekrarlayın: en iyi kenarı en kısa olan dış düğümü seçin, onu bu kenarla ağaca ekleyin ve kenarlarına bakın. Ağacın dışında olup artık daha kısa bir kenarla ulaşılabilen bir komşu, o kenarı yeni en iyi kenarı olarak alır. Tüm düğümler ağaca girdiğinde durun.

Bir örnek

Uzunluğu 1 olan A–B, 2 olan B–C, 3 olan A–C, 4 olan C–D ve 5 olan B–D kenarlarını alın ve A düğümünden başlayın. A düğümünün kenarları B düğümüne en iyi kenar olarak 1, C düğümüne 3 verir. En yakın düğüm B olduğu için A–B ile katılır; onun kenarları C düğümünü 2'ye iyileştirir ve D düğümüne 5 verir. C düğümü B–C ile katılır ve C–D kenarı D düğümünü 4'e iyileştirir. Son olarak D düğümü C–D ile katılır. A–B, B–C, C–D ağacının toplam uzunluğu 1 + 2 + 4 = 7'dir.

Neden doğrudur

Her adımda düğümler iki gruba ayrılmıştır: ağaçtakiler ve dışarıdakiler. Kesme özelliği, böyle iki grup arasındaki en kısa kenarın her zaman bir minimum kapsayan ağaca ait olduğunu söyler. Prim her zaman tam olarak bu kenarı ekler; bu yüzden şimdiye kadar kurduğu ağaç her zaman bir minimum kapsayan ağaca tamamlanabilir ve tüm düğümler katıldığında kendisi bir minimum kapsayan ağaçtır.

Tarihçe ve hız

Çek matematikçi Vojtěch Jarník algoritmayı 1930'da yayımladı. Robert Prim onu 1957'de Bell Labs'te, Edsger Dijkstra da 1959'da yeniden keşfetti. Bekleyen düğümler ikili yığında tutulduğunda iş, V düğüm ve E kenar için E log V ile büyür; düz bir diziyle yaklaşık V² olur, bu da neredeyse her düğüm çifti bağlı olduğunda daha iyidir. Fibonacci yığınıyla E + V log V olur.

Keşfedin

Uygulamayı açın, oradan başlamak için bir düğüme tıklayın ve Adım'a basın. Ağaçtaki düğümler yeşil, bekleyen düğümler mavidir ve her bekleyen düğümün en iyi kenarı kesik çizgiyle çizilir. Bekleyen düğümler grafın altında en iyi kenarlarının uzunluğuyla, en kısadan başlayarak listelenir: ilk sıradaki bir sonraki olarak katılır. Farklı düğümlerden başlayın ve toplam aynı kalırken sıranın nasıl değiştiğini görün.

Sık sorulan sorular

Prim ve Dijkstra algoritmaları arasındaki fark nedir?

İkisi de bir öncelik kuyruğu kullanarak bir başlangıçtan bir bölge büyütür. Prim bekleyen bir düğümü ağaca giden tek en iyi kenarının uzunluğuna göre sıralar; Dijkstra ise başlangıçtan tüm uzaklığına göre. Prim bir minimum kapsayan ağaç, Dijkstra bir en kısa yollar ağacı verir.

Prim algoritması negatif kenar uzunluklarıyla çalışır mı?

Evet. Dijkstra algoritmasının aksine Prim yalnızca kenarları birbiriyle karşılaştırır, bu yüzden negatif uzunluklar sorun çıkarmaz: yine toplamı en küçük kapsayan ağacı bulur.

Graf bağlı değilse ne olur?

O zaman Prim algoritması ulaşabildiği her düğüme ulaştığında durur: yalnızca başlangıcın bulunduğu parçanın minimum kapsayan ağacını verir. Henüz ulaşılmamış bir düğümden yeniden çalıştırmak bir minimum kapsayan orman verir.

Prim mi yoksa Kruskal algoritması mı daha iyi?

Hiçbiri her zaman kazanmaz. Prim yoğun graflara ve komşu listeleri olarak saklanan graflara uygundur; Kruskal ise kenar listesi olarak verilen seyrek graflara. İkisi de aynı toplam uzunlukta bir ağaç bulur.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Prim algoritmasını deneyin