Bölüm 4.3: Minimum Kapsayan Ağaç Algoritmaları

4.3.1Kapsayan ağaç ve minimum kapsayan ağaç

Çizgeler, nesneler ve aralarındaki bağlantılar üzerine kurulan problemlerin ortak dilidir. Bu notta ele alınan çizgeler yönsüzdür: u ile v arasındaki kenar iki yönde de kullanılabilir. Çizgeler ayrıca ağırlıklıdır: her kenarın bir sayısal değeri vardır ve bu değer kablonun uzunluğunu, yolun maliyetini ya da iki nokta arasındaki farkı gösterebilir. Düğüm sayısı V, kenar sayısı E ile gösterilir. Aynı harfler bağlama göre düğüm ve kenar kümesini de anlatır; G = (V, E) yazımında olduğu gibi.

Ağaç kavramı ise ikili arama ağaçlarından ve öbeklerden tanıdıktır. Orada ağaç köklü bir veri yapısıdır. Çizge kuramında ağaç daha genel bir nesnedir: bağlı ve döngüsüz her yönsüz çizge bir ağaçtır. Kök yoktur, çocuk sayısı sınırı yoktur. Bir ağacın herhangi iki düğümü arasında tam olarak bir yol bulunur. Yol hiç olmasaydı çizge bağlı olmazdı; iki farklı yol olsaydı bu iki yol birlikte bir döngü oluştururdu.

4.3.1.1Problemin tanımı

Bağlı bir çizgeden bazı kenarları silerek bütün düğümleri hâlâ birbirine bağlayan, ama hiç döngü içermeyen bir alt çizge elde edilebilir. Böyle bir alt çizge, çizgenin bütün düğümlerini “kapsar”.

Kapsayan ağacın kaç kenarı olduğu, düğüm sayısından kesin olarak bellidir. Bu sonuç bütün algoritmaların durma koşulunda kullanılır.

Bir çizgenin genellikle birçok kapsayan ağacı vardır. Kenarlar ağırlıklı olduğunda bu ağaçların toplam ağırlıkları da farklıdır. Asıl ilgilendiğimiz, toplamı en küçük olanıdır.

Tanımdaki “minimum” sözcüğü ağacın kendisini değil, toplam ağırlığı nitelendirir. Kenar sayısı her kapsayan ağaçta V − 1 olduğu için en az kenarlı ağaç diye bir arayış yoktur. Ağaçlar yalnız hangi kenarları seçtikleriyle ayrılır. Şekil 4.3.1 beş düğümlü küçük bir çizgeyi ve onun minimum kapsayan ağacını gösterir.

Şekildeki çizgenin yedi kenarı vardır. Kapsayan ağaç beş düğümü bağlamak için dört kenar seçer; üç kenar dışarıda kalır. Kalın dört kenar bir ağaç oluşturur: a'dan e'ye ve b'ye, b'den c'ye, c'den d'ye gidilebilir ve hiçbir döngü yoktur. Dışarıda kalan be = 4, ec = 6 ve ed = 7 kenarlarının her biri ağaca eklenseydi bir döngü kapatırdı. Örneğin be eklenirse b → a → e → b döngüsü oluşur.

4.3.1.2Kaç kapsayan ağaç vardır?

MST'yi bulmanın en kaba yolu, bütün kapsayan ağaçları tek tek kurup ağırlıklarını karşılaştırmaktır. Bu yöntemin neden işe yaramadığını kapsayan ağaç sayısı gösterir. Her düğüm çiftinin bir kenarla bağlandığı çizgeye tam çizge denir. Arthur Cayley 1889'da n düğümlü tam çizgenin tam olarak nⁿ⁻² kapsayan ağacı olduğunu gösterdi. Bu sonuç Cayley formülü diye bilinir.

On beş düğümlü bir tam çizgede kapsayan ağaç sayısı katrilyon mertebesindedir. Bütün ağaçları denemek, küçük çizgelerde bile kullanışsızdır. Tam olmayan çizgelerde sayı daha azdır, ama yine hızla büyür: Şekil 4.3.1'deki yedi kenarlı çizgenin 21 kapsayan ağacı vardır. Bu ağaçların ağırlıkları 11 ile 21 arasında değişir ve 11 ağırlıklı yalnız bir ağaç vardır. Neyse ki MST'yi bulmak için ağaçları saymaya gerek yoktur. Problem, her adımda yerel olarak en iyi görünen seçimi yapan açgözlü (greedy) algoritmalarla doğrudan çözülür. Açgözlü yaklaşımın burada neden doğru sonuç verdiğini kesim ve döngü özellikleri açıklar.

4.3.1.3Örnek: “MST” çizgesi

Daha büyük bir örnek, kapsayan ağacın hangi kenarları seçtiğini ve hangilerini dışarıda bıraktığını görmeye yardım eder. Şekil 4.3.2'deki çizge M, S ve T harflerini çizer. Çizgenin 15 düğümü ve 20 kenarı vardır.

Kalın kenar sayısı 14'tür ve bu sayı V − 1 = 15 − 1'e eşittir. Ağırlıkların toplamı şöyle bulunur:

2 + 2 + 5 + 10 + 7 + 8 + 10 + 11 + 4 + 1 + 20 + 25 + 24 + 12 = 141

Dışarıda kalan altı ince kenarın ortak bir özelliği vardır. Her biri kalın kenarlarla birlikte bir döngü kapatır ve o döngünün en ağır kenarıdır. M harfinin üstündeki 15'lik kenar, iki çapraz 2'lik kenarla bir üçgen kurar; üçgenin en ağırı 15'tir. M'nin altındaki 16'lık kenar, iki bacak (5 ve 10) ve iki çapraz (2 ve 2) ile döngü kurar. S harfinin sol alt kısmındaki 25'lik ince kenar ise 11, 1 ve 4 ağırlıklı kalın kenarlarla bir döngü kapatır. Her durumda ince kenarın yerine döngünün öteki kenarları bağlantıyı sağlar ve daha ucuzdur.

Ağırlığı yüksek bazı kenarlar ise ağaçtadır: 20, 24 ve S ile T arasındaki 25. Bu kenarlar hiçbir döngünün en ağırı değildir. Örneğin S'nin sağ altından T'nin sağ üst ucuna uzanan 40'lık kenar uzun bir döngü kapatır. Bu döngüde 20, 25 ve 24'lük kenarlar da vardır, ama döngünün en ağırı 40'tır. Aynı biçimde 50'lik kenar 24 ve 12 ile bir üçgen kurar. Çizgede bir de köprü vardır: M ile S'yi bağlayan 7'lik kenar silinirse çizge iki parçaya ayrılır. Bir köprü hiçbir döngüde yer almadığı için her kapsayan ağaçta, dolayısıyla her MST'de bulunmak zorundadır.

4.3.1.4Kesim özelliği

Bütün MST algoritmaları iki basit gözleme dayanır. Birincisi düğümleri iki gruba ayırmakla ilgilidir.

İspattaki fikre değiştirme argümanı (exchange argument) denir. Açgözlü seçimi içermeyen bir en iyi çözüm alınır. Bu çözümün bir parçası değiştirilir ve çözüm, o seçimi içeren, en az onun kadar iyi bir çözüme dönüşür. Aynı fikir açgözlü algoritmaların çoğunun doğruluk ispatında kullanılır.

4.3.1.5Döngü özelliği

İkinci gözlem, kesim özelliğinin bir bakıma tersidir. Kesim özelliği hangi kenarın kesinlikle seçilebileceğini söyler; döngü özelliği ise hangi kenarın kesinlikle dışarıda bırakılabileceğini söyler.

Döngü özelliği küçük bir uyarı içerir: en ağır kenar tek olmalıdır. Bir döngüde en ağır ağırlık iki kenarda birden görülürse, bunlardan biri bir MST'de bulunabilir. Örneğin kenarları 1, 2 ve 2 olan bir üçgende 2'lik kenarlardan biri mutlaka seçilir. Böyle durumda özellik yalnız şunu söyler: en ağır kenarlardan birini içermeyen bir MST vardır.

İki özellik birlikte algoritmaların iskeletini verir. Tablo 4.3.2 hangi algoritmanın hangi özelliği kullandığını özetler.

4.3.1.6MST ne zaman tektir?

Bir çizgenin birden fazla minimum kapsayan ağacı olabilir. Bunun için eşit ağırlıklı kenarlar gerekir. Kenarları 1, 2 ve 2 olan üçgende 1'lik kenar ile 2'lik kenarlardan herhangi biri bir MST oluşturur. İki farklı ağacın ağırlığı da 3'tür. Bütün ağırlıklar farklıysa böyle bir seçim serbestliği kalmaz.

Teoremin tersi doğru değildir: eşit ağırlıklı kenarlar bulunan bir çizgenin MST'si yine tek olabilir. Şekil 4.3.1'deki ağırlıklar zaten farklıdır; bu yüzden orada tek MST vardır. Eşit ağırlıklı kenarlar bulunduğunda farklı algoritmalar, hatta aynı algoritmanın farklı kenar sıraları farklı ağaçlar bulabilir. Bulunan ağaçların toplam ağırlığı ise her zaman aynıdır.

4.3.1.7Açgözlü MST algoritmaları

Kesim özelliği genel bir yöntem önerir. Başta hiç kenar seçilmemiştir. Seçilen kenarlar her an bir MST'nin parçası olacak biçimde büyütülür. Her adımda, seçilmiş kenarların hiçbirinin geçmediği bir kesim bulunur ve o kesimin en hafif kenarı eklenir. Böyle bir kenara güvenli kenar denir: eklendiğinde seçilen kümenin yine bir MST'ye genişletilebileceği garanti edilir. V − 1 güvenli kenar eklenince ağaç tamamlanır.

Dört klasik algoritma bu genel yöntemin farklı uygulamalarıdır. Hepsi açgözlüdür: her adımda yerel olarak en iyi kenarı seçer ya da en kötüsünü atar ve bu karar hiçbir zaman geri alınmaz.

Dört algoritma da aynı ağırlıkta bir MST bulur. Ağırlıklar farklıysa, MST'nin tekliği nedeniyle aynı ağacı bulurlar. Aralarındaki fark kenarları hangi sırayla ele aldıklarında ve gereken veri yapısındadır. Kruskal ve Borůvka bir ormanla, yani birden çok ağaçla çalışır. Prim her an tek bir ağaç tutar. Ters silme ise bütün çizgeden başlar ve onu inceltir. Tablodaki yıllar da ilginçtir: en eski algoritma Borůvka'nınkidir ve bilgisayarlardan önce, bir elektrik ağı problemi için yazılmıştır.

4.3.1.8Uygulama alanları

MST, kuramsal bir merak değildir; birçok mühendislik probleminin ya kendisi ya da bir adımıdır.

• Ağ tasarımı. Şehirleri, binaları ya da cihazları en az kabloyla bağlamak doğrudan bir MST problemidir. Elektrik, su, fiber optik ve yol ağları bu sınıfa girer. Borůvka'nın 1926 çalışmasının çıkış noktası da Moravya'nın elektrik ağıydı.
• Kümeleme. Noktalar düğüm, aralarındaki uzaklıklar ağırlık sayılır. MST'den en ağır k − 1 kenar silinirse k parça kalır ve her parça bir kümedir. Bu yönteme tek bağlantılı kümeleme (single-linkage clustering) denir. Dokuz düğümlü Kruskal örneğinde MST'nin en ağır iki kenarı silinince {A, B}, {C, D, E, F, H} ve {G, I} kümeleri oluşur.
• Yaklaşık algoritmalar. Metrik gezgin satıcı probleminde (TSP), MST'yi derinlik öncelikli dolaşıp tekrar eden düğümleri atlayan tur, en iyi turun en fazla 2 katıdır. TSP'nin kesin çözümü çok pahalıdır; MST ise hızla bulunur.
• Görüntü işleme. Pikseller düğüm, komşu piksellerin renk farkı ağırlık sayılır. MST tabanlı yöntemler benzer renkteki bölgeleri bir araya toplayarak görüntüyü bölütler (segmentation).
• Devre tasarımı. Bir yonga üzerinde birbirine bağlanması gereken bacakları en kısa toplam iletkenle bağlamak, VLSI yönlendirmesinin ön adımıdır.
• Başka çizge problemleri. İki düğüm arasında, en ağır kenarı en hafif olan yola darboğaz yol denir. Böyle bir yol her zaman MST üzerindedir. Steiner ağacı problemi için de MST temel bir yaklaşık çözümdür.

4.3.2Kruskal algoritması

Kruskal algoritması MST problemine akla gelen en doğal yanıtı verir: önce en ucuz kenarlar alınır, yeter ki döngü oluşmasın. Joseph Kruskal bu algoritmayı 1956'da, gezgin satıcı problemiyle ilgili kısa bir makalede yayımladı. Aynı makalede ters silme algoritmasının fikri de yer alır.

4.3.2.1Fikir: ormanı birleştirmek

Başlangıçta her düğüm tek başına bir ağaçtır; çizge V ağaçlı bir ormandır. Kenarlar ağırlığa göre küçükten büyüğe sıralanır ve bu sırayla incelenir. İncelenen kenar iki farklı ağacın düğümlerini bağlıyorsa ağaca eklenir ve bu iki ağaç birleşir. Kenarın iki ucu zaten aynı ağaçtaysa, kenar eklendiğinde bir döngü oluşur; kenar atlanır. Her ekleme ağaç sayısını bir azaltır. V − 1 ekleme sonunda tek ağaç kalır ve algoritma biter.

Şekildeki ara durumda {a, b, c} ve {d, e, f} olmak üzere iki ağaç vardır. Sıradaki kenar bc = 4'tür. b ile c arasında b → a → c yolu zaten vardır; bc eklenirse bu yol ile birlikte bir döngü oluşur. Ardından gelen bd = 5 ise iki ayrı ağacı bağlar ve eklenir. Bu noktada orman tek ağaç olur.

Algoritmanın kısa bir değerlendirmesi şöyledir. Kruskal, kenar sayısının düğüm sayısına yakın olduğu seyrek çizgelerde çok uygundur. Kodu basittir: bir kenar listesi ve bir ayrık kümeler yapısı yeterlidir. Çizge bağlı değilse algoritma her bileşen için ayrı bir ağaç, yani bir minimum kapsayan orman üretir. Zayıf yanları da vardır. Kenarları sıralamanın maliyeti O(E log E)'dir. Kenar sayısının V²'ye yaklaştığı yoğun çizgelerde Prim'in dizi taramalı sürümü daha hızlı olabilir. Döngü denetimi için ek bir yapı gerekir.

4.3.2.2Adımlar ve sözde kod

Algoritmanın adımları şöyledir:

1. Çizgedeki bütün kenarlar ağırlıklarına göre artan sırada sıralanır.
2. Sıralı kenarlar arasından sıradaki en küçük ağırlıklı kenar seçilir.
3. Kenar farklı ağaçlara ait iki düğümü birleştiriyorsa ağaca eklenir ve iki ağaç birleştirilir.
4. Kenar aynı ağacın iki düğümünü bağlıyorsa döngü oluşturur ve atlanır.
5. V − 1 kenar seçilene (ya da kenarlar bitene) kadar 2–4. adımlar tekrarlanır.

KRUSKAL(G):
  MST = [ ]
  ayrikKume.oluştur(V)
  kenarlar.sırala(artana göre)
  her bir (u, v, ağırlık) için kenarlar içinde:
    eğer ayrikKume.bul(u) ≠ ayrikKume.bul(v):
      MST.ekle((u, v, ağırlık))
      ayrikKume.birleştir(u, v)
  döndür MST

Sözde kodun tek gizemli yeri ayrikKume.bul(u) ≠ ayrikKume.bul(v) karşılaştırmasıdır. bul, bir düğümün hangi ağaçta olduğunu söyleyen bir temsilci döndürür. İki ucun temsilcisi farklıysa kenar iki ayrı ağacı bağlar. birleştir ise iki ağacı tek ağaçta toplar. “Bu iki düğüm aynı ağaçta mı?” sorusu ayrık kümeler yapısıyla neredeyse sabit zamanda yanıtlanır. Yapı bir sonraki kesimde ayrıntılı ele alınır.

4.3.2.3Adım adım örnek

Şekil 4.3.1'deki beş düğümlü çizgeye Kruskal uygulanır. Çizgenin kenarları ab = 3, ae = 1, bc = 5, be = 4, cd = 2, ed = 7 ve ec = 6'dır.

İzlemede reddedilen kenar yalnız be'dir. Bu kenar Şekil 4.3.1'deki çizgenin dördüncü en hafif kenarıdır. Kruskal onu ağırlığı yüzünden değil, konumu yüzünden atlar: b ve e daha ucuz iki kenarla zaten birbirine bağlıdır.

4.3.2.4Kruskal neden doğrudur?

Ağırlıklar farklıysa sıralı kenar listesi tek türlüdür ve Kruskal her zaman aynı ağacı bulur. Eşit ağırlıklı kenarlar bulunduğunda sıralama onları farklı sıralarla dizebilir. Bu durumda sonuç ağaç değişebilir, ama ağırlığı değişmez: kanıt hangi sıralama seçilirse seçilsin geçerlidir.

4.3.3Ayrık kümeler (union-find)

Kruskal'ın hızı, “iki düğüm aynı ağaçta mı?” sorusunun ne kadar çabuk yanıtlandığına bağlıdır. Her kenar için BFS ya da DFS ile yol aramak O(V) sürer ve toplam maliyeti O(E · V)'ye çıkarır. Ayrık kümeler yapısı aynı soruyu pratikte sabit zamanda yanıtlar.

4.3.3.1Yapı ve işlemler

Yapının en yaygın gösterimi bir ormandır. Her küme bir ağaçtır ve ağacın kökü kümenin temsilcisidir. Ağaç bellekte tek bir dizide tutulur: ata[i], i'nin ebeveynidir; kökte ata[r] = r'dir. Bu ağaçların, MST'nin kendisiyle bir ilgisi yoktur. Yalnız “kim hangi kümede?” bilgisini taşırlar ve biçimleri çizgenin kenarlarından farklı olabilir.

oluştur(V) her düğüm için ata[i] = i yazar. bul(x) ebeveyn bağlantılarını izleyerek köke kadar çıkar ve kökü döndürür. birleştir(x, y) iki kökü bulur ve birini öbürünün altına bağlar. Kruskal'da kullanım şöyledir: bul(u) == bul(v) ise u ve v aynı ağaçtadır ve kenar bir döngü kapatır. Sunumdaki Java kodu şöyledir:

int bul(int[] ata, int i) {
  if (ata[i] != i)
    ata[i] = bul(ata, ata[i]); // yol sıkıştırma
  return ata[i];
}
void birlestir(int[] ata, int x, int y) {
  ata[bul(ata, x)] = bul(ata, y);
}

bul özyinelemelidir. ata[i] == i ise i köktür ve kendisi döndürülür. Değilse ebeveynin kökü özyinelemeyle bulunur. Dönüşte bulunan kök ata[i]'ye yazılır. Bu atama, metodun asıl işi olan kökü bulmanın yanında bir yan etki yaratır: yol üzerindeki her düğüm doğrudan köke bağlanır. Bu iyileştirmeye yol kısaltma (path compression) denir; kodun yorumundaki “yol sıkıştırma” aynı işlemin öbür adıdır. birlestir ise tek satırdır: x'in kökünün ebeveyni, y'nin kökü yapılır. İki öğe zaten aynı kümedeyse iki bul aynı kökü döndürür ve atama kökü kendine bağlar; yapı değişmez.

4.3.3.2Kruskal'da döngü denetimi

Ayrık kümelerin Kruskal içinde nasıl çalıştığı, beş düğümlü bir çizge üzerinde izlenir. Kenarlar sıralıdır: ac 1, de 2, ab 3, bc 4, bd 5, cd 6, ce 7. Her kabul edilen (u, v) kenarı için ata[bul(u)] = bul(v) uygulanır.

ab adımında bul(a) önce a'nın ebeveyni c'ye çıkar. c köktür; kök c döner. bul(b) ise b'nin kendisini döndürür. Kökler farklı olduğu için kenar eklenir ve c kökü b'nin altına bağlanır. bc adımında bul(b) = b ve bul(c) de c → b yoluyla b'yi bulur. Kökler aynıdır; kenar döngü kapatır. Dört kenar seçildiğinde MST tamamlanır: ac + de + ab + bd = 1 + 2 + 3 + 5 = 11.

MST doğru bulunmuştur, ama ayrık küme ormanı uzun bir zincire dönüşmüştür. bul(a) çağrısı a → c → b → e yolunu izler. Bu durumda yol kısaltma devreye girer. bul(a) dönerken yol üzerindeki her düğümü doğrudan köke bağlar: ata[a] = ata[c] = e olur. b zaten köke bağlıdır. Sonraki aramalar tek adımda biter.

4.3.3.3Kod izleme: bul ve birlestir

Yol kısaltmanın özyineleme içinde nasıl gerçekleştiği, 0, …, 4 öğeli küçük bir örnekle adım adım izlenir. Çağrı sırası birlestir(0, 1), birlestir(1, 2), birlestir(2, 3), bul(0) ve birlestir(4, 0)'dır.

İlk üç birleştirme kötü bir örüntü üretir. Her seferinde bir kök öbür kökün altına bağlanır ve zincir bir uzar. bul(0) artık üç adım sürer. Genel durumda n öğe bu biçimde zincirlenirse tek bir bul n − 1 adım sürer. bul(0) çağrısı özyinelemeyle köke iner: önce bul(1), sonra bul(2), sonra bul(3) çağrılır. bul(3) kökü bulur ve 3 döndürür. Özyineleme geri sarılırken her çerçeve kendi ata[i] değerine 3 yazar. Sonuçta 0, 1 ve 2 doğrudan 3'e bağlanır. Son birleştirmede bul(0) tek adımda biter ve 4 de 3'ün altına girer; bütün öğeler tek kümededir.

4.3.3.4Yol kısaltma ve rütbeye göre birleştirme

Ayrık kümelerin hızı ağaçların yüksekliğine bağlıdır. İki iyileştirme yüksekliği küçük tutar. Birincisi yukarıda görülen yol kısaltmadır. İkincisi birleştirme anında hangi kökün hangisinin altına gireceğini akıllıca seçer. Her kökte bir rütbe (rank) tutulur; rütbe, ağacın yüksekliği için bir üst sınırdır. Birleştirmede rütbesi küçük kök, rütbesi büyük kökün altına bağlanır. Rütbeler eşitse biri öbürünün altına girer ve yeni kökün rütbesi bir artar. Bu yönteme rütbeye göre birleştirme (union by rank) denir.

void birlestirRutbe(int[] ata, int[] rutbe, int x, int y) {
  int a = bul(ata, x), b = bul(ata, y);
  if (a == b) return;                    // zaten aynı küme
  if (rutbe[a] < rutbe[b]) ata[a] = b;   // alçak ağaç yüksek ağacın altına
  else if (rutbe[a] > rutbe[b]) ata[b] = a;
  else { ata[b] = a; rutbe[a]++; }       // eşitse biri altına, rütbe artar
}

Kod önce iki kökü bulur; kökler aynıysa iş yoktur. Rütbeler farklıysa alçak ağaç yüksek ağacın altına girer ve hiçbir rütbe değişmez: yüksek ağacın yüksekliği artmaz. Yalnız eşit rütbeli iki ağaç birleştiğinde yükseklik bir artabilir; bu yüzden yalnız o durumda rütbe artırılır. Önceki izlemedeki çağrı dizisi bu metotla tekrarlanırsa zincir oluşmaz. birlestirRutbe(0, 1) rütbeleri eşit bulur, 1'i 0'ın altına bağlar ve 0'ın rütbesini 1 yapar. Sonraki birleştirmelerde 2, 3 ve 4 tek öğeli, rütbesi 0 olan ağaçlardır; hepsi rütbesi 1 olan 0'ın altına girer. Sonuçta ata = [0, 0, 0, 0, 0] olur ve ağacın yüksekliği 1'de kalır.

Sınır sıkıdır. 8 öğe ikişer ikişer, sonra dörder dörder, sonra sekizli olarak eşit rütbeli ağaçlar hâlinde birleştirilirse rütbe 3'e ulaşır; 1024 öğede aynı yöntem rütbeyi 10'a çıkarır. Yol kısaltma da eklendiğinde yapı çok daha hızlıdır. Robert Tarjan 1975'te iki iyileştirme birlikte kullanıldığında m işlemin toplam maliyetinin O(m · α(n)) olduğunu gösterdi. Burada α, çok hızlı büyüyen Ackermann fonksiyonunun tersidir. Ters Ackermann fonksiyonu o kadar yavaş büyür ki evrendeki atom sayısından büyük her pratik n için α(n) ≤ 4'tür. Bu yüzden işlem başına maliyet amortize olarak sabit kabul edilir. Amortize maliyet, uzun bir işlem dizisinde işlem başına düşen ortalama maliyettir. Tek bir bul yine de uzun sürebilir, ama bu uzun yürüyüş sonraki çağrıları hızlandırır.

4.3.4Kruskal kodu ve karmaşıklığı

4.3.4.1Java kodu

Kruskal'ın Java uygulaması bir kenar sınıfına dayanır. Kenar iki uç düğümü ve ağırlığı tutar. Collections.sort ile sıralanabilmesi için Comparable arayüzünü uygular ve kenarları ağırlığa göre karşılaştırır:

class Kenar implements Comparable<Kenar> {
  int u, v, w;                  // uçlar ve ağırlık
  Kenar(int u, int v, int w) { this.u = u; this.v = v; this.w = w; }
  public int compareTo(Kenar o) {
    return Integer.compare(w, o.w);   // ağırlığa göre artan
  }
}

Integer.compare(w, o.w), w − o.w çıkarmasının güvenli karşılığıdır. Çok büyük ya da negatif ağırlıklarda çıkarma taşabilir; Integer.compare taşmaz. Düğümler 1'den V'ye kadar numaralanır. Sunumdaki Kruskal kodu şöyledir:

void kruskal(int V, List<Kenar> ke) {
  Collections.sort(ke);         // artan
  int[] ata = new int[V + 1];
  for (int i = 1; i <= V; i++) ata[i] = i;
  List<Kenar> agac = new ArrayList<>();
  int k = 0;
  while (agac.size() < V - 1) {
    Kenar e = ke.get(k++);
    int x = bul(ata, e.u);
    int y = bul(ata, e.v);
    if (x != y) {               // ayrı ağaç
      agac.add(e);
      ata[x] = y;               // birleştir
    }
  }
}

Kod satır satır şöyle çalışır. Collections.sort(ke) kenar listesini ağırlığa göre artan sıraya koyar. Java'nın liste sıralaması kararlıdır: eşit ağırlıklı kenarlar listedeki ilk sıralarını korur. ata dizisi V + 1 uzunluktadır, çünkü düğümler 1'den başlar ve 0. hücre kullanılmaz. Döngü her düğümü kendi kümesinin kökü yapar. agac seçilen kenarları, k ise sıralı listede sıradaki kenarın indisini tutar.

while (agac.size() < V - 1) döngüsü V − 1 kenar seçilene kadar sürer. Her turda sıradaki kenar alınır ve k bir artar. İki ucun kökü x ve y olarak bulunur. Kökler farklıysa kenar ağaca eklenir ve ata[x] = y ile iki küme birleşir. Burada birlestir çağrılmaz, çünkü kökler zaten bulunmuştur; atama doğrudan yapılır. Kökler aynıysa hiçbir şey yapılmaz ve döngü sıradaki kenara geçer.

4.3.4.2Kod izleme: beş düğümlü çizge

Kod, düğümleri 1–5 olan bir çizge üzerinde izlenir. Kenarlar (1,3) = 2, (2,5) = 2, (1,2) = 3, (2,3) = 4, (3,4) = 4 ve (1,4) = 6'dır.

Üçüncü satırda bul(1) 1'in ebeveyni 3'e çıkar ve 3'ü döndürür; bul(2) 5'i döndürür. Kökler farklıdır ve ata[3] = 5 ile iki ağaç birleşir. Dikkat edilirse değişen hücre 1'in ya da 2'nin hücresi değil, kök 3'ün hücresidir. Dördüncü satırda bul(2) ve bul(3) ikisi de 5'i bulur; (2,3) iki ayrı ağacı birleştirmediği için döngü kurar ve atlanır. Beşinci satırda 4 tek başınadır; (3,4) eklenir ve ata[5] = 4 olur. agac.size() artık 4 = V − 1'dir; döngü biter. (1,4) = 6 hiç incelenmez. MST (1,3), (2,5), (1,2), (3,4) kenarlarından oluşur ve w(T) = 11'dir.

İzlemede eşit ağırlıklı iki çift vardır: (1,3) ile (2,5) ve (2,3) ile (3,4). Kararlı sıralama onları listedeki sırada bırakır. (3,4) listede (2,3)'ten önce gelseydi önce (3,4) eklenir, sonra (2,3) yine döngü gerekçesiyle atlanırdı. Bu çizgede sonuç değişmez. (2,3)'ün atlanmasının nedeni 2 → 1 → 3 yolunun daha ucuz kenarlarla zaten kurulmuş olmasıdır.

4.3.4.3Dokuz düğümlü örnek

Daha büyük bir örnek olarak A, …, I düğümlü, 15 kenarlı çizge ele alınır. Sıralı kenarlar şöyledir:

EF 1, CF 1, DE 2, FH 3, AB 4, EH 5, GI 5, DG 6, AC 7, BD 9, EG 10, BC 11, HI 12, EI 15, BF 20

Dokuzuncu incelenen kenar AC = 7'dir ve sekizinci eklenen kenardır. 8 = V − 1 olduğu için algoritma burada durur; BD 9'dan sonraki altı kenara bakılmaz. MST'nin ağırlığı 29'dur. Bu ağaç, uygulama alanlarında söz edilen kümeleme örneğinin de kaynağıdır. En ağır iki MST kenarı AC = 7 ve DG = 6'dır. Bu iki kenar silinirse üç küme kalır: {A, B}, {C, D, E, F, H} ve {G, I}.

4.3.4.4Karmaşıklık

Kruskal'ın maliyeti işlemlerine ayrılarak hesaplanır. Tablo 4.3.8 her işlemin kaç kez yapıldığını ve maliyetini verir.

Toplam O(E log E)'dir ve bu maliyeti sıralama belirler. Bağlı bir çizgede E ≥ V − 1 olduğu için O(V)'lik ilkleme de sıralamanın yanında küçük kalır. Çoğu kaynakta aynı sınır O(E log V) diye yazılır. İki yazım aynı mertebeyi gösterir. Yönsüz basit bir çizgede E ≤ V(V − 1)/2 < V²'dir. Logaritma alınırsa log E < 2 log V bulunur. Sabit çarpanlar mertebeyi değiştirmediği için O(E log E) = O(E log V)'dir. Örneğin V = 1000 düğümlü tam çizgede E = 499.500'dür; log₂ E ≈ 18,9, 2 log₂ V ≈ 19,9'dur.

Kenarlar zaten sıralı geliyorsa ya da ağırlıklar küçük tam sayılarsa durum değişir. İkinci durumda saymalı sıralama kenarları doğrusal zamanda sıralar. Bu durumlarda toplam süre neredeyse doğrusaldır: O(E · α(V)). Ayrık kümelerde yalnız rütbeye göre birleştirme kullanılırsa her işlem en kötü O(log V) sürer; yol kısaltma da eklenince işlem başına amortize maliyet O(α(V))'ye iner. Her iki durumda da toplamı sıralama belirler. Sunumdaki kod yalnız yol kısaltma yapar; rütbe kullanmaz. Bu kodun da pratikte çok hızlı olduğu bilinir.

Bellek gereksinimi kenar listesi ve ebeveyn dizisi kadardır: O(V + E). Kenar listesi zaten girdinin kendisidir; ek bellek ata dizisi ve seçilen V − 1 kenardır.

4.3.4.5Bağlı olmayan çizge

Sunumdaki kod, çizgenin bağlı olduğunu varsayar. Bağlı olmayan bir çizgede V − 1 kenar asla seçilemez. Liste bittiğinde döngü koşulu hâlâ doğrudur ve ke.get(k++) liste sınırının dışına çıkar.

Çözüm, döngü koşuluna liste sınırını eklemektir. Sonda agac.size() < V − 1 ise çizge bağlı değildir. Bu durumda seçilen kenarlar bir minimum kapsayan orman oluşturur: her bileşen için bir minimum kapsayan ağaç.

List<Kenar> kruskalOrman(int V, List<Kenar> ke) {
  Collections.sort(ke);
  int[] ata = new int[V + 1];
  for (int i = 1; i <= V; i++) ata[i] = i;
  List<Kenar> agac = new ArrayList<>();
  int k = 0;
  while (k < ke.size() && agac.size() < V - 1) {
    Kenar e = ke.get(k++);
    int x = bul(ata, e.u), y = bul(ata, e.v);
    if (x != y) { agac.add(e); ata[x] = y; }
  }
  return agac;                  // agac.size() < V - 1 ise orman
}

Örnekteki çizgede bu sürüm (4,5), (1,2), (2,3), (5,6) kenarlarını döndürür. Orman iki ağaçlıdır ve toplam ağırlığı 1 + 2 + 3 + 4 = 10'dur. Kenar sayısı V − 2'dir. Genel olarak c bileşenli bir çizgenin kapsayan ormanında V − c kenar bulunur.

4.3.5Prim algoritması

Kruskal bütün çizgeye yayılmış küçük ağaçlarla çalışır. Prim ise tek bir ağaçla başlar ve onu adım adım büyütür. Algoritma Robert C. Prim'in 1957 tarihli makalesiyle tanındı. Aynı yöntemi Vojtěch Jarník 1930'da bulmuştu; Edsger W. Dijkstra 1959'da yeniden keşfetti. Bu yüzden bazı kaynaklarda Jarník algoritması ya da Prim–Jarník algoritması adıyla geçer.

4.3.5.1Fikir: tek ağacı büyütmek

Bir başlangıç düğümü seçilir; ağaç başta yalnız bu düğümden oluşur. Her adımda ağaçta olmayan düğümler arasından, ağaca en ucuz kenarla bağlanan düğüm seçilir. Bu düğüm ve onu bağlayan kenar ağaca eklenir. Tüm düğümler ağaca girince algoritma biter. Her an tek bir ağaç vardır; Kruskal'daki orman yoktur.

Prim her adımda bir kesimin en hafif kenarını seçer: kesim, o ana kadar kurulan ağaç ile geri kalan düğümler arasındadır. Şekildeki c–d = 1 kenarı çizgenin en hafif kenarıdır, ama kesimi geçmez; iki ucu da ağaçta değildir. Prim bu kenarı ancak d ağaca girdikten sonra kullanabilir. Kruskal ise aynı çizgede işe c–d = 1 ile başlardı.

Algoritmanın değerlendirmesi şöyledir. Prim yoğun çizgelerde çok uygundur: komşuluk matrisi ile O(V²) sürede çalışır. Kenarları sıralamaya gerek yoktur. Komşuluk listesi ya da matrisiyle doğal biçimde çalışır. Zayıf yanı, başarımının kullanılan veri yapısına bağlı olmasıdır: dizi, ikili heap ve Fibonacci heap farklı süreler verir. Bağlı olmayan çizgede yalnız başlangıç düğümünün bileşenini kapsar.

4.3.5.2Anahtar ve ebeveyn

“Ağaca en ucuz kenarla bağlanan düğüm” her adımda yeniden aranırsa algoritma yavaşlar. Prim bu bilgiyi her düğüm için iki dizide saklar ve ağaç büyüdükçe günceller.

Ağaca yeni bir u düğümü girdiğinde yalnız u'nun komşularının anahtarı değişebilir; çünkü ağaca bağlanmanın yeni yolları yalnız u üzerinden açılır. Ağaçta olmayan her v komşusu için w(u, v) < anahtar[v] ise anahtar ve ebeveyn güncellenir: anahtar[v] = w(u, v), ata[v] = u. Ardından anahtarı en küçük olan ağaç dışı düğüm seçilir. Bu düğümün anahtarı, kesimi geçen en hafif kenarın ağırlığıdır.

4.3.5.3Sözde kod

Prim'in adımları şöyle sıralanabilir:

1. Başlangıç düğümü seçilir ve bu düğüme ait bütün kenarlar öncelikli kuyruğa eklenir.
2. Kuyruktan, ağaçta olmayan bir düğüme giden en küçük ağırlıklı kenar seçilir.
3. Seçilen kenar ile bağlantılı yeni düğüm ağaca eklenir.
4. Yeni düğüme bağlı kenarlar kuyruğa eklenir; bütün düğümler ağaca girene kadar 2–4. adımlar tekrarlanır.

Sunumdaki sözde kod iki parçadan oluşur. İlk parça dizileri ilkler, ikinci parça ana döngüdür:

PRIM(G, kaynak):
  MST = [ ]
  mesafeler = [ ]
  ata = [ ]
  ziyaretEdildi = [ ]
  her bir v için V içinde:
    mesafeler[v] = ∞
    ziyaretEdildi[v] = 0
  mesafeler[kaynak] = 0
  öncelikKuyruğu.ekle(kaynak, 0)

döngü öncelikKuyruğu boş değil iken:
  u = öncelikKuyruğu.çıkar()
  eğer ziyaretEdildi[u] == 0:
    ziyaretEdildi[u] = 1
    her bir (u, v, ağırlık) için G[u] içinde:
      eğer ziyaretEdildi[v] == 0 ve
           ağırlık < mesafeler[v]:
        mesafeler[v] = ağırlık
        ata[v] = u
        öncelikKuyruğu.ekle(v, ağırlık)
her bir v için V içinde (kaynak hariç):
  MST.ekle((ata[v], v, mesafeler[v]))
döndür MST

Sözde koddaki mesafeler dizisi, tanımdaki anahtar dizisidir. Ad yanıltıcı olabilir: değer bir uzaklık değil, tek bir kenarın ağırlığıdır. Kod bir düğümü kuyruğa birden çok kez ekleyebilir. Bir düğümün anahtarı her küçüldüğünde kuyruğa yeni bir kayıt girer; eski kayıt silinmez, kuyrukta kalır. Bu yüzden bu sürüme tembel (lazy) Prim denir. Eski kayıt sonunda kuyruktan çıktığında ziyaretEdildi[u] denetimi onu atar. Kuyruk en fazla E kadar kayıt tutar; her kenar bir anahtar küçülmesine yol açabilir. Toplam süre O(E log E)'dir.

4.3.5.4Adım adım: öncelikli kuyruk

Prim, Şekil 4.3.11'daki beş düğümlü çizgede 1'den başlatılır. Burada ders kitaplarındaki klasik gösterim kullanılır: kuyruk Q bütün düğümlerle başlar ve her düğüm anahtarıyla birlikte kuyrukta durur. Tablolardaki π, ebeveyndir; “/” henüz ebeveyn atanmadığını gösterir.

Adımlar şöyle açıklanır. İlklemede yalnız kaynağın anahtarı 0'dır; bu yüzden ilk çıkan düğüm 1'dir. 1'in komşuları güncellenir: key(3) = 2, key(2) = 3, key(4) = 6. İkinci adımda en küçük anahtar 3'ündür; 3 çıkar ve (1,3) ağaca girer. 3'ün komşusu 4 için (3,4) = 4 < 6 olduğundan key(4) = 4, π(4) = 3 olur. Öbür komşu 2 için (2,3) = 4 > key(2) = 3 olduğundan değişiklik yoktur. Üçüncü adımda 2 çıkar ve (1,2) eklenir; 5'in anahtarı 2 olur. Dördüncü adımda 5 çıkar; ağaçta olmayan başka komşusu yoktur. Son adımda 4 çıkar ve (3,4) eklenir.

Sonuç ağaç (1,3), (1,2), (2,5), (3,4) kenarlarından oluşur ve w(T) = 11'dir. Kruskal aynı çizgede aynı ağacı bulmuştu. Kenarların eklenme sırası ise farklıdır: Kruskal 2, 2, 3, 4 sırasıyla ekler; Prim 2, 3, 2, 4 sırasıyla. Prim'in 2'lik (2,5) kenarını 3'lük (1,2)'den sonra eklemesinin nedeni, 5'in ancak 2 ağaca girdikten sonra ağaca komşu olmasıdır.

4.3.5.5Prim neden doğrudur?

İspattan çıkan bir sonuç da başlangıç düğümünün önemsiz olduğudur. Farklı bir düğümden başlayan Prim, kenarları farklı sırada ekler. Ağırlıklar farklıysa sonunda yine aynı ağacı bulur; eşit ağırlıklar varsa farklı ama aynı ağırlıkta bir ağaç bulabilir.

4.3.6Prim kodu ve karmaşıklığı

4.3.6.1Komşuluk matrisli sürüm

Prim'in en kısa uygulaması öncelikli kuyruk kullanmaz. Çizge bir komşuluk matrisiyle verilir: G[u][v], u ile v arasındaki kenarın ağırlığıdır; kenar yoksa 0'dır. Anahtarı en küçük düğüm her adımda dizinin baştan sona taranmasıyla bulunur.

void prim(int[][] G, int kaynak) {
  int V = G.length;
  int[] anahtar = new int[V];
  int[] ata = new int[V];
  boolean[] agacta = new boolean[V];
  Arrays.fill(anahtar, Integer.MAX_VALUE);
  anahtar[kaynak] = 0;
  ata[kaynak] = -1;
  for (int s = 0; s < V - 1; s++) {
    int u = enKucukAnahtar(anahtar, agacta);
    agacta[u] = true;
    for (int v = 0; v < V; v++)
      if (G[u][v] != 0 && !agacta[v]
          && G[u][v] < anahtar[v]) {
        anahtar[v] = G[u][v];
        ata[v] = u;
      }
  }
}

Kod satır satır şöyle çalışır. anahtar dizisinin bütün hücrelerine Integer.MAX_VALUE yazılır; bu değer ∞ yerine kullanılır. Kaynağın anahtarı 0, ebeveyni −1'dir; −1 “ebeveyn yok” anlamına gelir. agacta dizisi hangi düğümlerin ağaca girdiğini tutar.

Dış döngü V − 1 kez döner. Her turda enKucukAnahtar ağaçta olmayan düğümler arasında anahtarı en küçük olanı bulur ve bu düğüm ağaca alınır. İç döngü bu düğümün bütün komşularını gezer. Üç koşul birlikte aranır: G[u][v] != 0 kenarın var olduğunu, !agacta[v] komşunun henüz ağaçta olmadığını, G[u][v] < anahtar[v] ise yeni kenarın eski en iyiden ucuz olduğunu söyler. Üçü de doğruysa anahtar ve ebeveyn güncellenir.

Dış döngünün V değil V − 1 kez dönmesi bilinçli bir seçimdir. V − 1 düğüm ağaca girdiğinde son düğümün anahtarı ve ebeveyni artık değişemez: onu ağaca bağlayan bütün kenarların öbür ucu ağaçtadır ve hepsi incelenmiştir. Son düğüm agacta dizisinde işaretlenmez, ama ata değeri doğrudur. Sunumdaki kod enKucukAnahtar yardımcısını kullanır. Bu yardımcı şöyle yazılabilir:

int enKucukAnahtar(int[] anahtar, boolean[] agacta) {
  int enKucuk = Integer.MAX_VALUE, indis = -1;
  for (int v = 0; v < anahtar.length; v++)
    if (!agacta[v] && anahtar[v] < enKucuk) {
      enKucuk = anahtar[v];
      indis = v;
    }
  return indis;
}

Yardımcı, eşitlikte küçük indisli düğümü seçer, çünkü karşılaştırma < ile yapılır: sonra gelen eşit anahtar, bulunan en küçüğü değiştirmez. Bağlı olmayan bir çizgede ağaç dışındaki bütün anahtarlar ∞ kalabilir; o zaman metot −1 döndürür ve prim içinde agacta[-1] erişimi hata verir. Kod bağlı çizge varsayar.

4.3.6.2Kod izleme: A–F çizgesi

Kod altı düğümlü bir çizgede izlenir. Düğümler A–F'dir ve indisleri 0–5'tir. Kaynak B'dir (indis 1). Kenarlar AB = 1, BC = 3, AD = 3, BD = 2, BE = 6, BF = 5, CE = 4, CF = 4, DE = 3 ve EF = 2'dir.

İlk turda enKucukAnahtar B'yi döndürür, çünkü yalnız B'nin anahtarı sonludur. B'nin beş komşusu da güncellenir. İkinci turda en küçük anahtar A'nındır (1); (B, A) ağaca girer. A'nın ağaç dışı tek komşusu D'dir, ama AD = 3, D'nin mevcut anahtarı 2'den büyüktür. Üçüncü turda D (2) girer ve E'nin anahtarı 6'dan 3'e iner: E'ye D üzerinden bağlanmak B üzerinden bağlanmaktan ucuzdur.

Dördüncü turda C ve E'nin anahtarları eşittir (3). enKucukAnahtar küçük indisli C'yi seçer. C'den F'ye 4'lük kenar, F'nin mevcut anahtarı 5'ten ucuzdur; F'nin ebeveyni C olur. Beşinci turda E (3) girer ve EF = 2 ile F'nin anahtarı 2'ye iner. Dış döngü beş tur döner ve biter. F ağaca resmen alınmaz, ama ebeveyni E'dir. MST (ata[v], v) kenarlarından okunur: BA, BC, BD, DE, EF. Toplam 1 + 3 + 2 + 3 + 2 = 11'dir.

Eşitlikte E seçilseydi ne olurdu? E girer, F'nin anahtarı 2 olur; sonra C (3) ve F (2) yarışır ve F seçilir. Sonunda C de girer. Seçilen kenarlar yine BA, BD, DE, EF, BC olurdu; yalnız sıra değişirdi. Bu çizgede eşit ağırlıklı kenarlar bulunmasına rağmen MST tektir.

4.3.6.3Tembel öncelikli kuyruk sürümü

Seyrek çizgelerde dizinin her turda baştan sona taranması gereksiz bir maliyettir. Java'nın PriorityQueue sınıfı en küçük öğeyi O(log n) sürede çıkarır. Sunumdaki tembel sürüm, sözde koddaki yöntemi Java ile yazar. Çizge komşuluk listesiyle verilir: komsu.get(u), u'dan çıkan kenarların listesidir. anahtar, ata, agacta ve komsu sınıf alanlarıdır.

void primPQ(int kaynak) {
  Arrays.fill(anahtar, SONSUZ);
  anahtar[kaynak] = 0;
  PriorityQueue<int[]> pq =
      new PriorityQueue<>((a, b) -> a[1] - b[1]);
  pq.add(new int[] { kaynak, 0 });
  while (!pq.isEmpty()) {
    int u = pq.poll()[0];
    if (agacta[u]) continue;  // eski
    agacta[u] = true;
    for (Kenar k : komsu.get(u))
      if (!agacta[k.v] && k.w < anahtar[k.v]) {
        anahtar[k.v] = k.w; ata[k.v] = u;
        pq.add(new int[] { k.v, k.w });
      }
  }
}

Kuyruktaki her kayıt iki öğeli bir dizidir: {düğüm, anahtar}. Karşılaştırıcı a[1] - b[1] kayıtları anahtara göre sıralar. Ağırlıklar küçük olduğu sürece çıkarma güvenlidir; çok büyük ağırlıklarda Integer.compare(a[1], b[1]) yazmak daha doğrudur. Döngü her turda en küçük kaydı çıkarır. Düğüm zaten ağaçtaysa kayıt eskidir ve continue ile atlanır. Değilse düğüm ağaca girer ve komşuları incelenir. Anahtarı küçülen her komşu için kuyruğa yeni bir kayıt eklenir. Eski kayıt silinmez; silme işi, kaydın kuyruktan çıkacağı ana ertelenir. Bu ertelemeye tembel silme denir.

Kod beş düğümlü çizgede, kaynak 1 ile izlenir. Tablo 4.3.11'deki kuyruk sütunu, kaydı çıkarmadan önceki içeriği anahtara göre sıralı verir.

İkinci satırda 4'ün anahtarı 6'dan 4'e iner ve kuyruğa (4,4) kaydı eklenir. Eski (4,6) kaydı kuyrukta kalır. 4 ağaca (4,4) kaydıyla girer. (4,6) en son çıkar ve atlanır. Kuyruk boşalınca MST kenarları (ata[v], v) olarak okunur: 1–3 (2), 1–2 (3), 2–5 (2) ve 3–4 (4); toplam 11.

Tembel sürümün karşılığı, anahtarı yerinde küçülten istekli (eager) sürümdür. İstekli sürüm her düğüm için kuyrukta tek kayıt tutar ve anahtar küçüldüğünde o kaydı günceller. Bu işleme anahtar azaltma (decrease-key) denir. Java'nın PriorityQueue sınıfı bu işlemi doğrudan sunmaz; bu yüzden Java uygulamalarında tembel sürüm yaygındır. Tembel sürüm kuyrukta V yerine en fazla E kayıt tutar, ama log E ≤ 2 log V olduğu için mertebe değişmez.

4.3.6.4Dokuz düğümlü örnek

Kruskal'ın dokuz düğümlü örneği Prim ile A'dan başlanarak çözülür. Her satır, o adımda ağaca giren düğümden sonraki anahtar ve ebeveyn değerlerini verir.

Tablo birkaç şeyi açıkça gösterir. F'nin anahtarı önce B üzerinden 20 olur, C girince 1'e iner. D'nin anahtarı B üzerinden 9'dur, E girince 2'ye iner. I'nın anahtarı üç kez değişir: E üzerinden 15, H üzerinden 12, G üzerinden 5. Bir düğümün anahtarı yalnız küçülür; büyümesi mümkün değildir. H ağaca girdiğinde EH = 5 kenarı artık kullanılamaz, çünkü E ve H ikisi de ağaçtadır. Kruskal aynı kenarı döngü gerekçesiyle atlamıştı.

Sonuç ağırlığı 29'dur ve Kruskal'ın bulduğu ağaçla aynıdır. İki algoritmanın kenar ekleme sıraları ise belirgin biçimde farklıdır. Kruskal ağırlıkları 1, 1, 2, 3, 4, 5, 6, 7 sırasıyla ekler. Prim 4, 7, 1, 1, 2, 3, 6, 5 sırasıyla ekler: önce A'nın çevresindeki pahalı kenarları alır, ucuz kenarlara ancak ağaç onlara ulaşınca erişir.

4.3.6.5Karmaşıklık

Prim'in süresi iki işlemin maliyetine bağlıdır: anahtarı en küçük düğümü çıkarmak ve bir komşunun anahtarını azaltmak. Birinci işlem V kez yapılır. İkinci işlem en fazla E kez yapılır, çünkü her kenar iki ucundan biri ağaca girdiğinde bir kez incelenir. Yönsüz çizgede her kenar iki komşuluk listesinde görünür; incelemelerin sayısı 2E'yi aşmaz.

Matris sürümünde dış döngü V kez döner. Her turda enKucukAnahtar V hücreyi tarar ve iç döngü V komşuyu gezer. Toplam O(V²)'dir ve bu süre kenar sayısından bağımsızdır. Heap sürümünde her çıkarma ve her anahtar azaltma O(log V) sürer; toplam O((V + E) log V) olur. Bağlı çizgede E ≥ V − 1 olduğu için bu ifade çoğu zaman O(E log V) diye kısaltılır.

Hangi sürümün daha iyi olduğu çizgenin yoğunluğuna bağlıdır. Yoğun bir çizgede (E ≈ V²) matris sürümü O(V²) ile en iyisidir; heap sürümü O(V² log V)'ye çıkar. Seyrek bir çizgede (E ≈ V) ise heap sürümü O(V log V) sürer; matris sürümü gereksiz yere O(V²) harcar.

4.3.6.6Prim ile Dijkstra arasındaki fark

Prim'in kodu, en kısa yol için kullanılan Dijkstra algoritmasının koduna çok benzer. İkisi de bir kaynaktan başlar, öncelikli kuyruktan en küçük anahtarlı düğümü çıkarır ve komşularını günceller. Tek fark anahtarın anlamıdır.

Beş düğümlü çizgede de benzer bir fark görülür. 1'den 4'e en kısa yol uzunluğu 6'dır ve bu uzaklık hem doğrudan (1,4) kenarıyla hem 1 → 3 → 4 yoluyla elde edilir. Bu yüzden en kısa yollar ağacı (1,4) = 6 kenarını kullanabilir. MST onun yerine (3,4) = 4 kenarını seçer.

4.3.7Borůvka algoritması

Minimum kapsayan ağacı bulan en eski algoritma Otakar Borůvka'nın 1926 tarihli çalışmasıdır. Borůvka, Moravya bölgesinin elektrik ağını en ucuz biçimde kurma problemiyle uğraşıyordu. Yöntem sonradan birkaç kez yeniden bulundu; Georges Sollin'in 1960'lardaki çalışması nedeniyle Sollin algoritması diye de anılır.

4.3.7.1Fikir: bütün bileşenler aynı anda

Başlangıçta her düğüm bağımsız bir bileşendir. Algoritma turlar hâlinde ilerler. Her turda her bileşen, kendisini dışarıya bağlayan en ucuz kenarı seçer. Seçilen kenarların hepsi birden eklenir ve bağladıkları bileşenler birleşir. Tek bileşen kalana kadar turlar sürer. Bağlı bir çizgede algoritma V − 1 kenar üretir.

Bir bileşenin en ucuz dış kenarı, o bileşen ile geri kalan düğümler arasındaki kesimin en hafif kenarıdır. Kesim özelliğine göre bu kenar güvenlidir. Kruskal ve Prim her adımda tek bir kesim seçer; Borůvka ise her turda bileşen sayısı kadar kesimi aynı anda kullanır.

Şekildeki çizgede e'nin en ucuz kenarı ef = 6'dır, çünkü öbür kenarı ae = 9'dur. f ise bf = 3'ü seçer. Bir kenar iki ucundan da seçilebilir; ab hem a'nın hem b'nin seçimidir ama bir kez eklenir. İlk tur sonunda bileşenler {a, b, e, f}, {c, d} ve {g, h}'dir. İkinci turda bc = 4 ve fg = 5 eklenir ve ağaç tamamlanır; toplam ağırlık 22 olur.

Algoritmanın en önemli üstünlüğü bileşenlerin seçimlerinin birbirinden bağımsız olmasıdır. Her bileşenin en ucuz kenarı ayrı bir işlemcide bulunabilir. Bu yüzden Borůvka paralel ve dağıtık hesaplamaya çok uygundur. Tur sayısı da küçüktür: en fazla ⌈log₂ V⌉. Zayıf yanları da vardır. Kodlaması Kruskal ve Prim'den daha karmaşıktır. Eşit ağırlıklı kenarlar bulunduğunda tutarlı bir eşitlik bozucu gerekir; yoksa döngü oluşabilir.

4.3.7.2Adımlar ve sözde kod

1. Başlangıçta her düğüm tek başına bir bileşen (küme) sayılır.
2. Her bileşen için, onu başka bir bileşene bağlayan en küçük ağırlıklı kenar bulunur.
3. Bulunan kenarların hepsi eklenir; bağladıkları bileşenler birleştirilir. Aynı kenar iki kez eklenmez.
4. Tek bileşen kalana kadar 2. ve 3. adımlar tekrarlanır.

BORUVKA(G):
  MST = [ ]
  bileşenSayısı = |V|
  döngü bileşenSayısı > 1 iken:
    enUcuz = [ ]  // bileşen başına
    her bir e = (u, v, ağırlık) için E içinde:
      cu = ayrikKume.bul(u)
      cv = ayrikKume.bul(v)
      eğer cu ≠ cv:
        enUcuz[cu] = min(enUcuz[cu], e)
        enUcuz[cv] = min(enUcuz[cv], e)
    her bir (u, v, ağırlık) için enUcuz içinde:
      eğer ayrikKume.bul(u) ≠ ayrikKume.bul(v):
        MST.ekle((u, v, ağırlık))
        ayrikKume.birleştir(u, v)
        bileşenSayısı -= 1
  döndür MST

Borůvka kenarları sıralamaz. Her turda bütün kenarları bir kez tarar ve her bileşen için o ana kadar görülen en küçük dış kenarı tutar. Bileşenler ayrık kümeler yapısıyla izlenir: bir kenarın iki ucunun bul sonuçları aynıysa kenar bileşenin içindedir ve hesaba katılmaz. İkinci döngüde seçilen kenarlar eklenirken yeniden bul sorulur. Bunun nedeni, iki bileşenin aynı kenarı seçmiş olabilmesidir. İlk kez eklendiğinde iki bileşen birleşir; ikinci kez sırası geldiğinde iki ucu artık aynı bileşendedir ve kenar atlanır.

4.3.7.3Altı düğümlü örnek

Algoritma A–F düğümlü, dokuz kenarlı bir çizgede çalıştırılır. Kenarlar AB = 1, BC = 5, AD = 4, BE = 3, BD = 7, BF = 6, CF = 9, DE = 8 ve EF = 2'dir.

AB'yi ve EF'yi ikişer bileşen seçer, ama her biri bir kez eklenir. Tur 1'de dört farklı kenar eklenir: AB, BC, AD ve EF. İki bileşen kalır: {A, B, C, D} ve {E, F}. Toplam ağırlık 1 + 5 + 4 + 2 = 12'dir.

Tur 2'de iki bileşen arasındaki kenarlar BE = 3, BF = 6, CF = 9 ve DE = 8'dir. Bileşenlerin ikisi de en ucuz olanı, BE = 3'ü seçer. BE eklenir ve tek bileşen kalır. MST AB, BC, AD, EF, BE kenarlarından oluşur ve ağırlığı 12 + 3 = 15'tir.

Kruskal aynı çizgede kenarları 1, 2, 3, 4, 5 sırasıyla tek tek ekler: AB, EF, BE, AD, BC. Borůvka'da ise ilk turda dört kenar aynı anda eklenir. Bulunan ağaç aynıdır.

4.3.7.4On iki düğümlü örnek

Borůvka'nın gücü büyük çizgelerde daha açık görülür. A–L düğümlü, 20 kenarlı bir çizge ele alınır. Kenarlar şunlardır:

AB 13, AC 6, BC 7, BD 1, CD 14, CE 8, CH 20, DE 9, DF 3, EF 2, EJ 18, GH 15, GJ 19, GK 10, GI 5, HJ 17, IK 11, JK 16, JL 4, KL 12

İlk turda yedi farklı kenar eklenir ve bileşen sayısı 12'den 5'e iner. H'nin seçimi dikkat çekicidir: H'nin bütün kenarları pahalıdır (15, 17, 20) ve en ucuzu GH 15'tir. Bu kenar ağır olmasına rağmen güvenlidir, çünkü {H} kesiminin en hafif kenarıdır. K da GK 10'u seçer; IK 11 ve KL 12 daha pahalıdır. G, H, I ve K böylece tek bileşende toplanır.

İkinci turda {A, C} bileşeni BC 7'yi seçer. {B, D} ve {E, F} bileşenleri aynı DF 3 kenarını seçer. Sağ taraftaki iki bileşen de KL 12'yi seçer. Üç farklı kenar eklenir ve iki bileşen kalır. Üçüncü turda iki yarıyı bağlayan yalnız iki kenar vardır: CH 20 ve EJ 18. Daha ucuz olan EJ 18'dir ve iki bileşen de onu seçer. MST üç turda tamamlanır ve ağırlığı 83'tür.

Kruskal bu çizgede 11 kenarı 11 ayrı adımda ekler. Borůvka aynı ağacı üç turda kurar: 7 + 3 + 1 kenar. Her tur bütün kenarları bir kez tarar; toplam iş 3 · 20 = 60 kenar incelemesidir.

4.3.7.5Java kodu ve izleme

Sunumdaki Java kodu, ana döngünün gövdesini verir. kenarlar kenar listesi, ata ayrık kümelerin ebeveyn dizisi, agac seçilen kenarlar, bilesenSayisi ise kalan bileşen sayısıdır ve başta V'dir.

while (bilesenSayisi > 1) {
  Kenar[] enUcuz = new Kenar[V];
  for (Kenar e : kenarlar) {        // 1) en ucuzlar
    int k1 = bul(ata, e.u), k2 = bul(ata, e.v);
    if (k1 == k2) continue;         // aynı bileşen
    if (enUcuz[k1] == null || e.w < enUcuz[k1].w)
      enUcuz[k1] = e;
    if (enUcuz[k2] == null || e.w < enUcuz[k2].w)
      enUcuz[k2] = e;
  }
  for (Kenar e : enUcuz) {          // 2) hepsini ekle
    if (e == null) continue;
    int k1 = bul(ata, e.u), k2 = bul(ata, e.v);
    if (k1 == k2) continue;         // zaten eklendi
    agac.add(e);
    ata[k1] = k2;                   // birleştir
    bilesenSayisi--;
  }
}

Her turda enUcuz dizisi yeniden oluşturulur. Dizinin indisi bir bileşenin köküdür; hücre o bileşenin şimdiye kadar bulunan en ucuz dış kenarını tutar. Birinci döngü bütün kenarları tarar. Kenarın iki ucunun kökü aynıysa kenar bileşen içindedir ve continue ile geçilir. Değilse kenar iki kökün de adayıdır: her kök için hücre boşsa ya da yeni kenar daha ucuzsa hücreye yazılır.

İkinci döngü enUcuz dizisini gezer. Boş hücreler kök olmayan düğümlere aittir ve atlanır. Her aday kenar için kökler yeniden bulunur. Kökler aynıysa kenar bu turda zaten eklenmiştir ya da iki bileşen başka bir kenarla birleşmiştir; kenar atlanır. Değilse kenar ağaca girer, ata[k1] = k2 ile bileşenler birleşir ve bileşen sayısı bir azalır.

Kod, altı düğümlü örnekte izlenir. Düğümler A–F, indisler 0–5'tir. Kenarlar listede şu sırayla durur: AB, BC, AD, BE, BD, BF, CF, DE, EF.

Tur 1'in taramasında E'nin adayı önce BE(3) olur, sonra EF(2) gelince değişir. F'nin adayı da önce BF(6), sonra EF(2) olur. Ekleme döngüsünde AD eklenirken bul(A), A → B → C yolunu izler ve C'yi bulur. Kökler C ve D olduğu için ata[C] = D yazılır. Tur 2'de bileşen kökleri D ve F'dir; bu yüzden aday kenar enUcuz[D] ve enUcuz[F] hücrelerine yazılır. Sonuç ağırlığı 15'tir.

4.3.7.6Karmaşıklık ve eşitlik bozucu

İspattaki ⌊c/2⌋ gözlemi aslında biraz daha sıkı bir sınır verir. V = 1000 için bileşen sayısı en kötü durumda 1000, 500, 250, 125, 62, 31, 15, 7, 3, 1 diye iner; 9 tur yeter. ⌈log₂ 1000⌉ = 10 ise güvenli bir üst sınırdır. Uygulamada tur sayısı çoğu zaman daha da küçüktür, çünkü bir turda ikiden fazla bileşen birleşebilir. On iki düğümlü örnek 3 turda bitmiştir; ⌈log₂ 12⌉ = 4'tür. Borůvka kenarları sıralamaz; ağırlıkları yalnız karşılaştırır.

Eşit ağırlıklar Borůvka'da özel bir sorun yaratır. Örnek olarak kenarlarının hepsi 1 olan bir a, b, c üçgeni alınsın. Eşitlik keyfî çözülürse a ab'yi, b bc'yi, c de ca'yı seçebilir. Üç kenar aynı anda eklenirse bir döngü oluşur. Bunu önlemek için tutarlı bir eşitlik bozucu gerekir: ağırlıklar eşitse kenarlar örneğin listedeki indislerine göre karşılaştırılır. Böylece kenarların hepsi kesin bir sıraya girer ve döngü oluşamaz. Sunumdaki kodda e.w < enUcuz[k1].w karşılaştırması katı küçüktür; eşitlikte listede önce gelen kenar korunur. Bütün bileşenler aynı listeyi aynı sırayla taradığı için bu seçim tutarlıdır. Kodun ikinci döngüsündeki bul denetimi de ayrıca bir güvenlik sağlar: zaten bağlanmış iki ucu olan kenar eklenmez.

4.3.8Ters silme algoritması

4.3.8.1Fikir: Kruskal'ın aynası

Ters silme algoritması (reverse-delete) da açgözlüdür ve Kruskal'ın 1956 makalesinde önerilmiştir. Kruskal boş çizgeden başlayıp küçük kenarları eklerken, ters silme bütün çizgeden başlar ve büyük kenarları silmeye çalışır. Kenarlar ağırlıklarına göre azalan sırada sıralanır. En ağır kenardan başlanarak çizgenin bağlılığını bozmayan her kenar silinir. Silinmesi çizgeyi koparan kenar yerinde bırakılır.

Algoritma döngü özelliğine dayanır. Bir kenar silindiğinde çizge bağlı kalıyorsa, kenarın iki ucu arasında başka bir yol vardır; kenar bir döngünün üzerindedir. Kenarlar azalan sırada işlendiği için bu döngünün kalan kenarları en fazla onun kadar ağırdır. Daha ağır kenarlar ise zaten ya silinmiş ya da köprü olduğu için kalmıştır. Bu yüzden silinen kenar, kalan çizgedeki bir döngünün en ağır kenarıdır ve döngü özelliğine göre bir MST'ye gerekmez. Silinemeyen kenar ise o anda bir köprüdür ve her kapsayan ağaçta bulunmak zorundadır.

Ters silmenin daha çok kuramsal ve öğretici bir değeri vardır. Her silme için bir bağlılık testi gerekir ve bu test pahalıdır; pratikte algoritma genellikle yavaştır.

4.3.8.2Adımlar, sözde kod ve karmaşıklık

1. Bütün kenarlar ağırlığına göre azalan şekilde sıralanır.
2. Sıradaki en ağır kenar silinir.
3. Çizge artık bağlı değilse silinen kenar geri eklenir.
4. Bütün kenarlar işlenene kadar 2. ve 3. adımlar tekrarlanır.

TERS_SİLME(G):
  MST = tüm kenarlar
  kenarlar.sırala(azalana göre)
  her bir (u, v, ağırlık) için kenarlar içinde:
    MST.sil((u, v, ağırlık))
    ayrikKume.sıfırla()
    her bir (x, y) için MST içinde:
      ayrikKume.birleştir(x, y)
    kök = ayrikKume.bul(V[0])
    eğer bir v için ayrikKume.bul(v) ≠ kök:
      MST.ekle((u, v, ağırlık))  // geri koy
  döndür MST

Sözde kod bağlılığı ayrık kümelerle sınar. Her silmeden sonra yapı sıfırlanır ve kalan bütün kenarlar için birleştir çağrılır. Sonra ilk düğümün kökü bulunur. Kökü bundan farklı bir düğüm varsa çizge kopmuştur ve silinen kenar bir kez geri konur. Geri konan kenar, döngünün başında silinen (u, v, ağırlık) kenarıdır; koşul satırındaki v ise yalnız “bir düğüm” anlamında kullanılmıştır ve iki ad birbirine karıştırılmamalıdır.

Karmaşıklık hesabı basittir. Her kenar için bir bağlılık testi yapılır. Test BFS ya da DFS ile O(V + E) sürer; ayrık kümelerle yeniden kurma da aynı mertebededir. E test toplam O(E · (V + E)) eder. Sıralamanın O(E log E) maliyeti bunun yanında küçük kalır. V = 1000, E = 5000 olan bir çizgede bu, yaklaşık 3 · 10⁷ adım demektir; Kruskal aynı çizgede yaklaşık 6 · 10⁴ adımla yetinir.

4.3.8.3Yedi düğümlü örnek

Ters silme, düğümleri 0–6 olan, 11 kenarlı bir çizgede çalıştırılır. Kenarların toplam ağırlığı 90'dır. Azalan sıra şöyledir:

3–4 15, 5–6 11, 1–3 9, 4–6 9, 1–2 8, 4–5 8, 1–4 7, 0–1 7, 3–5 6, 2–4 5, 0–3 5

İlk üç silme döngü kenarlarını kaldırır. 3–4 = 15 silindiğinde 3 ile 4, 3 → 0 → 1 → 4 yoluyla bağlı kalır. 4–6 = 9 sırası geldiğinde 5–6 zaten silinmiştir; 6'nın tek kenarı 4–6'dır. Bu kenar silinirse 6 yalnız kalır, bu yüzden geri konur. 1–2 = 8 ve 4–5 = 8 silinebilir, çünkü 2'ye 2–4 ile, 5'e 3–5 ile ulaşılır. Bu noktada kalan altı kenar bir ağaç oluşturur ve her biri köprüdür; hiçbiri silinemez. Kalan kenar sayısı 6 = V − 1'dir ve MST ağırlığı 9 + 7 + 7 + 6 + 5 + 5 = 39'dur.

Kruskal aynı çizgede önce 5, 5, 6, 7, 7 ağırlıklı kenarları ekler. Ardından 8'lik iki kenarı ve 9'luk 1–3'ü döngü gerekçesiyle atlar. Son olarak 4–6 = 9'u ekler. İki algoritma aynı ağaca ters yönlerden ulaşır: Kruskal neyin ekleneceğine, ters silme neyin kalacağına karar verir.

4.3.8.4Java kodu ve izleme

void tersSil(int V, List<Kenar> ke) {
  ke.sort((a, b) -> b.w - a.w); // azalan
  int i = 0;
  while (i < ke.size()) {
    Kenar e = ke.remove(i);     // geçici sil
    if (!bagliMi(V, ke)) {
      ke.add(i, e);             // geri koy
      i++;
    }
  }
}

ke.sort((a, b) -> b.w - a.w) kenarları azalan sıraya koyar; karşılaştırıcının b − a biçiminde yazılması sırayı tersine çevirir. i, listede incelenecek sıradaki kenarın indisidir. Döngünün her turunda kenar ke.remove(i) ile geçici olarak silinir. Silmeden sonra liste bir kayar ve sıradaki kenar yine i indisine gelir; bu yüzden silme başarılıysa i artırılmaz. Kenar silinince çizge kopuyorsa ke.add(i, e) kenarı eski yerine koyar ve i bir artar. Döngü i liste boyuna ulaşınca biter. Bu anda listede kalan kenarlar MST'dir. Kodun kullandığı bagliMi metodu BFS ile yazılabilir:

boolean bagliMi(int V, List<Kenar> ke) {
  List<List<Integer>> komsu = new ArrayList<>();
  for (int i = 0; i < V; i++) komsu.add(new ArrayList<>());
  for (Kenar e : ke) { komsu.get(e.u).add(e.v); komsu.get(e.v).add(e.u); }
  boolean[] goruldu = new boolean[V];
  ArrayDeque<Integer> kuyruk = new ArrayDeque<>();
  kuyruk.add(0); goruldu[0] = true;
  int sayac = 1;
  while (!kuyruk.isEmpty()) {
    int x = kuyruk.poll();
    for (int y : komsu.get(x))
      if (!goruldu[y]) { goruldu[y] = true; sayac++; kuyruk.add(y); }
  }
  return sayac == V;            // her düğüme ulaşıldı mı?
}

Metot önce kenar listesinden komşuluk listesini kurar, sonra 0. düğümden BFS başlatır ve ulaşılan düğümleri sayar. Sayı V'ye eşitse çizge bağlıdır. Her çağrı O(V + E) sürer; çağrı sayısı E olduğu için toplam maliyet yukarıda hesaplanan O(E · (V + E))'dir.

Kod, aynı yedi düğümlü çizgenin harfli sürümünde izlenir: 0–6 düğümleri A–G olarak adlandırılır. Kenar listesi alfabetik sırayla verilir: AB 7, AD 5, BC 8, BD 9, BE 7, CE 5, DE 15, DF 6, EF 8, EG 9, FG 11. Sıralama kararlıdır; eşit ağırlıklı kenarlar bu sırayı korur.

EG adımında FG zaten silinmiştir ve G'nin tek bağlantısı EG'dir. AB adımına gelindiğinde A'nın kenarları AB ve AD, D'nin kalan kenarları AD ve DF, F'nin kalan kenarı ise yalnız DF'dir. AB silinirse A, D ve F öbür düğümlerden kopar. Son satırdan sonra i = 6 liste boyuna eşittir ve döngü biter. Kalan ağaç AB, AD, BE, CE, DF ve EG kenarlarından oluşur; ağırlığı 39'dur.

4.3.9Dört algoritmanın karşılaştırması

Dört algoritma aynı problemi çözer ve aynı kuramsal temele dayanır, ama çalışma biçimleri ve maliyetleri farklıdır. Tablo 4.3.20 farkları bir arada gösterir.

Tablonun satırları birkaç pratik soruya karşılık gelir. Çizge bir kenar listesi olarak geliyor ve seyrekse Kruskal en kolay ve en hızlı seçimdir. Çizge bir komşuluk matrisiyle veriliyor ve yoğunsa, dizi taramalı Prim O(V²) ile en iyi sonucu verir; sıralama ya da heap gerekmez. Seyrek çizge komşuluk listesiyle verildiğinde heap'li Prim de Kruskal ile aynı mertebededir. İş birden çok işlemciye dağıtılacaksa Borůvka'nın bağımsız seçimleri büyük kolaylık sağlar. Ters silme ise üretim kodunda pek kullanılmaz; döngü özelliğinin algoritmik bir karşılığı olarak öğreticidir.

Bağlı olmayan çizgelerde davranış farkı da önemlidir. Kruskal ve Borůvka her bileşeni ayrı ayrı tamamlar ve bir minimum kapsayan orman döndürür. Prim yalnız başlangıç düğümünün bileşenini kapsar; ormanı bulmak için kapsanmayan her bileşenden yeniden başlatılmalıdır. Ters silme hiçbir bileşeni koparmadığı için bileşenleri olduğu gibi korur; bağlılık testinin bileşen sayısını koruyacak biçimde yazılması yeter.

Dokuz düğümlü çizge farkı somut olarak gösterir. Kruskal ve Prim aynı ağacı (29) bulur. Kruskal kenarları 1, 1, 2, 3, 4, 5, 6, 7 sırasıyla, Prim ise 4, 7, 1, 1, 2, 3, 6, 5 sırasıyla ekler. Kruskal'ın ekleme sırası ağırlık sırasıdır; Prim'in sırası ise ağacın büyüme yönünü izler.

Bu dört algoritma tarihin sonu değildir. Karger, Klein ve Tarjan 1995'te beklenen süresi doğrusal olan rastgele bir algoritma verdi. Bernard Chazelle 2000'de ters Ackermann fonksiyonuyla neredeyse doğrusal süreli belirlenimci bir algoritma yayımladı. Belirlenimci, kesin doğrusal süreli bir MST algoritmasının var olup olmadığı hâlâ açık bir sorudur.

4.3.10Sık yapılan hatalar

Bu kesim, notun içine dağılmış uyarıları ve sunumdaki hata listesini bir arada toplar.

4.3.11Özet

• Kapsayan ağaç ve MST: bağlı, yönsüz bir çizgenin bütün düğümlerini içeren, bağlı ve döngüsüz alt çizgesi kapsayan ağaçtır ve tam V − 1 kenarlıdır. Toplam ağırlığı en küçük olana minimum kapsayan ağaç denir. Tam çizgede nⁿ⁻² kapsayan ağaç vardır; bu yüzden hepsini denemek yerine açgözlü algoritmalar kullanılır.
• Kesim özelliği: her kesimin en hafif kenarı bir MST'ye aittir; kesimin en hafif kenarı tekse her MST'dedir. Kruskal, Prim ve Borůvka bu özelliğe dayanır.
• Döngü özelliği: bir döngünün tek en ağır kenarı hiçbir MST'de yer almaz. Ters silme bu özelliğe dayanır. Bütün ağırlıklar farklıysa MST tektir.
• Kruskal: kenarlar artan sırada incelenir; bul(u) ≠ bul(v) ise kenar eklenir ve iki ağaç birleşir. Süre O(E log E) = O(E log V)'dir ve sıralama baskındır.
• Ayrık kümeler: ata[] ormanında her küme bir ağaçtır, kök temsilcidir. Yol kısaltma ve rütbeye göre birleştirme birlikte işlem başına amortize O(α(V)) verir; α pratikte 4'ü geçmez. Yalnız rütbe ile her işlem O(log V)'dir.
• Prim: tek bir ağaç büyütülür; anahtar[v], v'yi ağaca bağlayan en ucuz tek kenarın ağırlığıdır. Dizi taramasıyla O(V²), ikili heap ile O((V + E) log V), tembel sürümle O(E log E), Fibonacci heap ile O(E + V log V) sürer.
• Prim ve Dijkstra: kodlar neredeyse aynıdır; Prim tek kenar ağırlığını, Dijkstra kaynaktan toplam uzaklığı anahtar yapar. Prim'in sonucu kaynaktan bağımsız ağırlıktadır ve negatif ağırlıkla da doğrudur.
• Borůvka: her turda her bileşen en ucuz dış kenarını seçer ve bu kenarlar aynı anda eklenir. Bileşen sayısı her turda en az yarıya iner; en fazla ⌈log₂ V⌉ tur, toplam O(E log V). Eşit ağırlıklarda tutarlı bir eşitlik bozucu gerekir.
• Ters silme: kenarlar azalan sırada silinir; çizge koparsa kenar geri konur. Her silmede bağlılık testi yapıldığı için süre O(E · (V + E))'dir.
• Seçim: seyrek çizge ve kenar listesi → Kruskal; yoğun çizge ve komşuluk matrisi → dizi taramalı Prim; paralel hesaplama → Borůvka; bağlı olmayan çizgede orman → Kruskal ya da Borůvka.

4.3.12Kavram listesi

• kapsayan ağaç spanning tree
• minimum kapsayan ağaç minimum spanning tree (MST)
• minimum kapsayan orman minimum spanning forest
• bileşen connected component
• kesim cut
• kesim özelliği cut property
• döngü özelliği cycle property
• köprü bridge
• açgözlü algoritma greedy algorithm
• değiştirme argümanı exchange argument
• Kruskal algoritması Kruskal's algorithm
• ayrık kümeler union-find, disjoint sets
• yol kısaltma path compression
• rütbeye göre birleştirme union by rank
• amortize analiz amortized analysis
• Prim algoritması Prim's algorithm
• öncelikli kuyruk priority queue
• ebeveyn parent
• komşuluk matrisi adjacency matrix
• komşuluk listesi adjacency list
• Dijkstra algoritması Dijkstra's algorithm
• Borůvka algoritması Borůvka's algorithm
• ters silme algoritması reverse-delete algorithm
• darboğaz bottleneck

4.3.13Kendini Dene

Sorular 1–6, aynı K çizgesini kullanır. K'nin düğümleri A–F, kenarları AB = 7, AC = 3, AD = 6, BC = 4, BE = 2, CD = 5, CE = 8, CF = 9, DF = 1 ve EF = 10'dur.

1. K'de {A, C} | {B, D, E, F} kesimini geçen kenarlar hangileridir? Kesim özelliği hangi kenar için ne söyler?

   Cevap

   Kesimi geçen kenarlar AB 7, AD 6, BC 4, CD 5, CE 8 ve CF 9'dur. AC 3 kesimi geçmez, çünkü iki ucu da aynı taraftadır. En hafif geçen kenar BC 4'tür ve tek en hafif olduğu için her MST'de bulunur.

2. Kruskal K'de hangi kenarları hangi sırayla ekler? Kaç kenar reddedilir, hangi kenarlar hiç incelenmez? w(T) kaçtır?

   Cevap

   Sıralı liste DF 1, BE 2, AC 3, BC 4, CD 5, AD 6, AB 7, CE 8, CF 9, EF 10'dur. İlk beş kenarın hepsi iki ayrı ağacı bağlar ve eklenir; hiçbir kenar reddedilmez. Beşinci ekleme V − 1 = 5'e ulaştığı için AD, AB, CE, CF ve EF hiç incelenmez. w(T) = 1 + 2 + 3 + 4 + 5 = 15.

3. Prim K'de A'dan çalıştırılırsa düğümler hangi sırayla ağaca girer? C ağaca girdikten sonra anahtar dizisi nedir?

   Cevap

   Sıra A (0), C (3), B (4), E (2), D (5), F (1)'dir. A'dan sonra anahtarlar B = 7, C = 3, D = 6, E = F = ∞ olur. C girince B, BC ile 4'e; D, CD ile 5'e iner; E = 8 ve F = 9 olur. Dizi A, …, F için 0, 4, 3, 5, 8, 9'dur. Ebeveynler B → C, D → C, E → B, F → D olarak sonuçlanır; toplam yine 15'tir.

4. Borůvka K'de kaç turda biter? Her turda hangi kenarlar eklenir?

   Cevap

   Tur 1'de A ve C aynı AC 3'ü, B ve E aynı BE 2'yi, D ve F aynı DF 1'i seçer. Üç farklı kenar eklenir ve {A, C}, {B, E}, {D, F} bileşenleri oluşur. Tur 2'de {A, C} ve {B, E} BC 4'ü, {D, F} CD 5'i seçer. İki kenar eklenir ve tek bileşen kalır: 2 tur, ağırlık 15.

5. Ters silme K'de hangi kenarları siler? İlk “kalır” kararı hangi kenarda verilir ve neden?

   Cevap

   Silinenler EF 10, CF 9, CE 8, AB 7 ve AD 6'dır. İlk “kalır” kararı CD 5'te verilir: AD ve CF silindikten sonra D ile F'yi geri kalan düğümlere bağlayan tek kenar CD'dir. Ardından BC, AC, BE ve DF de köprü oldukları için kalır.

6. K'de A'dan Dijkstra çalıştırılsa en kısa yollar ağacı hangi kenarlardan oluşur ve ağırlığı kaçtır? Bu ağacın Prim'in A'dan bulduğu ağaçtan farkı nedir?

   Cevap

   Uzaklıklar B = 7, C = 3, D = 6, E = 9 (A → B → E), F = 7 (A → D → F)'dir. Ağaç AB, AC, AD, BE, DF kenarlarından oluşur ve ağırlığı 7 + 3 + 6 + 2 + 1 = 19'dur. Prim'in ağacı (AC, BC, CD, BE, DF) 15 ağırlıklıdır. Dijkstra B'ye doğrudan AB 7 ile gider; A → C → B yolu da 7'dir ve daha kısa değildir. Prim ise B'yi C'ye 4'lük kenarla bağlar.

7. 0–6 öğeli bir ayrık kümeler yapısında sunumdaki yol kısaltmalı bul ve birlestir kullanılıyor. Sırasıyla birlestir(0, 1), (2, 3), (0, 2), (4, 5), (6, 4), (5, 0) çağrılıyor. Son ata dizisi nedir? Ardından bul(6) neyi değiştirir?

   Cevap

   Adımlar: ata[0] = 1; ata[2] = 3; bul(0) = 1, bul(2) = 3 → ata[1] = 3; ata[4] = 5; bul(6) = 6, bul(4) = 5 → ata[6] = 5. Son çağrıda bul(5) = 5; bul(0), 0 → 1 → 3 yolunu izler ve 0'ı doğrudan 3'e bağlar. Ardından ata[5] = 3 yazılır. Dizi [3, 3, 3, 3, 5, 3, 5] olur. bul(6), 6 → 5 → 3 yolunu izler ve ata[6] = 3 yapar: [3, 3, 3, 3, 5, 3, 3]. 4 bu yolda olmadığı için 5'e bağlı kalır.

8. K'nin en büyük kapsayan ağacı nasıl bulunur ve ağırlığı kaçtır?

   Cevap

   Kruskal kenarları azalan sırayla işler (ya da bütün ağırlıklar −w yapılıp olağan Kruskal çalıştırılır). Sıra EF 10, CF 9, CE 8, AB 7, AD 6, CD 5'tir. EF, CF eklenir; CE döngü kurar (C–F–E); AB, AD eklenir; son olarak CD eklenir. Ağaç EF, CF, AB, AD, CD'dir ve ağırlığı 10 + 9 + 7 + 6 + 5 = 37'dir.

9. 50 düğümlü, 3 bileşenli bir çizgede minimum kapsayan ormanda kaç kenar vardır? Sunumdaki Kruskal kodu bu çizgede ne yapar?

   Cevap

   Her bileşen için (bileşen boyu − 1) kenar gerekir; toplam 50 − 3 = 47 kenardır. Sunumdaki kod 49 kenar bekler. 47 kenar ekledikten sonra liste biter ve ke.get(k++) IndexOutOfBoundsException fırlatır.

10. V = 10⁴ düğümlü bir çizgede Prim'in iki sürümü karşılaştırılıyor: dizi taramalı O(V²) ve ikili heap'li O((V + E) log V). E = 5 · 10⁴ ve E = 5 · 10⁷ için hangisi daha az iş yapar?

    Cevap

    V² = 10⁸, log₂ 10⁴ ≈ 13,3'tür. E = 5 · 10⁴ için heap sürümü yaklaşık 6 · 10⁴ · 13,3 ≈ 8 · 10⁵ adım atar; yüz kattan fazla daha iyidir. E = 5 · 10⁷ (tam çizgenin aşağı yukarı tamamı) için heap sürümü yaklaşık 6,6 · 10⁸ adım atar; dizi sürümü 6–7 kat daha iyidir.

4.3.14İleri okuma

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (4. baskı, 2022), Bölüm 19 ve 21: ayrık kümelerin ters Ackermann analizini ve genel MST yöntemini, güvenli kenar kavramıyla birlikte ispatlarıyla verir.
• R. Sedgewick ve K. Wayne, Algorithms (4. baskı, 2011), Kesim 1.5 ve 4.3: ayrık kümeleri, tembel ve istekli Prim'i ve Kruskal'ı Java koduyla ve deneysel ölçümlerle anlatır.
• R. L. Graham ve P. Hell, “On the History of the Minimum Spanning Tree Problem”, Annals of the History of Computing 7(1), 1985: Borůvka, Jarník, Kruskal ve Prim'in çalışmalarını ve problemin erken tarihini karşılaştırmalı olarak inceler.
• R. E. Tarjan, “Efficiency of a Good But Not Linear Set Union Algorithm”, Journal of the ACM 22(2), 1975: yol kısaltma ve rütbeye göre birleştirmenin ters Ackermann sınırını ilk kez kanıtlayan makale.

4.3.15Kaynaklar

1. O. Borůvka, “O jistém problému minimálním”, Práce Moravské přírodovědecké společnosti 3, 1926.
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022 (Bölüm 19: ayrık kümeler, Bölüm 21: MST).
3. R. L. Graham, P. Hell, “On the History of the Minimum Spanning Tree Problem”, Annals of the History of Computing 7(1), 43–57, 1985.
4. J. B. Kruskal, “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem”, Proceedings of the American Mathematical Society 7(1), 1956.
5. R. C. Prim, “Shortest Connection Networks and Some Generalizations”, Bell System Technical Journal 36(6), 1957.
6. R. Sedgewick, K. Wayne, Algorithms, 4. baskı, Addison-Wesley, 2011 (Bölüm 4.3: Minimum Spanning Trees).
7. R. E. Tarjan, “Efficiency of a Good But Not Linear Set Union Algorithm”, Journal of the ACM 22(2), 1975.

İlgili sayfalar: Bölüm 4.3 sunumu · Çalışma soruları · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.