Bölüm 17: Minimum Kapsayan Ağaçlar

17.1Kapsayan ağaçlar

Bir çizge G = (V, E), düğümlerden (V) ve düğüm çiftlerini birleştiren kenarlardan (E) oluşur. Notta düğüm sayısı n = |V|, kenar sayısı e = |E| ile gösterilir ve aksi söylenmedikçe çizge yönsüzdür. Her düğüm çiftinin arasında bir yol varsa çizge bağlantılıdır (connected). Başladığı düğüme geri dönen yola döngü (cycle) denir. Bağlantılı ve döngüsüz bir çizge ağaçtır; ağaçta kök seçmek zorunlu değildir.

Bu notun bütün sorusu şu cümleye sığar: bir çizgenin düğümlerini birbirine bağlamak için kenarlarının hangileri yeter ve bunların en ucuzu hangisidir? Önce “yeter” sözcüğünü kesinleştirelim.

17.1.1Gezinme kenarları ikiye ayırır

Bir çizgede gezinmenin iki temel yolu vardır. Derinlik öncelikli arama (depth-first search, DFS) bir komşuya geçer ve olabildiğince derine iner; gidecek yer kalmayınca geri döner. Özyinelemeyle ya da bir yığınla yazılır; “önce derinliğine arama” adıyla da anılır. Genişlik öncelikli arama (breadth-first search, BFS) başlangıç düğümünün bütün komşularını, sonra onların komşularını ziyaret eder; bir kuyrukla yazılır. İkisi de her düğümü bir kez işaretler ve komşuluk listesiyle O(n + e) sürede biter.

Bağlantılı bir çizgede gezinme bütün düğümleri ziyaret edince kenarlar iki gruba ayrılmış olur:

• T: ağaç kenarları (tree edges). Gezinmenin işlediği, yani daha önce görülmemiş bir düğüme götüren kenarlardır. Başlangıç dışındaki her düğüme tam bir kez böyle bir kenarla varılır. Bu yüzden ağaç kenarlarının sayısı tam olarak n − 1'dir.
• N: ağaç dışı kenarlar (non-tree edges). Gezinmenin baktığı ama işlemediği kenarlardır; öteki ucu zaten işaretlidir. DFS'de bunlara geri kenar (back edge), BFS'de çapraz kenar (cross edge) da denir.

Şekil 17.1'deki çizgenin 10 kenarı vardır: (0,1), (0,2), (1,3), (1,4), (2,5), (2,6), (3,7), (4,7), (5,7), (6,7). Komşuluk listeleri küçükten büyüğe sıralıdır. Tablo 17.1 DFS'nin hangi kenarı neden işlediğini ya da atladığını sırasıyla gösterir.

Yedi ağaç kenarı (0,1), (1,3), (3,7), (7,4), (7,5), (5,2), (2,6)'dır; n − 1 = 7 beklentisiyle örtüşür. Geri dönüşlerde bakılan öteki kenarlar (ör. 3'ün listesindeki 1) yeni bilgi vermediği için tabloya yazılmadı. BFS aynı çizgede 0'dan başlayınca önce 1 ve 2'yi, sonra 3, 4, 5, 6'yı, en son 7'yi işaretler. Ağaç kenarları (0,1), (0,2), (1,3), (1,4), (2,5), (2,6), (3,7) olur. 7'ye ilk ulaşan kenar (3,7)'dir; (4,7), (5,7), (6,7) ağaç dışında kalır.

İki gezinme aynı çizgeden iki farklı ağaç çıkardı. İkisi de bütün düğümleri kapsar, ikisinde de döngü yoktur. Demek ki “bütün düğümleri bağlamaya yeten kenarlar” tek bir küme değildir. Başlangıç düğümü ya da komşuların sırası değişince yine başka ağaçlar çıkar.

17.1.2Kapsayan ağacın tanımı

Tanımdaki iki koşul birbirini tamamlar. “Bütün düğümleri içerir” koşulu ağacın kapsayıcı olmasını sağlar: hiçbir düğüm dışarıda kalmaz. “Kenarları E'den seçilir” koşulu yeni bağlantı uydurmayı yasaklar: yalnız çizgede var olan kenarlar kullanılabilir. Bağlantılı olmayan bir çizgenin kapsayan ağacı yoktur. Böyle bir çizgede her bileşenin ayrı ayrı kapsayan ağacı bulunur ve bunların topluluğuna kapsayan orman (spanning forest) denir.

Şekil 17.2'nin solundaki K₄ tam çizgedir (complete graph): her düğüm çifti bir kenarla bağlıdır, toplam 4 · 3 / 2 = 6 kenar vardır. Yanındaki beş çizimin her biri bu altı kenardan üçünü seçer. Hepsinde dört köşe de kullanılır ve hiçbirinde döngü yoktur; beşi de kapsayan ağaçtır.

Bu beş ağaçtan a, c, d ve e aynı biçimdedir: dört düğüm tek bir çizgi üzerinde sıralanmıştır. Yalnız hangi köşenin yolun neresinde durduğu değişir. b ise farklıdır: bir köşe öteki üçüne doğrudan bağlanmıştır. Birinci biçime yol, ikincisine yıldız denir.

Şekildeki ağaçlar için a ≡ c ≡ d ≡ e yazılır; b bunların hiçbiriyle eş biçimli değildir. Bunu görmenin kısa yolu derecelere bakmaktır. Yolda iki düğümün derecesi 1, ikisininki 2'dir. Yıldızda bir düğümün derecesi 3, üçününki 1'dir. Eş biçimli iki çizgede derece dizileri aynı olmak zorundadır; burada farklı olduğu için a ile b eş biçimli olamaz. Tersi doğru değildir: derece dizileri aynı olan iki çizge eş biçimli olmayabilir. Bu yüzden derece karşılaştırması eş biçimliliği ancak çürütebilir, kanıtlayamaz.

K₄'ün kaç kapsayan ağacı olduğunu saymak kolaydır. Altı kenardan üçü C(6, 3) = 20 biçimde seçilir. Bu seçimlerin dördü üçgendir: dört köşeden üçünü seçip aralarındaki üç kenarı almak döngü kurar ve dördüncü köşeyi dışarıda bırakır. Geriye kalan 16 seçimin hepsi ağaçtır. Yıldızların sayısı merkez seçimine eşittir: 4. Yolların sayısı dört düğümün sıralamalarından bulunur. 4! = 24 sıralama vardır, ama her yol iki kez (baştan ve sondan) okunur. Yol sayısı 24 / 2 = 12'dir. Toplam 12 + 4 = 16 eder.

Formül n = 4 için 4² = 16 verir ve yukarıdaki sayımla örtüşür. Sayı çok hızlı büyür: K₅'in 125, K₁₀'un yüz milyon kapsayan ağacı vardır. Kanıtı bu notun kapsamı dışındadır. Burada önemli olan sonuçtur: kapsayan ağaçları tek tek üretip en iyisini seçmek, küçük çizgelerde bile umutsuz bir iştir. Kenarlara ağırlık verildiğinde “kaç tane?” sorusu “hangisi en ucuz?” sorusuna dönüşür ve bu sayının büyüklüğü yeniden karşımıza çıkar.

17.1.3Eş biçimlilik, çizim ve düzlemsellik

Bir çizge, kâğıda çizilmiş hâlinden ibaret değildir. Çizgeyi düğümleri ve kenarları belirler; düğümlerin kâğıttaki yeri bir tercihtir. Aynı çizge birbirine hiç benzemeyen biçimlerde çizilebilir. Şekil 17.3 bunun çarpıcı bir örneğidir.

K_3,3, iki gruba ayrılmış altı düğümden oluşur: {1, 2, 3} ve {a, b, c}. Her grubun her düğümü öteki grubun üç düğümüne bağlıdır, kendi grubundakilere bağlı değildir. Toplam 3 · 3 = 9 kenar vardır. Soldaki çizim bu tanımı doğrudan uygular ve kenarlar birbirine karışır. Sağdaki çizimde düğümler başka yerlere konmuş, (1,c) kenarı dışarıdan dolaştırılmıştır. Dokuz kenarın hepsi hâlâ oradadır, ama artık yalnız bir kesişme kalmıştır.

İki çizimin aynı çizge olduğunu göstermek, eş biçimliliği göstermektir: soldaki her düğüme sağda bir düğüm karşılık gelir ve kenarlar karşılıklı eşlenir. Buradaki eşleme kolaydır, çünkü etiketler korunmuştur. Etiketsiz iki çizim verildiğinde ise problem zorlaşır. Derece dizisi gibi basit ölçütler yetmez; DFS ya da BFS ile düğümleri katmanlara ayırmak eşlemeyi daraltmaya yardım eder, ama genel çözüm vermez. Çizge eş biçimliliği, verimli bir algoritması bilinip bilinmediği uzun süre tartışılmış ünlü bir problemdir. Hoca bu problemi güzel bir dördüncü sınıf projesi olarak önerir: üç boyutlu bir gösterimle bir çizimi ötekine dönüştüren, hangi düğümlerin yer değiştirmesi gerektiğini bulan bir program. Ardından bu tür soruların gerçekten zor olduğunu, ciddi biçimde ancak yüksek lisans ya da doktorada uğraşılabileceğini ekler. Vurgulanan, problemin çözülemez olduğu değil, emek istediğidir.

Kesişme sorusunun da bir adı vardır. Kenarları hiç kesişmeden çizilebilen çizgeye düzlemsel (planar) denir. K_3,3 düzlemsel değildir: düğümler nasıl yerleştirilirse yerleştirilsin, en az bir kesişme kalır. Sağdaki çizim bu alt sınıra ulaşmıştır. Sorunun mühendislikte somut bir karşılığı vardır. Bir baskılı devre kartında iletken yollar aynı katmanda kesişemez. K_3,3 biçiminde bağlanması gereken bir devre tek katmana sığmaz, en az iki katman ister.

17.1.4Kaç farklı kapsayan ağaç vardır?

Kapsayan ağaçları üretmenin en kaba yolu bütün olası kenar kümelerini denemektir. Kapsayan ağaçta tam n − 1 kenar bulunduğundan e kenar arasından n − 1 tanesi seçilir. Bu, C(e, n − 1) biçimde yapılabilir. Her seçim için döngü olup olmadığı denetlenir; döngüsüz olanlar ağaçtır. Eş biçimli ağaçlar ayrıca sayılmak istenmiyorsa bir de eş biçimlileri ayıklamak gerekir.

Kare biçimli dört düğümlü bir çizge düşünelim: A, B, C, D köşeleri sırayla bağlı, ayrıca A ile C arasında bir köşegen var. Beş kenardan üçü C(5, 3) = 10 biçimde seçilir. Bunlardan ikisi üçgendir (ABC ve ACD) ve döngü kurar; geriye 8 kapsayan ağaç kalır.

Daha akıllıca bir yöntem, bir kapsayan ağaçtan başlayıp kenar değiştirerek öteki ağaçlara geçmektir. Şekil 17.4 yöntemi adım adım gösterir.

1. Önce bir kapsayan ağaç bulunur, örneğin DFS ile. Şekilde T = {(A,B), (B,C), (C,D)}'dir.
2. Ağaç dışı bir kenar eklenir. Ağaçta her düğüm çifti arasında tek yol olduğu için yeni kenar tam olarak bir döngü kurar. (D,A) eklenince döngü A-B-C-D-A olur.
3. Döngüdeki kenarlardan biri çıkarılır. Döngü kırılır, düğümler yine bağlı kalır; sonuç yeni bir kapsayan ağaçtır. (A,B) çıkarılınca {(B,C), (C,D), (D,A)} elde edilir. (A,B) geri konup (B,C) çıkarılınca bir başkası, (C,D) çıkarılınca bir üçüncüsü bulunur.
4. İşlem bütün ağaç dışı kenarlar için ve bulunan her yeni ağaç için tekrarlanır. Bu çizgede sonunda 8 kapsayan ağacın hepsine ulaşılır.

Yöntem çalışır ama uzundur. Aynı ağaca farklı yollardan defalarca varılır ve her yeni ağacın daha önce bulunup bulunmadığı ayrıca denetlenmelidir. Bu yüzden ağaç saymak ya da en ucuz ağacı bulmak için tercih edilmez. Kesin sayı gerektiğinde Kirchhoff'un matris-ağaç teoremi kullanılır. Bu teorem, çizgenin derece ve komşuluk bilgisinden kurulan bir matrisin determinantını alarak sayıyı tek hamlede verir. Teoreme göre Şekil 17.1'deki sekiz düğümlü çizgenin 64, notun ana örneği olan yedi köy çizgesinin 46 kapsayan ağacı vardır. Teoremin ayrıntısı ileri bir konudur.

17.1.5Kapsayan ağacın özellikleri

Kapsayan ağacın algoritmalarda kullanılan dört özelliği vardır. Şekil 17.5 bunları BFS kapsayan ağacı üzerinde gösterir.

Şekilde bu özellikler tek tek görülür. Sol çizimdeki BFS ağacı 8 düğümü 7 kenarla bağlar. Ortadaki çizimde (6,7) eklenince 6'dan 7'ye ağaç üzerindeki tek yol 6-2-0-1-3-7 ile yeni kenar birleşir ve 6-2-0-1-3-7-6 döngüsü kapanır. Bu çizge artık ağaç değildir. Sağdaki çizimde (0,2) silinince 2, 5 ve 6 düğümleri 0'a bağlanamaz hâle gelir. Kapsayan ağaç, düğümleri bağlı tutan alt çizgeler arasında en az kenarlı olanıdır. Bir kenar fazlası döngü, bir kenar eksiği kopukluk demektir.

İkinci ve üçüncü özellik birlikte kullanılınca kapsayan ağaç üretme yöntemi ortaya çıkar: ağaç dışı bir kenar eklenir, oluşan tek döngüden bir kenar çıkarılır. Minimum kapsayan ağaç algoritmalarının doğruluk kanıtları da aynı iki özelliğe dayanır.

Kapsayan ağaçların uygulamaları da bu özelliklerden gelir:

• Gereksiz bağlantıları atmak. Bir bilgisayar ağında döngüler, yayınlanan bir paketin sonsuza kadar dolaşmasına yol açabilir. Ağın bir kapsayan ağacı seçilir ve yalnız onun hatları kullanılır.
• Yayın ağacı. Bir kaynaktan bütün düğümlere ileti göndermek (broadcast) için kapsayan ağacın kenarları izlenir; her düğüm iletiyi bir kez alır.
• Elektrik devreleri. Kirchhoff, devre denklemlerinin bağımsız bir kümesini bulmak için kapsayan ağaçları kullanmıştır. Her ağaç dışı kenar tek bir döngü kurar; bu döngülerin her biri bağımsız bir gerilim denklemi verir.

17.2Minimum maliyetli kapsayan ağaç

17.2.1Ağırlıklı çizge ve problem

Gerçek problemlerde kenarlar eşit değildir. İki şehir arasındaki yolun bir uzunluğu, iki bilgisayar arasındaki hattın bir kira bedeli, iki köy arasına çekilecek kablonun bir maliyeti vardır. Kenarlarına böyle bir sayı atanmış çizgeye ağırlıklı çizge (weighted graph) denir ve G(V, E) yerine G(V, E, w) yazılır. Burada w(u, v), (u, v) kenarının ağırlığıdır. Bu notta ağırlığa maliyet de denir.

Tanım “en küçük olan” der, “en küçük olanlar” demez; yine de birden çok kapsayan ağaç aynı en küçük maliyeti verebilir. Kenar ağırlıklarının hepsi farklıysa minimum kapsayan ağaç tektir. Eşit ağırlıklar varsa birden çok ağaç olabilir, ama hepsinin maliyeti aynıdır.

İki örnek problemi somutlaştırır. Birincisinde düğümler bir kurumun bilgisayarlarıdır, kenar ağırlıkları iki bilgisayar arasına hat çekmenin maliyetidir. Bütün bilgisayarları birbirine ulaştıran en ucuz hat kümesi aranır. İkincisinde yedi köye elektrik ya da fiber optik kablo götürülecektir. Fizibilite çalışması hangi köyden hangisine kaç kilometre kablo gerektiğini çıkarmıştır. Arada dağ ya da göl olduğu için doğrudan bağlanamayan köy çiftlerinin maliyeti sonsuzdur; bu kenarlar çizgeye hiç yazılmaz.

Şekil 17.6'daki çizgenin kenarları ağırlıklarıyla şunlardır: (0,1) = 28, (0,5) = 10, (1,2) = 16, (1,6) = 14, (2,3) = 12, (3,4) = 22, (3,6) = 18, (4,5) = 25, (4,6) = 24. Notun bütün Kruskal ve Prim izlemeleri bu çizge üzerindedir. Çizgenin 46 kapsayan ağacı vardır. Dokuz kenardan altısı C(9, 6) = 84 biçimde seçilir; bunların 38'i döngü kurar. 46 ağacın maliyetleri 99 ile 129 arasında değişir. En ucuz ağacın maliyeti 99'dur ve tektir; ondan sonraki en ucuz iki ağacın maliyeti 101'dir. Bu sayılar bütün seçimlerin bilgisayarla tek tek denenmesiyle bulundu. Amaç, bu denemeyi yapmadan 99'luk ağaca doğrudan ulaşmaktır.

Hoca burada önemli bir noktanın altını çizer: minimum kapsayan ağaç ararken döngüden kaçınılır. Bir köye iki yoldan elektrik gelmesi, örneğin “Aşağı Tepecik'ten gelmezse Yukarı Tepecik'ten gelsin” diye yedek hat çekilmesi bu problemin konusu değildir. Döngü, yedek bağlantı demektir ve yedek bağlantı fazladan maliyettir. Güvenilirlik isteyen ağlar başka problemlerle tasarlanır.

17.2.2Açgözlü yaklaşım

Minimum kapsayan ağaç için birçok algoritma bilinir: Kruskal, Prim ve Sollin (Borůvka) algoritmaları en tanınmışlarıdır; ters silme (reverse-delete) adlı bir yöntem de vardır. Bu notun ağırlığı ilk ikisindedir, öteki ikisi kısaca anlatılır.

Algoritma tasarımında birkaç genel yöntem vardır. Geri izleme (backtracking) kısmi bir çözümü adım adım genişletir, çıkmaza girince son kararı geri alır. Dinamik programlama küçük alt problemlerin çözümlerini saklayıp büyüklerini onlardan kurar. Açgözlü yöntem (greedy method) ise her adımda o an en iyi görünen seçimi yapar ve bu seçimi bir daha değiştirmez. Hoca bu tutuma “ısrarcı” der: açgözlü algoritma geri dönmez, bir kez aldığı kenarı bırakmaz.

Minimum kapsayan ağaç algoritmaları açgözlüdür ve üç kurala uyar:

1. Döngü oluşturan kenar alınmaz.
2. Seçilebilecek kenarlar arasından en az maliyetli olan tercih edilir.
3. n düğümlü çizgede tam n − 1 kenar seçilir.

Birinci kural sonucun ağaç olmasını, üçüncüsü bütün düğümleri kapsamasını sağlar; ikisi birlikte Teorem 17.2'nin (ii) ve (iii) koşullarıdır. İkinci kural maliyeti küçük tutar. Algoritmalar arasındaki fark, “seçilebilecek kenarlar” kümesini nasıl tanımladıklarındadır. Kruskal'da bu küme henüz denenmemiş bütün kenarlardır. Prim'de yalnız büyüyen ağaca dokunan kenarlardır.

Bölümün sunumu Michelangelo'ya atfedilen bir sözle açılır: “Güzellik, fazlalıktan arınmışlıktır.” Minimum kapsayan ağaç tam olarak budur: bağlantıyı koruyan, fazlası atılmış en yalın ağ.

17.2.3Açgözlü seçim neden doğru sonuç verir?

Açgözlü algoritmalar çoğu problemde en iyi sonucu bulamaz. Bozuk para üstü vermek için her seferinde en büyük madeni parayı seçmek bazı para sistemlerinde fazla sayıda para kullandırır. O hâlde minimum kapsayan ağaçta açgözlü seçimin neden pişman olmadığı gösterilmelidir. Bunun anahtarı kesit özelliğidir.

Kruskal ve Prim her adımda bir kesitin en hafif kenarını seçer. Prim'de kesit apaçıktır: S o ana kadar kurulan ağacın düğümleridir ve seçilen kenar, ağaçtan dışarı çıkan en ucuz kenardır. Kruskal'da seçilen kenarın uçları iki ayrı öbekte durur. Bir ucun öbeği S alınırsa, kenar bu kesiti geçen kenarların en ucuzudur. Daha ucuz bir geçiş kenarı olsaydı Kruskal ona daha önce bakmış ve iki öbek zaten birleşmiş olurdu. Böylece iki algoritma da her adımda bir minimum kapsayan ağacın kenarını seçer ve hiçbir seçim sonradan geri alınmak zorunda kalmaz.

Kesit özelliğinin bir ikizi daha vardır: döngü özelliği. Bir döngüdeki en ağır kenar (ağırlıklar farklıysa) hiçbir minimum kapsayan ağaçta bulunmaz. Ters silme yöntemi bu özelliğe dayanır.

17.3Kruskal algoritması

17.3.1Algoritma

Joseph B. Kruskal algoritmayı 1956'da yayımladı. Fikri bir cümledir: kenarları ucuzdan pahalıya sırayla dene; döngü kurmayanı al, kuranı bırak. Algoritmanın doğruluğunun kanıtı vardır ve kesit özelliğine dayanır. Kanıtı okumak algoritmanın neden böyle kurulduğunu daha iyi anlatır. Sözde kodu şöyledir:

T = {};                    /* seçilen kenarlar */
while (|T| < n-1 && E ≠ Ø) {
    E'den en az maliyetli (v,w) kenarını seç;
    E = E - {(v,w)};
    if ((v,w) T içinde döngü oluşturmuyorsa)
        T = T ∪ {(v,w)};
    else
        (v,w)'yi bırak;
}
if (|T| < n-1)
    printf("minimum kapsayan ağaç yok\n");

Kodda T seçilen kenarların, E henüz denenmemiş kenarların kümesidir; |T| seçilen kenar sayısını gösterir.

• Satır 1. Başta hiçbir kenar seçilmemiştir. Her düğüm, tek düğümlü kendi öbeğidir.
• Satır 2. Döngü iki koşuldan biri bozulunca durur. n − 1 kenar seçildiyse ağaç tamamlanmıştır; daha fazla kenara bakmaya gerek yoktur. Seçilecek kenar kalmadıysa da durulur.
• Satır 3–4. Kalan kenarlardan en ucuzu alınır ve kümeden çıkarılır. Bir kenar en çok bir kez denenir.
• Satır 5–8. Kenar, o ana kadar seçilmiş kenarlarla bir döngü kurmuyorsa ağaca eklenir; kuruyorsa bırakılır. Bırakılan kenar bir daha ele alınmaz. Seçilenlerle döngü kuran bir kenar, sonra ne seçilirse seçilsin yine döngü kurar.
• Satır 10–11. Döngü bittiğinde n − 1'den az kenar seçilmişse kenarlar tükenmiş ama ağaç tamamlanamamıştır. Bu, çizgenin bağlantılı olmadığını gösterir ve minimum kapsayan ağaç yoktur.

Kruskal'ın ara durumları ağaç değil ormandır. Seçilen kenarlar birbirinden ayrık birkaç öbek (bağlantılı bileşen) oluşturabilir. Öbekler birleşe birleşe büyür ve en sonda tek öbek kalır. Bir kenarın döngü kurması, iki ucunun zaten aynı öbekte olması demektir.

17.3.2Kruskal adım adım

Yedi köy çizgesinin dokuz kenarı maliyete göre sıralanınca şu dizi çıkar: (0,5) 10, (2,3) 12, (1,6) 14, (1,2) 16, (3,6) 18, (3,4) 22, (4,6) 24, (4,5) 25, (0,1) 28. Tablo 17.2 her kenarın kararını, Şekil 17.7 de seçilmiş dört anı gösterir.

Tablonun üç satırı dikkat ister. Dördüncü adımda (1,2) iki ayrı öbeği, {1,6} ile {2,3}'ü birleştirir. Bu adımdan önce öbek sayısı (tek düğümlüler dahil) 4'tü, sonra 3'e düşer. Beşinci adımda (3,6)'nın iki ucu da aynı öbektedir. 3'ten 6'ya ağaç üzerinde 3-2-1-6 yolu zaten vardır; (3,6) bu yolu kapatıp döngü kurar. Yedinci adımda (4,6) için de aynı durum geçerlidir: 4-3-2-1-6 yolu hazırdır. Sekizinci adımda altıncı kenar seçilir ve algoritma durur. En pahalı kenar (0,1)'e hiç bakılmaz.

Bulunan ağaç {(0,5), (2,3), (1,6), (1,2), (3,4), (4,5)} ve maliyeti 10 + 12 + 14 + 16 + 22 + 25 = 99'dur. Bu, 46 kapsayan ağacın en ucuzudur.

17.3.3Kruskal nasıl kodlanmaz?

Sözde kodun iki satırı belirsiz kalır: “en az maliyetli kenarı seç” ve “döngü oluşturmuyorsa”. Bu iki işin nasıl yapılacağı kodun hızını belirler. Hoca derste önce bilerek yanlış bir yoldan gider ve sonra doğrusunu gösterir. Yanlış yolu görmek doğrusunu anlamayı kolaylaştırır.

Tablodaki öbek sayılarına bakan biri bir gözlem yapar: öbekler önce ikiye, sonra üçe çıktı, sonra yeniden ikiye düştü. “Yakaladım!” der, “seçtiğim kenarların öbeklerini birer listede tutarım.” Seçilmemiş kenarlar da bir dizidedir. Her seferinde dizide en ucuz kenarı aramak, onu silmek ve kalanları kaydırmak kötü bir fikirdir. Kenarları bir kez maliyete göre sıralayıp (uç1, uç2, maliyet) üçlüleri hâlinde tutmak daha iyidir.

Bu planla izleme şöyle gider. (0,5) gelir: listelerde aranır; ne 0 vardır ne 5, yeni bir liste açılır. (2,3) ve (1,6) için de yeni listeler açılır. (1,2) gelince 1 bir listede, 2 başka bir listede bulunur. Farklı listelerde oldukları için döngü yoktur; kenar alınır ve iki liste birleştirilir. (3,6) gelince ikisi de aynı listededir: döngü!

Bu kod doğru çalışır. Ama her kenar için iki ucu bütün listelerde aranır ve bu arama O(n) sürer. Toplam maliyet O(e · n) olur. Hoca bu noktada açık konuşur: döngü yakalanmıştır, sonuç da doğrudur, ama böyle kodlanmaz ve sınavda böyle yazan kod puan almaz. Algoritmanın kendisi değil, arkasındaki veri yapısı yanlıştır. Hoca ayrıca Kruskal'ın kodlanmasını ödev olarak verebileceğini ve öğrencilerin gereken veri yapılarını kendi başlarına keşfedip edemeyeceğini merak ettiğini söyler.

17.3.4İki soru, iki veri yapısı

Kruskal'ın her adımında iki soru sorulur ve her birinin karşılığı olan bir veri yapısı vardır.

1) En az maliyetli kenar hangisi? Bu soru, en küçük öğeyi tekrar tekrar isteyen bir yapıya işaret eder: min-heap ile gerçeklenen öncelikli kuyruk (priority queue). Min-heap'te her düğüm çocuklarından küçük ya da onlara eşittir; en küçük öğe köktedir. Kökü almak (deleteMin) O(log e) sürer. Heap iki yolla kurulur. Kenarlar tek tek eklenirse O(e log e) gerekir. Kenar dizisi hazırsa aşağıdan yukarıya heap oluşturma (bottom-up heap construction) ile O(e) yeter. Bu yöntemde son iç düğümden köke doğru her düğüm aşağı süzülür ve dizi heap'e dönüşür. Üçüncü yol kenarları bir kez sıralamaktır; C'de bunun için standart kütüphanenin qsort fonksiyonu kullanılır.

2) Bu kenar döngü kurar mı? Kenarın iki ucu farklı öbeklerdeyse döngü kurmaz. Öbekler birbirinden ayrık kümelerdir (disjoint sets): her düğüm tam bir kümededir. Ayrık kümeler üzerinde iki işlem gerekir. Küme bulma (find) bir düğümün hangi kümede olduğunu kümenin kökünü döndürerek söyler. Birleşim (union) iki kümeyi tek kümede toplar. Bu ikiliye kısaca union-find denir. Döngü sorusu böylece bir karşılaştırmaya iner: kume_bul(3) ile kume_bul(2) aynı kökü mü veriyor?

Hoca bu noktada şaşkınlığı paylaşır: arka planda heap ve kümeler çoktan anlatılmış, ama öğrenci bunların Kruskal'da işe yarayacağını fark etmeden gidip liste tutmaya kalkmıştır. İlkokulda öğretilen kümeler burada bir çizge algoritmasını hızlandırır.

Sunum maliyeti ayrıntılı bir formülle verir. Heap kenarlar tek tek eklenerek kurulursa yaklaşık |E| · lg |E| iş gerekir. Ardından |V| kez en küçük kenar alınır; her alma lg |E|, her küme denetimi neredeyse sabit sürer. Toplam |E| · lg |E| + |V| · (lg |E| + Θ(1)) olur. Heap aşağıdan yukarıya kurulursa ilk terim 2|E|'ye iner. Buradaki “neredeyse sabit” süre, union-find'ın ters Ackermann fonksiyonu α ile sınırlanan maliyetidir. Formül bir noktada iyimserdir: döngü kuran kenarlar da heap'ten alınır. En kötü durumda n − 1 değil e kez en küçük alınabilir. Güvenli üst sınır O(e log e)'dir.

17.3.5Union-find ve karşılaştırma fonksiyonu

Kruskal'ın C gerçeklemesi üç küçük parçaya dayanır: bir kenar yapısı, union-find işlemleri ve qsort için bir karşılaştırma fonksiyonu.

typedef struct { int u, v, w; } kenar;

int kume_bul(int ata[], int i)   /* kok: ata < 0 */
{
    while (ata[i] >= 0) i = ata[i];
    return i;
}
void birlestir(int ata[], int a, int b)   /* a, b kok */
{
    if (ata[a] <= ata[b]) {   /* a daha buyuk kume */
        ata[a] += ata[b];  ata[b] = a;
    } else {
        ata[b] += ata[a];  ata[a] = b;
    }
}
int kars(const void *x, const void *y)
{
    return ((const kenar *)x)->w - ((const kenar *)y)->w;
}

• Satır 1. Her kenar üç tamsayıdır: uçlar u, v ve ağırlık w. typedef sayesinde tip adı struct yazmadan kenar olarak kullanılır. x86-64 üzerinde sizeof(kenar) 12 bayttır; dolgu yoktur, çünkü üç alan da 4 baytlık int'tir.
• Satır 3–7. kume_bul, bir düğümün kümesinin kökünü bulur. Kümeler bir dizide ağaç olarak tutulur: ata[i], i'nin ağaçtaki ebeveynidir. Kökün ebeveyni yoktur; kökte ata negatif bir sayıdır. Döngü, negatif bir değere varana kadar ebeveynlere tırmanır. Döndürülen kök, kümenin adıdır.
• Satır 8–15. birlestir, iki kökü alıp kümelerini birleştirir. Parametreler kök olmak zorundadır; kök olmayan düğümle çağrılırsa ağaç bozulur. Kökte saklanan negatif sayının mutlak değeri küme boyutudur: ata[a] = −4, a'nın kümesinde 4 öğe olduğunu söyler. ata[a] <= ata[b] koşulu, a'nın kümesinin daha büyük ya da eşit olduğu anlamına gelir (−4 < −2). Büyük küme kök olarak kalır: boyutlar toplanır (ata[a] += ata[b]) ve küçük kümenin kökü büyüğün altına bağlanır (ata[b] = a). else kolu aynı işi ters yönde yapar.
• Satır 16–19. kars, qsort'un istediği imzadadır: iki const void * alır, birincisi küçükse negatif, büyükse pozitif, eşitse sıfır döndürür. void * işaretçiler const kenar * tipine dönüştürülür ve ağırlıklar çıkarılır.

Kümelerin bellekteki görünümü tek bir tamsayı dizisidir. Başta her düğüm kendi kümesinin köküdür ve boyutu 1'dir; dizi {−1, −1, −1, −1, −1, −1, −1} olur. Yedi köy örneğinde ilk dört kenar eklenince dizi {−2, −4, 1, 2, −1, 0, 1} hâline gelir. Bu dizi üç ağaç tanımlar. 0 köktür (boyut 2) ve 5'in ebeveynidir. 1 köktür (boyut 4); 2 ve 6 doğrudan 1'e, 3 ise 2'ye bağlıdır. 4 tek başınadır. kume_bul(ata, 3) çağrısı 3 → 2 → 1 yolunu izler ve 1'i döndürür.

Kural olmasaydı en kötü durumda ağaçlar zincire dönerdi. birlestir(0, 1), birlestir(0, 2), … biçiminde her seferinde büyük küme küçüğün altına bağlansa kume_bul O(n) adım sürerdi.

Bir iyileştirme daha mümkündür: yol kısaltma (path compression). Horowitz, Sahni ve Anderson-Freed'in kitabında aynı fikir azaltma kuralı (collapsing rule) adıyla geçer. kume_bul kökü bulduktan sonra, tırmandığı yol üzerindeki her düğümü doğrudan köke bağlar. Sonraki aramalar aynı yolu bir adımda geçer:

int kume_bul(int ata[], int i)       /* yol kisaltmali */
{
    int kok = i, sonraki;
    while (ata[kok] >= 0) kok = ata[kok];     /* 1. tur: koku bul */
    while (i != kok) {                        /* 2. tur: yoldakileri koke bagla */
        sonraki = ata[i];
        ata[i] = kok;
        i = sonraki;
    }
    return kok;
}

Birinci döngü kökü bulur, ikinci döngü yolu bir kez daha yürür. Her düğümün eski ebeveyni sonraki'de saklanır, sonra düğüm köke bağlanır. Saklama yapılmazsa yolun devamı kaybolur. Ağırlıklı kural ile yol kısaltma birlikte kullanılınca bir dizi işlemde işlem başına amortize maliyet O(α(n)) olur. α, ters Ackermann fonksiyonudur ve evrendeki atom sayısı kadar büyük n'ler için bile 4'ü aşmaz; pratikte sabittir. Rastgele 2000 düğümlü bir çizgede (8000 kenar) Kruskal'ın kume_bul çağrılarının tırmandığı bağ sayısı yol kısaltma olmadan 21 464, yol kısaltmayla 12 348 olarak ölçüldü.

kars fonksiyonundaki çıkarma da bir tuzak taşır. İki büyük ağırlığın farkı int sınırını aşabilir; örneğin 2 000 000 000 − (−2 000 000 000) taşar ve işaret yanlış çıkar. Burada ağırlıklar küçük, negatif olmayan tamsayılardır ve taşma olmaz. Genel amaçlı bir karşılaştırmada (a > b) − (a < b) biçimi güvenlidir.

17.3.6kruskal() ana döngüsü ve izlemesi

Parçalar hazır olunca ana döngü on bir satıra sığar. Kodda k, e öğeli kenar dizisi; T, seçilen kenarların yazılacağı n − 1 öğeli dizi; ata, n öğeli küme dizisidir. i ve t tamsayıdır.

for (i = 0; i < n; i++) ata[i] = -1;
qsort(k, e, sizeof(kenar), kars);
for (i = 0, t = 0; i < e && t < n - 1; i++) {
    int a = kume_bul(ata, k[i].u);
    int b = kume_bul(ata, k[i].v);
    if (a != b) {                 /* dongu yok */
        T[t++] = k[i];
        birlestir(ata, a, b);
    }                             /* yoksa birak */
}
if (t < n - 1) printf("agac yok\n");

• Satır 1. Her düğüm kendi kümesinin kökü yapılır; boyutu 1 olduğu için ata değeri −1'dir. Maliyet O(n).
• Satır 2. Kenarlar maliyete göre artan sırada dizilir. qsort'a dizinin başı, öğe sayısı, bir öğenin bayt boyutu ve karşılaştırma fonksiyonu verilir. qsort öğelerin tipini bilmez; sizeof(kenar) ile her öğenin kaç bayt olduğunu öğrenir ve öğeleri bayt bayt yer değiştirir. Maliyet O(e log e)'dir.
• Satır 3. Dizinin başından itibaren kenarlar denenir. İki sayaç birlikte başlatılır: i denenen kenarın indisi, t seçilen kenar sayısıdır. Döngü kenarlar bitince ya da n − 1 kenar seçilince durur. İkinci koşul unutulursa algoritma yine doğru sonuç verir, ama ağaç tamamlandıktan sonra kalan bütün kenarlar boşuna denenir.
• Satır 4–5. Kenarın iki ucunun kökleri bulunur. a ve b döngü gövdesinde bildirilmiştir; C99'dan beri blok içinde değişken bildirmek serbesttir.
• Satır 6–9. Kökler farklıysa uçlar ayrı kümelerdedir ve kenar döngü kurmaz. Kenar T'ye kopyalanır (yapı ataması üç alanı birden kopyalar), t bir artar ve iki küme birleştirilir. Kökler aynıysa hiçbir şey yapılmaz; kenar bırakılır.
• Satır 11. Döngü t < n − 1 iken bittiyse kenarlar tükenmiştir; çizge bağlantılı değildir.

Kod, sunumdaki biçimiyle derlenip bir test sürücüsüyle çalıştırıldı. Tablo 17.3 programın kendi çıktısıdır: her kenar için bulunan kökler ve birleşimden sonraki ata dizisi.

İzlemedeki birkaç ayrıntı ağırlıklı kuralın işleyişini gösterir. i = 0'da iki küme de 1 öğelidir; ata[0] <= ata[5] eşitlikle doğru olduğundan 0 kök kalır. i = 3'te {1,6} ile {2,3} yine eşit boyludur; 1 kök kalır, 2 onun altına girer, boyut −4 olur. Bu andan sonra 3'ün kökünü bulmak iki adım sürer: 3 → 2 → 1. i = 7'de 1'in kümesi beş, 0'ınki iki öğelidir; küçük küme (0) büyüğün (1) altına bağlanır ve ata[0] 1 olur. Son dizide en derin düğümler 3 ve 5'tir; ikisi de kökten iki bağ uzaktadır. Yedi öğeli bir küme için Teorem 17.4'ün verdiği sınır ⌊lg 7⌋ + 1 = 3 düzeydir; ağaç bu sınırın içindedir.

Aynı sürücü üç durumu daha denedi. Ağırlıkları farklı bir sınav çizgesinde maliyet 16 çıktı. Kopuk bir çizgede (iki bileşen, beş düğüm) yalnız üç kenar seçildi ve program “agac yok” yazdı. Bütün denemelerde malloc ve free çağrılarını sayan bir sarmalayıcı 12 ayırma ve 12 serbest bırakma saydı; sızıntı yoktur.

17.3.7Kruskal'ın karmaşıklığı

Kruskal'ın maliyeti, kodun her satırının kaç kez çalıştığından ve her çalışmanın ne sürdüğünden toplanır. Tablo 17.4 bu toplamı satır gruplarına göre verir.

Toplamda baskın terim sıralamadır. kume_bul çağrıları en çok 2e · O(log n) tutar ve bu da O(e log n)'dir. Son satırdaki eşitlik basit bir gözleme dayanır. Basit bir çizgede e ≤ n(n − 1)/2 < n²'dir. Logaritma alınınca log e < 2 log n çıkar; sabit çarpan O gösteriminde düşer ve O(e log e) = O(e log n) olur. Bağlantılı çizgede e ≥ n − 1 olduğundan ters yönde de log n = O(log e) geçerlidir. Bellek maliyeti kenar dizisi, T ve ata için O(n + e)'dir.

En iyi durumda ilk n − 1 kenarın hiçbiri döngü kurmaz ve döngü n − 1 turda biter. Ama sıralama yine bütün kenarları işler ve karşılaştırmaya dayalı bir sıralama genel olarak O(e log e) sürer; ağacın erken tamamlanması bu maliyeti azaltmaz. Heap kullanılırsa tablo değişir. Heap O(e)'de kurulur, sonra yalnız gereken kadar en küçük alınır. Ağaç erken tamamlanırsa toplam O(e + k log e) olur; k denenen kenar sayısıdır. Ödevde heap'in istenmesinin nedeni budur. Rastgele ağırlıklı yoğun bir çizgede (2000 düğüm, yaklaşık iki milyon kenar) ağaç yalnız 9685 kenar denendikten sonra tamamlandı; qsort ise iki milyon kenarın hepsini sıraladı.

Liste tutan “kötü” kodlama ile karşılaştırma notun ana fikrini özetler. Kötü kodlamada her kenar için uçlar bütün listelerde aranır: kenar başına O(n), toplam O(e · n). Yedi köy için fark önemsizdir. 5000 düğümlü ve altı milyon kenarlı bir çizgede ise e · n otuz milyarı aşar, e log e ise yaklaşık yüz kırk milyondur. Algoritma aynıdır; değişen yalnız arkasındaki veri yapısıdır.

17.4Prim algoritması

17.4.1Algoritma

Prim algoritmasının tarihi ilginçtir. Çek matematikçi Vojtěch Jarník algoritmayı 1930'da yayımladı. Robert C. Prim 1957'de, Edsger W. Dijkstra 1959'da aynı algoritmayı birbirinden habersiz yeniden buldu. Bu yüzden kaynaklarda DJP algoritması ya da Prim-Jarník algoritması adıyla da geçer.

Kruskal'da seçilen kenarlar birbirinden ayrık öbekler oluşturabiliyordu. Prim ise tek bir ağacı büyütür. Bir başlangıç düğümüyle başlar ve her adımda ağaçtaki bir düğümü ağaç dışındaki bir düğüme bağlayan en ucuz kenarı ekler. Sözde kodu şöyledir:

T  = {};
TV = {0};           /* ağaç düğümleri: 0'dan başla */
while (|T| < n-1) {
    u ∈ TV ve v ∉ TV olan en ucuz (u,v) kenarını seç;
    if (böyle kenar yok) break;
    TV = TV ∪ {v};
    T  = T  ∪ {(u,v)};
}
if (|T| < n-1)
    printf("minimum kapsayan ağaç yok\n");

• Satır 1–2. T seçilen kenarların, TV ağaca katılmış düğümlerin kümesidir. Başlangıç düğümü 0'dır; herhangi bir düğüm seçilebilir.
• Satır 3–4. Her turda bir ucu TV'de, öteki ucu TV dışında olan en ucuz kenar aranır. Seçilebilecek kenarlar yalnız bunlardır.
• Satır 5. Böyle bir kenar yoksa ağaç geri kalan düğümlere ulaşamaz; çizge bağlantılı değildir.
• Satır 6–7. Kenarın dıştaki ucu TV'ye, kenarın kendisi T'ye eklenir.
• Satır 9–10. Döngü erken bittiyse minimum kapsayan ağaç yoktur.

Prim'de döngü denetimi gerekmez. Seçilen kenarın bir ucu ağaçta, öteki ucu ağaç dışındadır; v ∉ TV koşulu kenarın yeni bir düğüme gittiğini zaten garanti eder. Yeni düğüme giden bir kenar döngü kuramaz. Seçilen kenar, S = TV kesitini geçen en ucuz kenardır; kesit özelliği her seçimin doğru olduğunu söyler.

17.4.2Prim adım adım

Yedi köy çizgesinde Prim 0'dan başlatılsın. Tablo 17.5 her turda TV'yi, seçilebilecek kenarları ve seçimi verir.

Tablonun “seçilebilecek” sütunu her turda değişir. Bir düğüm ağaca girince ona değen kenarlar adaylara katılır. Bir kenarın iki ucu da ağaca girince o kenar adaylıktan düşer. Örneğin (0,1), beş tur boyunca adaydır ama hep daha ucuz bir aday bulunur. Altıncı turun başında 1 de ağaçtadır; (0,1)'in iki ucu TV'dedir ve artık aday değildir. Sunum bu noktaya ayrıca dikkat çeker: (0,1) çizimde hâlâ “seçilebilecek” gibi görünür, ama seçilirse döngü kurar.

Prim'in bulduğu ağaç {(0,5), (5,4), (4,3), (3,2), (2,1), (1,6)}'dır ve Kruskal'ınkiyle aynıdır; yalnız kenarların seçilme sırası farklıdır. Bu bir rastlantı değildir. Yedi köy çizgesinde bütün ağırlıklar farklıdır ve minimum kapsayan ağaç tektir. Başlangıç düğümü değiştirilse de sonuç değişmez: 3'ten başlayan Prim kenarları (3,2), (2,1), (1,6), (3,4), (4,5), (5,0) sırasıyla seçer ve yine 99'a varır.

17.4.3Prim'i kodlamanın asıl zorluğu

Sözde kodun dördüncü satırı tek cümledir ama kodlaması kolay değildir: “bir ucu ağaçta, öteki ucu dışarıda olan en ucuz kenarı seç”. Bu satır her turda çalışır ve şu gereksinimleri taşır:

• En az maliyetli aday kenar tek hamlede alınabilmelidir.
• Bir kenar seçilince adaylara yeni kenarlar eklenir ve iki ucu da ağaca düşen kenarlar çıkar. Aday kümesi her turda değişir.
• 0 seçildiğinde yalnız (0,1) ve (0,5)'i gören bir yapı gerekir; çizgenin geri kalan kenarlarına bakmamalıdır bile.

Saf bir kodlama her turda bütün kenarları tarar ve ucu ağaçta olanlar arasında en ucuzunu arar. Bu, tur başına O(e), toplam O(n · e) eder. Kruskal'daki liste hatasının Prim'deki karşılığıdır.

Hoca iki gözlemle konunun önemini vurgular. Birincisi: bu satırın verimli bir çözümünü bulabilen öğrenci, veri yapıları konusunda belli bir düzeye gelmiş demektir. “Prim zaten yazmış, ben de kodlarım” diyerek sözde kodu doğrudan koda çeviren ise karmaşıklığın birden büyüdüğünü görür. İkincisi: “algoritma” kelimesini hiç duymamış bir çizge kuramcısına bu problem verilse o da Prim'in yaptığını yapar; en ucuz kenarı seçer. Bilgisayar mühendisinin farkı, bu seçimin arkasında hangi veri yapısının durması gerektiğini keşfetmesidir.

Çözüm şu gözleme dayanır: aday kenarların hepsini tutmak gerekmez. Ağaç dışındaki her v düğümü için yalnız bir sayı yeter: v'yi ağaca bağlayan en ucuz kenarın maliyeti. Bu sayı enaz[v] dizisinde, o kenarın ağaçtaki ucu da yakin[v] dizisinde tutulur. En ucuz aday kenar, enaz değeri en küçük olan ağaç dışı düğümün kenarıdır. Bir u düğümü ağaca girince yalnız u'nun komşularının enaz değerleri değişebilir. Bu fikir dizilerle O(n²), bir min-heap ile O(e log n) süreli iki gerçekleme verir.

17.4.4Dizilerle O(n²) gerçekleme

Çizge bir maliyet matrisiyle tutulur: w[u][v], (u, v) kenarının ağırlığıdır. Kenar yoksa w[u][v] büyük bir SONSUZ sabitidir; köşegen 0'dır. secildi[v], v'nin ağaçta olup olmadığını söyler (v ∈ TV). Prim'in sunumdaki C kodu şudur:

secildi[0] = 1;                    /* TV = {0} */
for (v = 0; v < n; v++)
    enaz[v] = w[0][v], yakin[v] = 0;
for (k = 1; k < n; k++) {
    u = en_yakin(enaz, secildi, n);  /* O(n) */
    if (u < 0) break;                /* agac yok */
    secildi[u] = 1;  toplam += enaz[u];
    for (v = 0; v < n; v++)
        if (!secildi[v] && w[u][v] < enaz[v])
            enaz[v] = w[u][v], yakin[v] = u;
}

• Satır 1. 0 ağaca alınır. Öteki secildi öğelerinin ve toplam'ın önceden 0 yapılmış olması gerekir; kod parçası bunu varsayar.
• Satır 2–3. Başta ağaçta yalnız 0 vardır. Bu yüzden her v'nin ağaca en ucuz bağlantısı doğrudan (0, v) kenarıdır: enaz[v] = w[0][v], yakin[v] = 0. Kenarı olmayan düğümlerde enaz SONSUZ kalır. Virgül işleci iki atamayı tek deyimde yapar.
• Satır 4. Ağaca n − 1 düğüm daha eklenecektir; döngü n − 1 tur döner.
• Satır 5–6. en_yakin, ağaç dışındaki düğümler arasında enaz değeri en küçük olanı döndürür. Bütün enaz değerleri SONSUZ ise ağaca bağlanabilecek düğüm kalmamıştır; fonksiyon −1 döndürür ve döngü kırılır.
• Satır 7. u ağaca alınır, kenarı (yakin[u], u)'dur ve maliyeti toplama eklenir.
• Satır 8–10. Ağaca yeni giren u, dışarıdaki düğümlere daha ucuz bir bağlantı sunabilir. Her ağaç dışı v için w[u][v], kayıtlı enaz[v]'den küçükse kayıt güncellenir: artık v'nin en ucuz bağlantısı u üzerindendir.

en_yakin fonksiyonu sunumda verilmez. Gerçeklemesi basit bir doğrusal aramadır:

int en_yakin(const int enaz[], const int secildi[], int n)
{
    int v, u = -1;
    for (v = 0; v < n; v++)
        if (!secildi[v] && enaz[v] < SONSUZ &&
            (u < 0 || enaz[v] < enaz[u]))
            u = v;
    return u;            /* -1: TV'ye bagli dugum kalmadi */
}

Arama yalnız ağaç dışındaki ve ağaca bağlanabilen (enaz değeri SONSUZ olmayan) düğümlere bakar. u < 0 koşulu ilk uygun düğümü aday yapar; sonraki her düğüm daha küçük bir enaz değeriyle adayın yerini alır.

Son durumdaki iki dizi, ağacın kendisidir. Her v ≠ 0 için (yakin[v], v) bir ağaç kenarı, enaz[v] onun maliyetidir: (2,1) 16, (3,2) 12, (4,3) 22, (5,4) 25, (0,5) 10, (1,6) 14. enaz'ın ilk öğesi dışındakilerin toplamı 99'dur. 6'nın kaydı üç kez değişmiştir: önce 24 (4 üzerinden), sonra 18 (3 üzerinden), en son 14 (1 üzerinden). Her güncelleme, ağaca yeni giren bir düğümün 6'ya daha ucuz bir yol açmasıdır.

Maliyet. Dış döngü n − 1 tur döner. Her turda en_yakin n düğüme bakar, güncelleme döngüsü de n sütunu tarar. Tur başına O(n), toplam O(n²) eder. Bu süre kenar sayısından bağımsızdır; en iyi ve en kötü durum aynıdır: Θ(n²). Bellek matris için O(n²), diziler için O(n)'dir. Yoğun bir çizgede, yani e ≈ n² iken, kenarların hepsine en az bir kez bakmak zaten Ω(n²) gerektirir. Dolayısıyla bu sürüm yoğun çizgeler için idealdir.

Kod sunumdaki biçimiyle derlenip çalıştırıldı; Tablo 17.6'daki değerler programın çıktısıdır. Kopuk bir çizgede en_yakin üçüncü turda −1 döndürdü, döngü kırıldı ve yalnız iki kenar seçildi.

17.4.5Heap ile hızlandırmak

Dizili sürüm her turda n düğümü tarar. Seyrek bir çizgede, örneğin e ≈ 4n iken, bu taramaların çoğu boşa gider: ağaç dışındaki düğümlerin çoğunun enaz değeri hâlâ sonsuzdur. İki iyileştirme birlikte yapılır. Çizge komşuluk listesiyle tutulur; böylece bir düğüm ağaca girince yalnız gerçek komşulara bakılır. En küçük enaz değeri de doğrusal aramayla değil, bir min-heap'ten alınır. Sunumdaki kod şöyledir:

/* komsuluk listesi + min-heap (anahtar = enaz) */
heap_ekle(H, 0, 0);
while (!heap_bos(H)) {
    u = heap_min_al(H);          /* O(log n) */
    if (secildi[u]) continue;    /* bayat kayit */
    secildi[u] = 1;
    for (p = baslik[u]; p; p = p->bag)
        if (!secildi[p->dugum] &&
            p->agirlik < enaz[p->dugum]) {
            enaz[p->dugum] = p->agirlik;
            yakin[p->dugum] = u;
            heap_ekle(H, p->dugum, p->agirlik);
        }
}

Komşuluk listesinde her düğümün bir listesi vardır; baslik[u], u'nun listesinin ilk öğesini gösterir. Her öğe üç alanlıdır: komşunun numarası dugum, kenarın ağırlığı agirlik ve listedeki sonraki öğeyi gösteren bag. Heap'in her kaydı bir (düğüm, anahtar) çiftidir ve anahtar, kayıt eklendiği andaki enaz değeridir. Kod çalışmadan önce bütün enaz değerleri SONSUZ, enaz[0] 0 ve bütün secildi değerleri 0 yapılmış olmalıdır.

• Satır 2. Başlangıç düğümü 0, anahtar 0 ile heap'e konur.
• Satır 3–4. Heap boşalana kadar anahtarı en küçük kayıt alınır. heap_min_al kökü döndürür, son kaydı köke taşıyıp aşağı süzer: O(log m), m heap'teki kayıt sayısıdır.
• Satır 5. Alınan düğüm zaten ağaçtaysa kayıt bayattır ve atlanır. Bayat kayıt şöyle oluşur: bir düğümün enaz değeri küçülünce eski kayıt heap'ten silinmez, yeni anahtarla ikinci bir kayıt eklenir. Küçük anahtarlı kayıt önce çıkar ve düğüm ağaca girer. Eski kayıt daha sonra çıktığında düğüm işaretlidir.
• Satır 6. Düğüm ağaca alınır. Ağaca girdiği kenar (yakin[u], u), maliyeti enaz[u]'dur.
• Satır 7–13. u'nun listesindeki her komşu için dizili sürümdeki güncelleme yapılır. Komşu ağaç dışındaysa ve (u, komşu) kenarı kayıtlı bağlantıdan ucuzsa enaz ve yakin güncellenir ve yeni anahtarla bir heap kaydı eklenir. Liste yürüyüşü, bağlı listelerde alışılmış for (p = baslik[u]; p; p = p->bag) kalıbıdır; p, NULL olunca döngü biter.

Sunum heap işlemlerinin içini vermez. Dizi üzerinde kurulan ikili bir min-heap ile şöyle yazılabilir:

typedef struct { int dugum, anahtar; } kayit;
typedef struct {
    kayit *a;          /* a[1..boyut]: kok a[1] */
    int boyut, kapasite;
} heap;

int heap_bos(const heap *H) { return H->boyut == 0; }

void heap_ekle(heap *H, int dugum, int anahtar)
{
    int i = ++H->boyut;                     /* kapasite >= 2e + 1 */
    while (i > 1 && H->a[i / 2].anahtar > anahtar) {
        H->a[i] = H->a[i / 2];              /* ebeveyni asagi indir */
        i /= 2;
    }
    H->a[i].dugum = dugum;  H->a[i].anahtar = anahtar;
}

int heap_min_al(heap *H)
{
    int kok = H->a[1].dugum;
    kayit son = H->a[H->boyut--];
    int i = 1, c = 2;
    while (c <= H->boyut) {
        if (c < H->boyut && H->a[c + 1].anahtar < H->a[c].anahtar) c++;
        if (son.anahtar <= H->a[c].anahtar) break;
        H->a[i] = H->a[c];                  /* kucuk cocugu yukari al */
        i = c;  c *= 2;
    }
    H->a[i] = son;
    return kok;
}

Kayıtlar a[1..boyut] aralığındadır; a[i]'nin ebeveyni a[i/2], çocukları a[2i] ile a[2i+1]'dir. heap_ekle yeni kaydı dizinin sonuna koyar ve anahtarı ebeveyninkinden küçük olduğu sürece yukarı taşır; yer değiştirmek yerine ebeveyni aşağı indirip boşluğu yukarı kaydırır. heap_min_al kökü saklar, son kaydı geçici bir değişkene alır ve onu kökten aşağı doğru, küçük çocuktan büyük kalmayana kadar indirir. Heap dizisi malloc ile 2e + 2 kayıtlık ayrılır. Her komşuluk öğesi en çok bir ekleme yapabilir; listelerde toplam 2e öğe vardır ve başlangıç kaydıyla 2e + 1 kayıt sığmalıdır. a[0] kullanılmaz. Dizi iş bitince free ile bırakılır; komşuluk listesinin 2e öğesi de tek tek serbest bırakılmalıdır.

Düğümlerin ağaca giriş sırası dizili sürümle aynıdır: 0, 5, 4, 3, 2, 1, 6. Toplam 10 kayıt eklendi ve 10 kayıt alındı; üçü bayattı. 6 için üç kayıt oluştu (24, 18, 14), çünkü 6'nın enaz değeri üç kez küçüldü. Program bu sayıları ve 99 toplamını aynen verdi. Sayaçlı malloc/free sarmalayıcısı 19 ayırma (18 liste öğesi ve heap dizisi) ile 19 serbest bırakma saydı.

Maliyet. Her komşuluk öğesi en çok bir ekleme yapar; heap'e en çok 2e + 1 kayıt girer ve o kadar kayıt çıkar. Heap'te en çok 2e + 1 kayıt bulunduğundan her işlem O(log e) sürer, bu da O(log n)'dir. Komşuluk listelerinin yürünmesi toplam O(n + e) tutar. Toplam O((n + e) log n), bağlantılı çizgede O(e log n) olur. Bellek O(n + e)'dir.

Bayat kayıt bırakmak yerine heap'teki kaydın anahtarı yerinde küçültülebilir. Bu işleme anahtar azaltma (decrease-key) denir. Bunun için her düğümün heap dizisinin neresinde durduğu ayrı bir dizide tutulmalıdır. Heap en çok n kayıtlı kalır, ama asimptotik sınır değişmez. Fibonacci heap ise anahtar azaltmayı amortize O(1)'de yapar ve sınırı O(e + n log n)'ye indirir. Bu sınır kuramsal açıdan önemlidir; pratikte yapının sabitleri büyüktür ve ikili heap çoğu zaman daha hızlıdır.

Tablodaki sınırların pratikteki karşılığını görmek için üç gerçekleme rastgele ağırlıklı çizgelerde çalıştırıldı. Tablo 17.9 süreleri verir. Süreler makineye, derleyiciye ve rastgele çizgeye göre değişir; burada önemli olan oranlardır.

Seyrek çizgelerde Kruskal ile heap'li Prim birkaç milisaniyede biter; dizili Prim onlardan 8 ila 35 kat yavaştır. 2000'den 5000'e çıkınca dizili Prim'in süresi yaklaşık altı kat arttı; (5000/2000)² ≈ 6,3 beklentisine yakındır. Yoğun çizgelerde tablo tersine döner. Dizili Prim kenar sayısından etkilenmez ve en hızlılar arasındadır. Kruskal'ın süresinin neredeyse tamamı milyonlarca kenarı sıralamaya gider, oysa ağaç ilk on bin kenar içinde tamamlanır. Yoğun çizgede heap'li Prim ancak dizili sürüme yetişir. Bir heap işlemi, matristeki bir hücreye bakmaktan çok daha pahalıdır; yoğun çizgede ise kenar sayısı hücre sayısına yakındır.

17.5Öteki algoritmalar ve karşılaştırmalar

17.5.1Sollin (Borůvka) ve ters silme

Çek mühendis Otakar Borůvka 1926'da Moravya'nın elektrik şebekesini tasarlarken minimum kapsayan ağaç problemini çözdü. Bu, problemin bilinen ilk algoritmasıdır; Sollin aynı yöntemi 1960'larda yeniden önerdiği için iki adla da anılır. Algoritma turlar hâlinde çalışır. Başta her düğüm ayrı bir bileşendir. Her turda her bileşen kendisinden dışarı çıkan en ucuz kenarı seçer; seçilen kenarların hepsi aynı anda eklenir ve bileşenler birleşir.

Birinci turda 0 ile 5'in en ucuz kenarı ortaktır: (0,5) = 10. 1 ile 6 için (1,6) = 14, 2 ile 3 için (2,3) = 12'dir. 4'ün kenarları 22, 24 ve 25'tir; en ucuzu (3,4)'tür. Aynı kenarı iki bileşen seçerse kenar bir kez eklenir. Tur sonunda {0,5}, {1,6} ve {2,3,4} kalır. İkinci turda {0,5}'ten çıkan kenarlar (0,1) 28 ve (4,5) 25'tir; en ucuzu (4,5). {1,6}'nın en ucuzu (1,2) 16'dır. {2,3,4}'ün en ucuzu da (1,2)'dir. Seçilen iki kenar eklenince tek bileşen kalır.

Her turda her bileşen başka bir bileşenle birleşir; bileşen sayısı en az yarıya iner. n bileşenden bire en çok lg n turda varılır. Her tur bütün kenarlara bir kez bakar: O(e). Toplam O(e log n)'dir. Bir turdaki seçimler birbirinden bağımsız olduğu için iş birçok işlemciye bölünebilir; algoritma paralelleştirmeye uygundur. Ağırlıklarda eşitlik varsa aynı ağırlıklı kenarlar arasında tutarlı bir seçim kuralı (ör. küçük numaralı uç) gerekir; yoksa bir turda döngü kurulabilir.

Ters silme (reverse-delete) Kruskal'ın tersidir. Bütün kenarlarla başlar ve kenarları azalan maliyetle dener. Bir kenarı silmek çizgeyi koparmıyorsa kenar silinir; koparıyorsa tutulur. Yedi köy çizgesinde (0,1) 28 silinir; (4,5) 25 tutulur, çünkü silinirse {0,5} kopar. (4,6) 24 ve (3,6) 18 silinir; geri kalanların her biri bir köprüdür ve tutulur. Kalan altı kenar yine 99'luk ağaçtır. Yöntem döngü özelliğine dayanır: silinen her kenar, bir döngünün en ağır kenarıdır.

Dört algoritma da aynı kesit ve döngü özelliklerine dayanır. Ağırlıklar farklıysa minimum kapsayan ağaç tek olduğundan hepsi aynı ağacı bulur.

17.5.2Minimum kapsayan ağaç ile en kısa yol ağacı

Minimum kapsayan ağaç, sık karıştırılan bir başka yapıya benzer: en kısa yol (shortest path) ağacı. Bir kaynak düğümden her düğüme giden en kısa yollar birleştirilince bir ağaç çıkar. İkisi de kapsayan ağaçtır ama farklı şeyleri küçültür.

• Minimum kapsayan ağaç toplam kenar maliyetini en aza indirir. Kökü yoktur; hangi düğümden bakıldığı önemsizdir. Ağaç üzerinde 0'dan 1'e gitmek 0-5-4-3-2-1 yolunu izler ve 10 + 25 + 22 + 12 + 16 = 85 tutar. Oysa doğrudan (0,1) kenarı 28'dir.
• En kısa yol ağacı her düğümün kaynağa uzaklığını tek tek en aza indirir. 0'dan başlayınca 1'e uzaklık 28, 2'ye 44, 3'e 56, 4'e 35, 5'e 10, 6'ya 42'dir. Ağacın kenarları (0,1), (0,5), (1,2), (1,6), (2,3), (5,4)'tür ve toplam maliyeti 105'tir; 99'dan büyüktür.

Hangi ağacın gerektiği soruya bağlıdır. Köylere kablo çekmenin toplam maliyeti soruluyorsa minimum kapsayan ağaç; merkezden her köye en çabuk ulaşım soruluyorsa en kısa yol ağacı aranır. En kısa yol ağacını bulan Dijkstra algoritması Prim'e çok benzer: o da tek bir ağacı büyütür ve her turda en küçük anahtarlı düğümü seçer. Tek fark anahtarın tanımıdır. Prim'de anahtar, düğümü ağaca bağlayan tek bir kenarın maliyetidir; Dijkstra'da kaynaktan o düğüme kadar olan yolun toplam uzunluğudur.

17.5.3Kruskal mı, Prim mi?

Seçimi çizgenin yoğunluğu ve elde hazır olan gösterim belirler. Kenarlar bir dosyadan liste hâlinde geliyorsa ve çizge seyrekse Kruskal en doğal seçimdir: liste olduğu gibi sıralanır. Çizge bir maliyet matrisiyle verilmişse ve yoğunsa dizili Prim hem kısa hem hızlıdır. Seyrek ve komşuluk listesiyle tutulan bir çizgede heap'li Prim ile Kruskal yakın sonuç verir. Son satırdaki fark da önemlidir. Kruskal kopuk bir çizgede durmaz; bütün kenarları dener ve her bileşenin minimum kapsayan ağacını, yani bir ormanı bulur. Prim ise başlangıç düğümünün bileşenini bitirince durur; öteki bileşenler için ayrıca başlatılması gerekir.

17.5.4Problem çözmede yaklaşım

Kruskal ve Prim'in öyküsü bir yöntemi de öğretir. Yeni bir problemle karşılaşan mühendis önce şu soruları sorar: Bu problem daha önce nasıl çözülmüş? Literatürde hangi veri yapıları önerilmiş? Dünya bunu nasıl çözüyor, ben nasıl çözeyim? Hoca, “algoritmaya çok iyi hâkimiz” rahatlığına da karşı çıkar. Bu algoritmalar üzerinde bugün de çalışılıyor. Bir problem çözülürken hangi yapının nerede kullanılacağını bilmek, veri yapıları dersinin asıl kazancıdır.

Sunum bu tutumu ustalık üzerine bir sözle anlatır. Söz, yolu izlemenin aşamalarını sıralar: ustaya bakmak, ustayı izlemek, ustayla yürümek, usta gibi görmek ve sonunda usta olmak. Yani önce literatürün çözümü öğrenilir ve uygulanır; özgün çözüm ondan sonra gelir. Kruskal'ı liste tutarak kodlayan öğrenci ilk aşamayı atlamıştır. Kümelerin ve heap'in bu probleme nasıl uyduğunu gören öğrenci ise sonraki aşamalara geçmiştir.

17.6Sınav tarzı soru

Kruskal'ın kodlanması ödev olarak verilir; aşağıdaki soru ise sınavlarda sorulabilecek türdendir. Şekil 17.13'teki altı düğümlü çizge için üç şey istenir:

1. Kruskal ile minimum kapsayan ağacı bulmak ve her kenar için “ekle” ya da “döngü” kararını yazmak.
2. Prim'i A'dan başlatıp seçilen kenarların sırasını yazmak.
3. Ağırlıklı birleşimle çalışan union-find'ın ata[] dizisinin son hâlini vermek.

Kruskal. Kenarlar sıralanır: (C,F) 1, (B,E) 2, (A,D) 3, (A,B) 4, (B,D) 5, (B,C) 6, (C,E) 7, (D,E) 8, (E,F) 9. Düğümler A..F, 0..5 diye numaralanır ve her kenar için birlestir(ata, kume_bul(ata, u), kume_bul(ata, v)) çağrılır. Tablo 17.11 kararları ve ata dizisini verir.

Beşinci kenar seçildiğinde n − 1 = 5 olur ve algoritma durur; (C,E), (D,E), (E,F)'ye bakılmaz. Ağaç {(C,F), (B,E), (A,D), (A,B), (B,C)}, maliyeti 1 + 2 + 3 + 4 + 6 = 16'dır. (B,D) döngü kurar, çünkü B ile D, A üzerinden zaten bağlıdır. Eşit boylu kümelerde ilk parametre kök kalır: (A,B)'de A ile B'nin ikisi de 2 öğelidir, A kök kalır. (B,C)'de A'nın kümesi 4, C'ninki 2 öğelidir; C, A'nın altına girer. Son dizi [−6, 0, 0, 0, 1, 2]'dir: A altı öğeli kümenin köküdür; E'nin ebeveyni B, F'nin ebeveyni C'dir.

Prim (A'dan). A'nın kenarları (A,B) 4 ve (A,D) 3'tür: (A,D) seçilir. TV = {A, D}; adaylar (A,B) 4, (D,B) 5, (D,E) 8: (A,B) seçilir. TV = {A, B, D}; adaylar (B,E) 2, (B,C) 6, (D,E) 8: (B,E) seçilir. TV = {A, B, D, E}; adaylar (B,C) 6, (E,C) 7, (E,F) 9: (B,C) seçilir. Son turda (C,F) 1 seçilir. Sıra (A,D) 3 → (A,B) 4 → (B,E) 2 → (B,C) 6 → (C,F) 1, toplam 16'dır. Ağaç Kruskal'ınkiyle aynıdır; ağırlıklar farklı olduğu için başka türlü olamaz. Dikkat çeken nokta, Prim'in en ucuz kenar (C,F)'yi en sona bırakmasıdır: C ağaca girene kadar bu kenar aday değildir.

Bütün değerler bir test sürücüsüyle doğrulandı. Çizgenin 55 kapsayan ağacı vardır ve maliyeti 16 olan tek ağaç budur.

17.7Ödev: Kruskal'ı veri yapısıyla kodlamak

Hoca bir sonraki hafta için herkesin Kruskal algoritmasını derste anlatıldığı biçimde kodlamasını ister. Beklenen program bir min-heap ve union-find kullanır. Girdisi bir kenar listesidir; çıktısı ağacın kenarları ve toplam maliyettir. Ödevin gereksinimleri şunlardır:

• Kenar yapısı kenar {u, v, w} biçimindedir. Heap, kenar dizisinden aşağıdan yukarıya kurulur (O(e)).
• kume_bul yol kısaltmalı, birlestir ağırlıklı kurallı olmalıdır.
• Çizge bağlantılı değilse (|T| < n − 1) program “minimum kapsayan ağaç yok” yazmalıdır.
• Yedi köy örneğinde 99'u bulduğunu ve (3,6) ile (4,6)'nın reddedildiğini gösteren bir çıktı üretmelidir.

Teslimden önce bakılacak bir denetim listesi de verilir. Heap'ten e kez değil, t = n − 1 olunca durulmalıdır. Her malloc çağrısından sonra NULL denetimi yapılmalı, program sonunda ayrılan her blok free ile bırakılmalıdır. Eşit ağırlıklı kenarlar varsa minimum kapsayan ağaç tek olmayabilir; farklı öğrencilerin programları farklı ağaçlar bulabilir, ama toplam maliyet hepsinde aynıdır.

Bu notta verilen parçalar ödevin bütün yapı taşlarını içerir: kenar yapısı ve birlestir, yol kısaltmalı kume_bul, aşağı süzme mantığı (heap'li Prim'deki heap_min_al) ve ana döngü. Ödevin asıl işi, bunları anahtar olarak kenar ağırlığını kullanan bir heap etrafında birleştirmektir.

17.8Karmaşıklık özeti

İlk satırdaki O(n) çarpanı, her seçimin döngü denetimidir. Yedi köy gibi küçük bir çizgede bile 84 seçim denenir; 30 düğüm ve 60 kenarlı bir çizgede C(60, 29) 10¹⁷'yi aşar. Son satırdaki DFS ve BFS ağırlıklara bakmadığı için herhangi bir kapsayan ağaç bulur. Bütün kenarların ağırlığı eşitse her kapsayan ağaç minimumdur ve doğrusal sürede bulunur.

17.9Sık yapılan hatalar

1. Kruskal'da döngüyü “iki uç da daha önce seçilmiş mi?” diye denetlemek. İki uç farklı öbeklerde olabilir. Yedi köy örneğinde (1,2) bu yanlış kurala takılır, oysa MST'nin kenarıdır. Doğru denetim kume_bul(u) != kume_bul(v)'dir.
2. Prim'de aday kümesinden iki ucu da TV'de olan kenarları çıkarmamak. (0,1) beş tur boyunca adaydır, altıncı turda iki ucu da ağaçtadır. Bu kenar seçilirse döngü kurulur. Dizili sürümde bu hata güncelleme döngüsündeki !secildi[v] koşulunun unutulmasıdır, heap'li sürümde bayat kayıtları atlamamaktır.
3. Minimum kapsayan ağaç ile en kısa yol ağacını karıştırmak. MST toplam maliyeti, en kısa yol ağacı tek tek uzaklıkları küçültür. Yedi köy örneğinde MST'de 0'dan 1'e uzaklık 85, en kısa yol ağacında 28'dir; toplamlar ise 99 ve 105'tir.
4. Bağlantılı olmayan çizgede |T| < n − 1 denetimini unutmak. Kruskal kenarlar bitince sessizce durur ve elinde bir orman kalır. Prim'de en_yakin'in −1 döndürmesi denetlenmezse secildi[-1] yazılır; bu, dizinin dışına yazmaktır.
5. Union-find'da kök olmayan düğümleri birleştirmek. birlestir iki kök bekler. Önce kume_bul çağrılır, sonra bulunan kökler birleştirilir.
6. Sonsuz için INT_MAX kullanıp toplamda taşma yaşamak. Karşılaştırma güvenli olsa da toplama taşar ve tanımsız davranışa yol açar. Olası en büyük toplamdan büyük, ama taşmayacak bir sabit seçilir.

17.10Alıştırmalar

1. Yedi köy örneğinde (3,6) kenarının maliyeti 18 yerine 11 olsaydı minimum kapsayan ağaç ve maliyeti ne olurdu?

   Çözüm

   Sıralı kenarlar: (0,5) 10, (3,6) 11, (2,3) 12, (1,6) 14, (1,2) 16, (3,4) 22, (4,6) 24, (4,5) 25, (0,1) 28. Kruskal: (0,5) ekle, (3,6) ekle, (2,3) ekle, (1,6) ekle, (1,2) döngü (1 ile 2, 6 ve 3 üzerinden bağlıdır), (3,4) ekle, (4,6) döngü, (4,5) ekle. Ağaç {(0,5), (3,6), (2,3), (1,6), (3,4), (4,5)}, maliyet 10 + 11 + 12 + 14 + 22 + 25 = 94. Ucuzlayan (3,6) ağaca girmiş, onunla aynı döngüdeki en pahalı kenar (1,2) çıkmıştır. Kod çıktısında son ata dizisi [3, 3, 3, −7, 3, 0, 3]'tür.

2. Kruskal ve Prim aynı çizgede hangi koşulda farklı ağaçlar verebilir?

   Çözüm

   Yalnız eşit ağırlıklı kenarlar varsa. Ağırlıklar farklıysa minimum kapsayan ağaç tektir ve her doğru algoritma onu bulur. Eşitlik varsa iki algoritma eşit kenarlar arasında farklı seçim yapabilir. Örneğin bütün kenarları 1 olan bir üçgende Kruskal sıralamadaki ilk iki kenarı alır. Prim ise başlangıç düğümünün iki kenarını alır ve bunlar farklı olabilir. Toplam maliyet yine aynıdır.

3. Sekiz düğümlü örnek çizgede (Şekil 17.1) 7'den başlayan DFS ve BFS kapsayan ağaçlarının kenarlarını yazın.

   Çözüm

   Komşuluk listeleri sıralıyken DFS(7): (7,3), (3,1), (1,0), (0,2), (2,5), (2,6), (1,4). 5'in komşuları 2 ve 7 işaretli olduğundan 2'ye, oradan 6'ya geçilir; en sonda 1'e dönülüp 4 alınır. BFS(7): (7,3), (7,4), (7,5), (7,6), (3,1), (5,2), (1,0). İki ağaçta da yedi kenar vardır.

4. K₄'ün kaç kapsayan ağacı vardır? Kaçı yol, kaçı yıldız biçimlidir?

   Çözüm

   16 (4⁴⁻²). Yıldızlar merkezin seçimiyle belirlenir: 4. Yollar dört düğümün sıralamalarıdır, ters okuma aynı yolu verir: 4!/2 = 12. 12 + 4 = 16.

5. Kenar ağırlıkları 1..10 arası tamsayıysa Kruskal'ın sıralama adımı nasıl O(e)'ye iner?

   Çözüm

   Karşılaştırmaya dayalı sıralama yerine sayarak sıralama (counting sort) ya da kova sıralaması kullanılır. Her ağırlık için bir kova açılır, kenarlar ağırlıklarına göre kovalara dağıtılır ve kovalar sırayla okunur. Maliyet O(e + 10) = O(e)'dir. Kruskal'ın toplam süresi bu durumda union-find işlemlerine iner.

6. Prim'in O(n²) sürümü neden seyrek çizgede kötüdür?

   Çözüm

   Her turda kenar sayısından bağımsız olarak n düğümü tarar. e ≈ n olan bir çizgede heap'li sürüm O(e log n) = O(n log n) sürer; O(n²) bundan çok büyüktür. 5000 düğüm ve 20 000 kenarlı rastgele bir çizgede ölçülen süreler 0,106 ve 0,003 saniyedir.

17.11Özet

• Kapsayan ağaç, bağlantılı bir çizgenin bütün düğümlerini n − 1 kenarla, döngüsüz bağlayan alt çizgesidir. DFS ve BFS birer kapsayan ağaç üretir; kenarları ağaç ve ağaç dışı olarak ikiye ayırır.
• Bağlantılılık, döngüsüzlük ve n − 1 kenar özelliklerinden ikisi üçüncüsünü gerektirir. Ağaca kenar eklemek tek bir döngü kurar, ağaçtan kenar silmek ağacı ikiye böler.
• Kapsayan ağaçların sayısı hızla büyür: K_n'de nⁿ⁻². Hepsini denemek pratik değildir; eş biçimliliği sınamak ayrıca zor bir problemdir.
• Minimum kapsayan ağaç, toplam ağırlığı en küçük kapsayan ağaçtır. Açgözlü seçim doğru sonuç verir; gerekçesi kesit özelliğidir. Ağırlıklar farklıysa ağaç tektir.
• Kruskal kenarları artan maliyetle dener, döngüyü union-find ile yakalar ve n − 1 kenar seçince durur: O(e log e). Ara durumlar ormandır.
• Union-find bir ata dizisidir; kökte küme boyutunun eksi işaretlisi durur. Ağırlıklı kural yüksekliği O(log n)'de tutar, yol kısaltma işlem başına maliyeti pratikte sabite indirir.
• Prim tek bir ağacı en ucuz kenarla büyütür ve döngü denetimine ihtiyaç duymaz. enaz/yakin dizileriyle O(n²), komşuluk listesi ve heap ile O(e log n) sürer.
• Aynı fikir, farklı yapı: liste aramasıyla O(e · n) süren Kruskal kümelerle O(e log e)'ye iner.
• Seyrek çizgede Kruskal ya da heap'li Prim, yoğun çizgede dizili Prim seçilir. Sollin (Borůvka) turlar hâlinde çalışır ve paralelleştirmeye uygundur.
• Minimum kapsayan ağaç toplam maliyeti, en kısa yol ağacı kaynaktan uzaklıkları küçültür; ikisi farklı ağaçlardır.

17.12Kavram listesi

Terimlerin İngilizce karşılıkları ve öteki bölümlerdeki kullanımları terim sözlüğünde bulunur.

• kapsayan ağaç spanning tree
• minimum kapsayan ağaç minimum spanning tree
• orman forest
• eş biçimli isomorphic
• tam çizge complete graph
• ağırlıklı çizge weighted graph
• bağlantılı bileşen connected component
• döngü cycle
• açgözlü yöntem greedy method
• Kruskal algoritması Kruskal's algorithm
• Prim algoritması Prim's algorithm
• Sollin (Borůvka) algoritması Sollin's algorithm
• ayrık kümeler disjoint sets
• küme bulma find
• birleşim union
• ağırlıklı kural weighting rule
• yol kısaltma path compression
• ters Ackermann fonksiyonu inverse Ackermann function
• min-heap min-heap
• öncelikli kuyruk priority queue
• aşağıdan yukarıya heap oluşturma bottom-up heap construction
• komşuluk listesi adjacency list
• derinlik öncelikli arama depth-first search
• genişlik öncelikli arama breadth-first search
• en kısa yol shortest path
• sayarak sıralama counting sort

17.13Kendini Dene

1. 10 düğümlü, 15 kenarlı bağlantılı bir çizgenin her kapsayan ağacında kaç kenar vardır? DFS bu çizgede kaç kenarı ağaç dışında bırakır?

   Cevap

   Kapsayan ağaçta n − 1 = 9 kenar vardır. Kalan 15 − 9 = 6 kenar ağaç dışıdır; bu sayı gezinmenin türünden ve başlangıç düğümünden bağımsızdır.

2. K₅'in kaç kapsayan ağacı vardır? Bunlardan kaçı yıldız biçimlidir?

   Cevap

   Cayley formülüyle 5³ = 125. Yıldızın merkezi beş biçimde seçilir: 5 yıldız.

3. Yedi köy çizgesinde Kruskal hangi kenarları döngü kurdukları için bırakır? Hangi kenara hiç bakmaz?

   Cevap

   (3,6) 18 ve (4,6) 24 döngü kurar: ikisinin de uçları o anda aynı öbektedir. (0,1) 28'e hiç bakılmaz, çünkü (4,5) 25 seçildiğinde altı kenar tamamlanmıştır.

4. ata = [−3, 0, 0, −2, 3] veriliyor. kume_bul(ata, 2) ne döndürür? Ardından birlestir(ata, 0, 3) çağrılırsa dizi ne olur?

   Cevap

   ata[2] = 0, ata[0] = −3 < 0: kök 0'dır. Birleşimde ata[0] = −3 <= ata[3] = −2 olduğundan 0 kök kalır: ata[0] = −5, ata[3] = 0. Dizi [−5, 0, 0, 0, 3] olur; 4'ün ebeveyni hâlâ 3'tür.

5. Yedi köy çizgesinde Prim 3'ten başlatılırsa kenarlar hangi sırayla seçilir? Maliyet değişir mi?

   Cevap

   (3,2) 12, (2,1) 16, (1,6) 14, (3,4) 22, (4,5) 25, (5,0) 10. Maliyet yine 99'dur; ağırlıklar farklı olduğundan ağaç tektir, yalnız seçilme sırası değişir.

6. Heap'li Prim'de if (secildi[u]) continue; satırı silinirse yedi köy çizgesinde ne olur?

   Cevap

   Bayat kayıtlar da işlenir. 6:18, 6:24 ve 1:28 kayıtları çıktığında 6 ve 1 yeniden “ağaca alınır” ve komşuları yeniden taranır. Komşuların hepsi işaretli olduğu için enaz ve yakin bozulmaz. Ama ağaca giren düğüm sayısı ya da toplam bu satırda sayılıyorsa düğümler birden çok kez sayılır; satır 5, her düğümün tam bir kez işlenmesini güvenceye alır.

7. 1000 düğümlü ve 3000 kenarlı bir yol ağı ile 1000 düğümlü ve yaklaşık 500 000 kenarlı bir tam çizge veriliyor. Her biri için hangi Prim gerçeklemesi seçilmelidir?

   Cevap

   Yol ağı seyrektir: heap'li Prim yaklaşık e log n ≈ 3000 · 10 = 30 000, dizili Prim n² = 10⁶ adım tutar; heap seçilir. Tam çizge yoğundur: heap'li sürüm 5 · 10⁵ · 10 = 5 · 10⁶ civarında heap işi yapar, dizili sürüm 10⁶ ile kalır; dizili Prim seçilir.

8. Bütün kenar ağırlıkları farklı bir çizgede en ağır kenar minimum kapsayan ağaçta olabilir mi?

   Cevap

   Olabilir, ama yalnız o kenar bir döngüde değilse, yani silinince çizge kopuyorsa. Örneğin bir düğüme tek bir kenarla bağlanılıyorsa o kenar ne kadar pahalı olursa olsun her kapsayan ağaçta bulunur. Kenar bir döngüdeyse döngü özelliğine göre ağaçta bulunamaz.

17.14İleri okuma

• E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2. baskı, Kesim 6.3. Bu notun Kruskal ve Prim sözde kodları ile yedi köy örneği oradaki biçimiyle izlenmiştir; Sollin algoritması da aynı kesimde anlatılır.
• T. H. Cormen ve ark., Introduction to Algorithms, 4. baskı, Bölüm 19 ve 21. Ayrık küme ormanlarının amortize analizi, ters Ackermann sınırının kanıtı ve kesit özelliğinin “güvenli kenar” adıyla genel kanıtı buradadır.
• R. Sedgewick, Algorithms in C, Part 5: Graph Algorithms, 3. baskı, Bölüm 20. Prim, Kruskal ve Borůvka'nın C gerçeklemeleri, büyük rastgele çizgelerde yapılmış deneysel karşılaştırmalarla birlikte verilir.

17.15Kaynaklar

1. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2. bs., Silicon Press, 2008. Kesim 6.3, Minimum Cost Spanning Trees.
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. bs., MIT Press, 2022. Bölüm 19, Data Structures for Disjoint Sets; Bölüm 21, Minimum Spanning Trees.
3. R. Sedgewick, Algorithms in C, Part 5: Graph Algorithms, 3. bs., Addison-Wesley, 2002. Bölüm 20, Minimum Spanning Trees.

İlgili sayfalar: Bölüm 17 sunumu · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.