Bölüm 14: Çizgeler

14.1Temel kavramlar

Çizge algoritmalarını okumak için önce küçük bir sözlüğe ihtiyaç vardır: düğüm, kenar, derece, yol, döngü, bağlantılılık. Bu kavramların çoğu günlük dildeki anlamlarına yakındır. Yine de her birinin kesin bir tanımı vardır. Algoritmaların doğru çalışıp çalışmadığı da çoğu zaman bu kesin tanımlara bakarak anlaşılır.

14.1.1Çizge nedir?

Bir şehir haritasını düşünelim. Haritada kavşaklar ve kavşakları birbirine bağlayan yollar vardır. Bir yolun uzunluğu, eğimi, kaç şeritli olduğu gibi pek çok ayrıntı da vardır. “Hangi kavşaktan hangi kavşağa gidilebilir?” sorusunu yanıtlamak için bu ayrıntıların çoğu gereksizdir. Yalnız iki bilgi yeter: kavşakların listesi ve hangi iki kavşağın doğrudan bir yolla bağlı olduğu. Bu iki bilginin oluşturduğu soyut yapıya çizge (graph) denir.

Tanımdaki |V| gösterimi, V kümesinin eleman sayısı demektir. Not boyunca n her zaman düğüm sayısını, m her zaman kenar sayısını gösterir. Algoritmaların maliyeti de bu iki sayıyla ifade edilir; örneğin “O(n + m) zaman” ifadesi, sürenin düğüm sayısı ile kenar sayısının toplamıyla orantılı büyüdüğü anlamına gelir.

Çizge, ağacın genelleştirilmiş hâli olarak da düşünülebilir. Ağaçta bir kök vardır, her düğümün (kök dışında) tek bir ebeveyni vardır ve döngü yoktur. Çizgede bu kuralların hiçbiri aranmaz:

• Kök yoktur. Hiçbir düğüm ötekilerden ayrıcalıklı değildir. Bir algoritma bir düğümden başlayacaksa bu başlangıç düğümü ayrıca verilir.
• Döngü olabilir. Bir düğümden çıkıp kenarlar boyunca ilerleyerek aynı düğüme geri dönmek mümkündür. Şekil 14.1'de 1 → 2 → 3 → 1 böyle bir dönüştür.
• Bir düğüme birden çok yoldan ulaşılabilir. 0'dan 3'e hem 0 → 1 → 3 hem de 0 → 4 → 3 yoluyla gidilir.

Ağaç “bire-çok” ilişkiyi modeller: bir ebeveynin çok çocuğu olur ama her çocuğun tek ebeveyni vardır. Çizge ise “çoğa-çok” ilişkiyi modeller. Bir kişinin pek çok arkadaşı olur; bu arkadaşların her birinin de başka pek çok arkadaşı vardır. Bir ders birkaç dersin ön koşuludur; aynı dersin kendisi de birkaç ön koşula bağlıdır. Bu esneklik çizgeyi güçlü bir model yapar. Bedeli ise algoritmalarda ortaya çıkar: aynı düğüme ikinci kez gelme ihtimali her zaman vardır ve algoritma bunu fark etmek zorundadır.

14.1.2Düğüm ve kenar

Düğüm, çizgenin temel yapı taşıdır ve modellenen nesneyi temsil eder: bir şehir, bir kişi, bir bilgisayar, bir web sayfası, bir ders. Düğüm yalnız bir numaradan ibaret olmak zorunda değildir; bir etiket, bir ad ya da haritadaki konum gibi bir değer de saklayabilir. Algoritmalar içinse düğümleri 0'dan n − 1'e numaralamak en pratik yoldur. Böylece düğüme ait bilgiler dizilerde, düğüm numarası indis olacak biçimde tutulabilir.

Harita çizge olarak modellenince “İstanbul'dan Van'a en kısa yol hangisi?” sorusu bir çizge algoritması problemine dönüşür. Kenarlara yolların uzunluğu yazılırsa bu problemi Dijkstra algoritması çözer (14.4.4). Modelleme, problemin özünü koruyup gereksiz ayrıntıyı atmak demektir. Yolun asfalt mı stabilize mi olduğu en kısa yol için önemli değildir, ama uzunluğu önemlidir.

Kenar, iki düğüm arasındaki ilişkiyi temsil eder: iki şehir arasındaki yol, iki bilgisayar arasındaki ağ bağlantısı, iki kişi arasındaki arkadaşlık. (v, w) bir kenar ise v ile w'ye komşu ya da bitişik (adjacent) düğümler denir. Kenar da bu iki düğüme bağlıdır (incident). Şekil 14.1'de 1 ile 3 komşudur, 0 ile 2 komşu değildir.

Şekil 14.3 gerçek ağların tipik bir özelliğini gösterir: düğüm sayısı büyüktür ama her düğümün yalnız birkaç komşusu vardır. Bir sosyal ağda milyonlarca kişi bulunur, oysa bir kişinin arkadaş sayısı en çok birkaç yüz ya da birkaç bindir. Kenar sayısı, olabilecek en büyük kenar sayısının çok küçük bir kesridir. Böyle çizgelere seyrek çizge denir. Seyreklik, çizgenin bellekte nasıl saklanacağına karar verirken belirleyici olur (14.2.6).

14.1.3Derece ve el sıkışma lemması

Günlük hayattaki karşılığı kolaydır: bir kavşağın derecesi, o kavşağa giren yolların sayısıdır. Öz döngünün neden 2 saydığı da bu benzetmeyle görülür. Kavşaktan çıkıp yine aynı kavşağa dönen bir yol kavşağa iki ucuyla bağlanır; kavşakta duran biri o yolun iki ağzını görür.

Şekil 14.4'teki çizgede derecelerin toplamını alalım: 1 + 3 + 3 + 2 + 5 + 2 + 0 = 16. Çizgede yedi sıradan kenar ve bir öz döngü, toplam sekiz kenar vardır. Toplamın kenar sayısının tam iki katı çıkması rastlantı değildir.

Adı, bir toplantıdaki el sıkışmalardan gelir: herkes kaç kişiyle el sıkıştığını söylerse bu sayıların toplamı, el sıkışma sayısının iki katıdır. Çünkü her el sıkışmada iki el vardır. Lemmanın iki pratik sonucu vardır:

• Dereceler biliniyorsa kenar sayısı hemen bulunur: m = Σ deg(v) / 2. Örneğin derecelerin toplamı 30 olan bir çizgede 15 kenar vardır.
• Toplam her zaman çifttir. Bu yüzden tek dereceli düğümlerin sayısı da her zaman çifttir. Çift dereceler toplamı çift yapar; tek derecelerin toplamının da çift olması için bunlardan çift sayıda bulunmalıdır. Dereceleri 3, 3, 2, 2, 1 olan bir çizge kurulamaz: toplam 11 tektir.

14.1.4Yönlü çizge

Bazı ilişkiler simetriktir. A, B'nin arkadaşıysa B de A'nın arkadaşıdır; iki şehir arasındaki çift yönlü yol her iki yönde kullanılır. Bazı ilişkiler ise tek yönlüdür. Bir web sayfası başka bir sayfaya bağlantı verebilir ama o sayfa geri bağlantı vermeyebilir. Bir ders başka bir dersin ön koşuludur, tersi doğru değildir. Tek yönlü sokakta yalnız bir yönde gidilir. Bu ilişkiler yönlü çizgeyle (directed graph, kısaca digraph) modellenir.

Tablodaki değerler oklar tek tek sayılarak bulunur. B'ye iki ok gelir: A'dan ve D'den. Bu yüzden B'nin giriş derecesi 2'dir. E'den iki ok çıkar: D'ye ve F'ye. Bu yüzden E'nin çıkış derecesi 2'dir. A'ya hiç ok gelmez; F'den hiç ok çıkmaz.

Satır toplamlarının ikisi de 6'dır ve çizgedeki kenar sayısına eşittir. Bu, el sıkışma lemmasının yönlü karşılığıdır: her ok kuyruğundaki düğümün çıkış derecesine 1, başındaki düğümün giriş derecesine 1 ekler. Dolayısıyla Σ giriş derecesi = Σ çıkış derecesi = m'dir. Yönsüz çizgedeki 2m'nin yerini burada iki ayrı toplam alır.

Yönlü çizgede ulaşılabilirlik de yöne bağlıdır. Şekil 14.5'te A'dan B'ye bir ok vardır, ama B'den A'ya hiçbir yol yoktur: A'ya hiç ok gelmez. Öte yandan B'den C'ye, oradan E'ye, D'ye ve yeniden B'ye gidilebilir. Yani B, C, E, D birbirine ulaşabilir; A ve F bu gruba dışarıdan bağlıdır.

14.1.5Yol ve döngü

Yolun uzunluğu, ağırlıksız çizgede üzerindeki kenar sayısıdır; k + 1 düğümlü bir yol k kenar uzunluğundadır. Yönlü çizgede yol, okların yönünde ilerlemelidir; böyle bir yola yönlü yol, yönlü bir döngüye de yönlü döngü denir.

Şekil 14.6'daki iki döngünün her biri altı kenar uzunluğundadır. Bunlar çizgedeki tek döngüler değildir. Örneğin C → G → L → C de bir döngüdür; C–G, G–L ve L–C kenarları vardır. Bir çizgedeki döngü sayısı, kenar sayısı arttıkça hızla büyür.

Ağaçta döngü yoktur. Ağaçta iki düğüm arasında tek bir basit yol bulunur. Çizgede ise iki düğüm arasında birden çok basit yol olabilir; iki farklı basit yol birleşince bir döngü oluşur. Uçuş rotalarıyla bir örnek verelim. İstanbul → Ankara → İzmir → İstanbul bir döngüdür. Uçak arada aynı şehre ikinci kez uğramadığı için bu basit bir döngüdür. Rota İstanbul → Ankara → İzmir → Ankara → İstanbul olsaydı Ankara iki kez geçerdi; döngü yine döngüdür ama basit değildir.

14.1.6İki örnek çizge

Kavramları küçük bir yönsüz ve küçük bir yönlü çizge üzerinde birlikte uygulayalım.

Bir dizinin yol olup olmadığını anlamak için ardışık her çiftin arasında kenar olup olmadığına bakılır. Örneğin 2 → 5 → 3 bir yol değildir, çünkü 5–3 kenarı yoktur. Basitlik ise ikinci bir denetimdir: önce dizi yol olmalı, sonra düğüm tekrarına bakılır.

14.1.7Bağlantılı çizge ve tam çizge

İki tanım arasındaki farka dikkat etmek gerekir. Bağlantılılık yol ister, tamlık kenar ister. Tam çizge her zaman bağlantılıdır, ama bağlantılı bir çizge tam olmak zorunda değildir. Bileşen tanımındaki “en büyük” sözcüğü de önemlidir: bir bileşene, ondaki herhangi bir düğüme yolla ulaşabilen her düğüm dahildir. Bileşenler çizgenin düğümlerini çakışmayan gruplara ayırır. Bağlantılı bir çizgenin tek bir bileşeni vardır.

Kenar sayısı için iki sınır vardır. Basit (öz döngüsüz ve çift kenarsız) yönsüz bir çizgede her düğüm çifti en çok bir kenarla bağlanır. Farklı düğüm çiftlerinin sayısı n(n − 1)/2'dir: ilk düğüm n biçimde, ikinci düğüm n − 1 biçimde seçilir ve her çift iki kez sayıldığı için 2'ye bölünür. Bu yüzden m ≤ n(n − 1)/2'dir ve eşitlik yalnız tam çizgede sağlanır. K₅'te 5 · 4 / 2 = 10, 10 düğümlü tam çizgede 10 · 9 / 2 = 45 kenar vardır.

Alt sınır bağlantılılıktan gelir. Bağlantılı bir çizgede m ≥ n − 1'dir. Bunu görmek için kenarları boş bir çizgeye tek tek eklediğimizi düşünelim. Başta n bileşen vardır; her yalnız düğüm ayrı bir bileşendir. Bir kenar eklemek bileşen sayısını en çok 1 azaltır: ya iki bileşeni birleştirir ya da aynı bileşenin içine düşer. Tek bileşene inmek için en az n − 1 kenar gerekir. Tam n − 1 kenarlı bağlantılı çizge bir ağaçtır; bu gözlem kapsayan ağaçta yeniden karşımıza çıkar (14.5.1).

Bu iki sınır, seyrek ve yoğun çizge ayrımının da temelidir. Kenar sayısı n mertebesindeyse (m ≈ n) çizge seyrektir; n² mertebesindeyse (m ≈ n²) yoğundur. Yol ağları ve sosyal ağlar seyrektir. Herkesin herkesle doğrudan bağlantılı olduğu küçük gruplar yoğundur.

14.1.8Ağırlıklı çizge

Pek çok problemde yalnız “bağlı mı?” sorusu yetmez; bağlantının bir bedeli vardır. İki şehir arasındaki yolun uzunluğu, bir ağ bağlantısının gecikmesi, bir boru hattının maliyeti ya da bir hattın kapasitesi bu türden bilgilerdir.

Bu gözlem, en kısa yol algoritmalarının neden gerektiğini açıklar. Ağırlıksız çizgede en kısa yol en az kenarlı yoldur. Ağırlıklı çizgede ise kenar sayısı yanıltıcıdır; ağırlıkların toplamına bakmak gerekir. Ağırlıksız çizgeyi, her kenarın ağırlığının 1 olduğu ağırlıklı çizge olarak da düşünebiliriz.

14.1.9Çizge ADT'si

Çizge de öteki veri yapıları gibi önce bir soyut veri tipi (abstract data type, ADT) olarak tanımlanabilir. ADT, hangi işlemlerin bulunduğunu ve ne yaptıklarını söyler; bu işlemlerin bellekte nasıl yürütüleceğini söylemez. Goodrich, Tamassia ve Goldwasser'in kitabındaki Graph arayüzü, aşağıdaki temel işlemleri içerir.

Algoritmaların en çok kullandığı iki işlem öne çıkar. Birincisi getEdge(u, v), yani “u ile v komşu mu?” sorusudur. İkincisi outgoingEdges(v), yani “v'nin komşuları kimler?” sorusudur. BFS, DFS, Dijkstra ve Prim gibi algoritmalar ikinci işlemi her düğüm için bir kez çağırır. Bu yüzden bir gösterimin komşuları ne kadar hızlı verdiği, algoritmaların toplam süresini doğrudan belirler.

removeVertex(v)'nin bağlı kenarları da silmesi bir tutarlılık kuralıdır. Ucu olmayan bir kenar anlamsız olur; bu yüzden düğümle birlikte ona bağlı bütün kenarlar da çizgeden çıkar. Bu işlemlerin maliyeti çizgenin bellekte nasıl temsil edildiğine bağlıdır.

14.2Çizge gösterimleri

Bir çizgeyi bilgisayarda saklamanın tek bir doğru yolu yoktur. Aynı çizge üç farklı biçimde tutulabilir ve her biçim bazı işlemleri hızlandırırken bazılarını yavaşlatır. Bu kesimde üç temel gösterimi sırayla ele alıyor, sonra bunları bellek ve işlem maliyetleri açısından karşılaştırıyoruz. Kesimin sonunda komşuluk listesinin ve matrisinin Java ile nasıl kurulduğunu satır satır izliyoruz.

14.2.1Üç temel gösterim ve kenar listesi

Çizgeyi saklamanın üç temel yolu şunlardır:

• Kenar listesi (edge list): bütün kenarlar tek bir listede tutulur, örneğin [(A,B), (A,E), …].
• Komşuluk listesi (adjacency list): her düğüm için o düğümün komşularının listesi tutulur, örneğin V[i] = {j, k, l}.
• Komşuluk matrisi (adjacency matrix): n × n boyutlu iki boyutlu bir dizi tutulur; M[i][j] hücresi i'den j'ye kenar olup olmadığını gösterir.

Kenar listesi en basit gösterimdir. Şekil 14.11'deki çizge için liste (A, B) (A, E) (B, C) (B, E) (C, D) (D, E) biçimindedir. Kenarı olmayan düğümleri kaybetmemek için düğümler de ayrı bir listede tutulur; böylece bellek O(n + m) olur. Yeni bir kenar eklemek listenin sonuna bir öğe eklemektir ve O(1) sürer.

Kenar listesinin zayıflığı sorgulardadır. “u ile v komşu mu?” sorusunu yanıtlamak için listede (u, v) ya da (v, u) aranır. Liste hiçbir düzene göre sıralı olmadığı için, en kötü durumda bütün liste taranır: O(m). “u'nun komşuları kim?” sorusu da aynı biçimde tüm listeyi taramayı gerektirir, çünkü u'ya bağlı kenarlar listenin herhangi bir yerinde olabilir. Gezinme algoritmaları bu soruyu her düğüm için sorduğundan, kenar listesiyle bir gezinme O(n · m)'ye çıkar. Kenar listesi yine de bir algoritmada işe yarar: Kruskal algoritması kenarları ağırlığa göre sıralayıp tek tek dener ve komşu sorgusu yapmaz (14.5.3).

14.2.2Komşuluk matrisi

Yönsüz çizgede her kenar iki yönde de geçerlidir. (i, j) kenarı hem matris[i][j] hem de matris[j][i] hücresine yazılır. Bu yüzden matris ana köşegene göre simetriktir: her i, j için matris[i][j] == matris[j][i]'dir. Yönlü çizgede bu simetri yoktur.

Matrisin güçlü yanı doğrudan erişimdir. Java'da iki boyutlu bir dizinin herhangi bir hücresi, indisleri bilindiği sürece sabit sürede okunur ve yazılır. Bu yüzden üç işlem O(1)'dir:

• “i ile j arasında kenar var mı?” sorusu, matris[i][j] hücresini okumaktır.
• Kenar eklemek, bir (yönsüzde iki) hücreye 1 yazmaktır.
• Kenar silmek, aynı hücrelere 0 yazmaktır.

Zayıf yanı da iki tanedir. Birincisi, bir düğümün komşularını bulmak için o düğümün satırının n hücresinin hepsine bakmak gerekir. Düğümün tek bir komşusu olsa bile süre O(n)'dir. İkincisi bellektir: matris, kenar sayısından bağımsız olarak n² hücre kaplar. Seyrek bir çizgede hücrelerin büyük çoğunluğu 0'dır; bellek, var olmayan kenarları kaydetmeye harcanır.

14.2.3Komşuluk matrisi: üç örnek

Aynı beş düğüm (A–E) üzerinde yönsüz, yönlü ve ağırlıklı üç çizgenin matrislerini karşılaştıralım. Satırlar ve sütunlar A, B, C, D, E sırasıyla dizilmiştir.

Yönsüz matriste her kenar iki hücreye yazılmıştır; altı kenar 12 tane 1 verir. Matris köşegene göre simetriktir: örneğin A satırının E sütunu ile E satırının A sütunu ikisi de 1'dir. Bir satırın toplamı, o düğümün derecesidir. B satırında üç tane 1 vardır (A, C, E), dolayısıyla deg(B) = 3'tür. Köşegen 0'dır, çünkü çizgede öz döngü yoktur.

Yönlü matriste her ok yalnız bir hücreye yazılır: dokuz ok, dokuz tane 1. Satır kaynağı, sütun hedefi gösterir; bu yüzden matris simetrik değildir. A → B oku m[A][B] = 1 yapar, ama B → A oku olmadığı için m[B][A] = 0'dır. Satır toplamı çıkış derecesini, sütun toplamı giriş derecesini verir. D satırında üç tane 1 vardır: D'nin çıkış derecesi 3'tür. C satırının tamamı 0'dır: C'den hiç ok çıkmaz. C sütununda ise iki tane 1 vardır (B ve D'den): C'nin giriş derecesi 2'dir.

Ağırlıklı matriste hücre, kenarın ağırlığını tutar. A satırının B sütunundaki 4, A → B okunun ağırlığıdır. Kenar olmayan hücrelere ∞ yazılır. Köşegende ise 0 vardır: bir düğümün kendisine uzaklığı sıfırdır. Bu gösterim en kısa yol problemlerinde kullanışlıdır, çünkü ∞ “doğrudan gidilemez” anlamına gelir ve toplamalarda kendiliğinden doğru davranır: ∞ artı herhangi bir sayı yine ∞'dur.

14.2.4Komşuluk listesi

Yönsüz çizgede bir (v, w) kenarı iki listeye birden eklenir: w, v'nin listesine; v, w'nin listesine. Yönlü çizgede ise yalnız kaynağın listesine eklenir. Listede yalnız var olan kenarlar yer aldığı için bellek n liste başı ile toplam kayıt sayısının toplamıdır. Yönsüz çizgede kayıt sayısı 2m, yönlü çizgede m'dir. Her iki durumda bellek O(n + m)'dir.

Komşuluk listesinin güçlü yanı gezinmedir. Bir düğümün komşularını gezmek, onun listesini baştan sona okumaktır ve O(deg(v)) sürer. Matristeki gibi komşu olmayan düğümlere boşuna bakılmaz. Kenar eklemek de listenin sonuna bir öğe eklemektir; dinamik dizide amortize O(1), bağlı listede O(1)'dir.

Zayıf yanı, “u ile v arasında kenar var mı?” sorgusudur. Listeler sıralı tutulmadığı sürece v'yi bulmak için u'nun listesi taranır: O(deg(u)). Yönsüz çizgede iki listeden kısa olanı seçilebilir ve süre O(min(deg u, deg v)) olur. Bir düğümün derecesi büyükse bu sorgu matristeki O(1)'e göre yavaştır.

14.2.5Komşuluk listesi: üç örnek

Şekil 14.13'teki üç çizgenin komşuluk listeleri aşağıdadır. Komşular alfabetik sırayla yazılmıştır.

• Yönsüz. Altı kenar listelerde 12 kayıt oluşturur; her kenar iki kez yazılır. Bir listenin uzunluğu, düğümün derecesidir: B'nin listesi üç öğelidir ve deg(B) = 3'tür.
• Yönlü. Yalnız çıkan kenarlar listelenir. Dokuz ok dokuz kayıt verir. C'den çıkan ok olmadığı için C'nin listesi boştur. Liste uzunluğu burada çıkış derecesidir. Giriş derecesini bulmak için bütün listeleri taramak gerekir; bu, listenin yönlü çizgedeki bir eksiğidir.
• Ağırlıklı. Her kayıt (komşu, ağırlık) çifti tutar. B'nin listesi (C, 3), (D, 3)'tür. Java'da bu çift int[]{v, w} dizisiyle ya da küçük bir Kenar sınıfıyla temsil edilir.

14.2.6Gösterimlerin maliyeti

Tablo, seçimin çizgenin yapısına ve en sık yapılan işleme göre verilmesi gerektiğini gösterir. İki tipik durum vardır:

• Seyrek çizge (m ≈ n). Yol ağları ve sosyal ağlar bu türdendir. Matris n² hücre ister ve hücrelerin neredeyse tamamı boş kalır. Komşuluk listesi hem belleği O(n + m)'de tutar hem de gezinmeyi hızlandırır. Bu notta incelenen bütün gezinme ve en kısa yol algoritmaları listeyle O(n + m) ya da ona yakın sürede çalışır.
• Yoğun çizge (m ≈ n²). Kenarların çoğu varsa matrisin boş hücresi azdır ve bellek kaybı önemsizleşir. “Kenar var mı?” sorgusu sık yapılıyorsa matrisin O(1) erişimi belirleyici olur.

14.2.7Java ile komşuluk listesi

Düğümler 0'dan n − 1'e numaralanırsa komşuluk listesi, listelerden oluşan bir liste olarak yazılabilir. Dış listenin i. öğesi, i düğümünün komşu listesidir.

class Cizge {
    private final int n;                                  // düğümler: 0..n-1
    private final List<List<Integer>> komsu = new ArrayList<>();
    Cizge(int n) {
        this.n = n;
        for (int i = 0; i < n; i++)
            komsu.add(new ArrayList<>());
    }
    void kenarEkle(int u, int v) {
        komsu.get(u).add(v);
        komsu.get(v).add(u);                  // yönlü çizgede bu satır yok
    }
    List<Integer> komsular(int u) { return komsu.get(u); }   // O(1)
    int derece(int u) { return komsu.get(u).size(); }
}

Kodun parçaları şunlardır:

• komsu alanı List<List<Integer>> türündedir. Dış liste düğüm başına bir iç liste tutar; iç listeler ArrayList, yani dinamik dizidir.
• Yapıcı, n'yi saklar ve döngüyle n tane boş iç liste ekler. Bu adım O(n) zaman alır. Düğümlerin hepsi baştan bilindiği için listeler önceden açılır; böylece komsu.get(u) her u için geçerli bir liste döndürür.
• kenarEkle(u, v) iki satırdır: v'yi u'nun listesine, u'yu v'nin listesine ekler. Yönlü çizgede ikinci satır yazılmaz. ArrayList.add amortize O(1)'dir; metot da öyledir.
• komsular(u) listenin kendisini döndürür; kopyalama yapılmadığı için O(1)'dir. Listenin gezilmesi ise çağıranın işidir ve O(deg(u)) sürer.
• derece(u), listenin boyutudur. ArrayList boyutunu bir alanda tuttuğu için bu da O(1)'dir.

Matris karşılığı daha kısadır: boolean[][] m = new boolean[n][n]; diziyi oluşturur, m[u][v] = m[v][u] = true; kenar ekler, m[u][v] sorgular. Ağırlıklı çizgede listenin öğesi int[]{v, w} ya da küçük bir Kenar sınıfı olur; matris ise int[][] olur ve kenarsız hücrelere Integer.MAX_VALUE yazılır.

14.2.8Kod izleme: komşuluk listesi kurma

Beş düğümlü bir çizgeyi altı kenarla kuralım. Kenarlar sırasıyla {0,1}, {0,4}, {1,2}, {1,4}, {2,3}, {3,4}'tür. İzlenen kod, sınıfın yapıcısı ile kenarEkle metodu ve bunları çağıran main parçasıdır.

Cizge(int n) {
  this.n = n;
  for (int i = 0; i < n; i++)
    komsu.add(new ArrayList<>());
}
void kenarEkle(int u, int v) {
  komsu.get(u).add(v);
  komsu.get(v).add(u);  // yönlüde yok
}
// main:
Cizge g = new Cizge(5);
int[][] E = {{0,1}, {0,4}, {1,2},
             {1,4}, {2,3}, {3,4}};
for (int[] e : E) g.kenarEkle(e[0], e[1]);

İzlemenin ilk aşaması yapıcıdır. new Cizge(5) çağrısında n = 5 atanır; komsu henüz boş bir dış listedir. Döngü i = 0'dan i = 4'e beş tur döner ve her turda boş bir iç liste ekler. Döngü bittiğinde her düğümün boş bir komşu listesi vardır.

İkinci aşama kenarlardır. kenarEkle(0, 1)'in ilk satırı 1'i 0'ın listesinin sonuna ekler. İkinci satır aynı kenarı ters yönde işler ve 0'ı 1'in listesine ekler. Sonraki her çağrı aynı iki adımı yapar. Listelerdeki sıra, ekleme sırasıdır: 1'in listesi [0, 2, 4] olur, çünkü 0–1, 1–2 ve 1–4 kenarları bu sırayla gelmiştir.

Sonuçta altı kenar, listelerde 2 · 6 = 12 kayıt oluşturur. Liste uzunlukları 2, 3, 2, 2, 3'tür ve toplamları 12'dir; bu da el sıkışma lemmasının kodda görünen biçimidir. derece(1), 1'in listesinin boyutudur ve 3 döndürür. Her kenarEkle çağrısı sabit sürelidir; bellek O(n + m)'dir.

14.2.9Kod izleme: komşuluk matrisi kurma

Aynı altı kenarı bu kez 5 × 5 boyutlu bir boolean matrise ekleyelim.

boolean[][] m = new boolean[n][n];
void kenarEkle(int u, int v) {
  m[u][v] = true;
  m[v][u] = true;  // yönlü çizgede yok
}
// main: aynı 6 kenar (n = 5)
for (int[] e : E) g.kenarEkle(e[0], e[1]);

new boolean[n][n] 25 hücrelik bir matris ayırır. Java, boolean dizisinin bütün hücrelerini false ile başlatır; başlangıçta hiç kenar yoktur. Matrisin oluşturulması bile O(n²) sürer, çünkü 25 hücrenin her biri başlangıç değerini almak zorundadır.

Her kenarEkle(u, v) iki hücre yazar. kenarEkle(0, 1) önce m[0][1] = true yapar (satır 0, sütun 1), sonra simetrik hücreyi, m[1][0]'ı true yapar. Altı kenar sırayla şu hücre çiftlerini doldurur: (0,1)–(1,0), (0,4)–(4,0), (1,2)–(2,1), (1,4)–(4,1), (2,3)–(3,2), (3,4)–(4,3).

Bu küçük örnekte bile iki gösterimin farkı görülür. “2–4 kenarı var mı?” sorusu m[2][4] hücresine tek erişimle yanıtlanır: false, yani kenar yok. Aynı soruyu listeyle yanıtlamak için 2'nin listesi [1, 3] taranır. Öte yandan 2'nin komşularını bulmak için matriste 2. satırın beş hücresinin hepsi okunur; listede ise yalnız iki öğe okunur. Matrisin 25 hücresinden 13'ü hiçbir bilgi taşımaz. Çizge büyüdükçe ve seyrekleştikçe bu oran hızla kötüleşir.

14.3Gezinme: BFS ve DFS

Çizge algoritmalarının çoğu, çizgeyi sistemli biçimde dolaşan bir iskelet üzerine kurulur. Bu iskeletin iki temel türü vardır: genişlik öncelikli arama ve derinlik öncelikli arama. İkisi de aynı düğüm kümesini ziyaret eder; farkları ziyaret sırasındadır. Sıranın farklı olması, her birini farklı problemlere uygun kılar. Kesimin ikinci yarısında bu iki aramanın üzerine kurulan dört uygulamayı ele alıyoruz: bağlantılı bileşenler, iki parçalılık testi, topolojik sıralama ve yönlü döngü tespiti.

14.3.1Gezinme ve ziyaret işareti

İki temel gezinme yöntemi vardır:

• Genişlik öncelikli arama (breadth-first search, BFS) önce başlangıcın bütün komşularını, sonra onların komşularını ziyaret eder. Seviye seviye ilerler. Yardımcı yapı olarak kuyruk (FIFO: ilk giren ilk çıkar) kullanır.
• Derinlik öncelikli arama (depth-first search, DFS) bir yol boyunca gidebildiği kadar derine iner. Çıkmaza gelince geri döner ve başka bir dalı dener. Yardımcı yapı olarak yığın (LIFO: son giren ilk çıkar) ya da özyineleme kullanır.

Ağaçta gezinme ile çizgede gezinme arasında önemli bir fark vardır. Ağaçta bir düğüme kökten tek bir yol vardır; çocuklara inerek ilerleyen bir algoritma hiçbir düğüme iki kez gelmez. Çizgede ise döngü olabilir ve aynı düğüme birden çok yoldan ulaşılabilir. Bu yüzden çizge gezinmesi hangi düğümleri gördüğünü kaydetmek zorundadır. Bu kayıt çoğunlukla düğüm numarasıyla indislenen bir boolean[] ziyaret dizisidir.

14.3.2Genişlik öncelikli arama

Suya atılan bir taşı düşünelim. Dalgalar taşın düştüğü noktadan halkalar hâlinde yayılır; önce yakın halkalar, sonra uzaktakiler oluşur. BFS de böyle çalışır. Başlangıca 1 kenar uzaklıktaki düğümleri bulur, sonra 2 kenar uzaklıktakileri, sonra 3 kenar uzaklıktakileri. Başlangıçtan k kenar uzaktaki düğümlerin oluşturduğu gruba seviye k denir.

Bu sırayı kuyruk sağlar. Bir düğüm keşfedildiğinde kuyruğun arkasına eklenir; işlenecek düğüm her zaman kuyruğun önünden alınır. Seviye 1'deki düğümlerin hepsi, seviye 2'deki herhangi bir düğümden önce kuyruğa girer. Kuyruk ilk giren ilk çıkar ilkesiyle çalıştığı için seviye 1'in hepsi seviye 2'den önce işlenir.

BFS'nin her düğümü keşfettiği kenarlar bir ağaç oluşturur; buna BFS ağacı denir. Şekil 14.18'de d'ye hem a hem b üzerinden gidilebilir. a daha önce işlendiği için d, a–d kenarıyla keşfedilir; b–d kenarı ağaca girmez. BFS ağacında kökten bir düğüme giden yol, o düğüme giden en az kenarlı yollardan biridir. Bu özellik, ağırlıksız en kısa yol algoritmasının temelidir (14.4.1).

BFS'nin iki güçlü yanı vardır: ağırlıksız çizgede en kısa yolu bulur ve başlangıca yakın düğümleri önce keşfeder. Sosyal ağda “arkadaşlarımın arkadaşları” sorusu seviye 2'deki düğümlerdir; bir web tarayıcı robotu (crawler) bir siteyi bağlantı derinliğine göre katman katman tarar. Zayıf yanı bellektir: bir seviyenin tamamı aynı anda kuyrukta bekleyebilir. Her düğümün çok sayıda komşusu olan geniş çizgelerde kuyruk çok büyüyebilir.

14.3.3BFS algoritması ve kodu

Önce algoritmayı sözde kodla, sonra Java ile verelim.

BFS(başlangıç):
  kuyruk.ekle(başlangıç)
  başlangıç.ziyaretEdildi()
  while kuyruk boş değil:
    w = kuyruk.çıkar()
    for w'nin ziyaret edilmemiş
        her komşusu u:
      u.ziyaretEdildi()
      kuyruk.ekle(u)

void bfs(int s) {
  boolean[] ziyaret = new boolean[n];
  Queue<Integer> q = new ArrayDeque<>();
  ziyaret[s] = true;  q.add(s);
  while (!q.isEmpty()) {
    int w = q.poll();
    System.out.print(w + " ");
    for (int u : komsu.get(w))
      if (!ziyaret[u]) {
        ziyaret[u] = true;
        q.add(u);
      }
  }
}

Java kodu, 14.2.7'deki Cizge sınıfının bir metodu olarak yazılmıştır; n ve komsu alanlarını kullanır. Satır satır inceleyelim:

• boolean[] ziyaret = new boolean[n]; her düğüm için bir işaret ayırır. Java bu diziyi false ile başlatır; başta hiçbir düğüm görülmemiştir.
• Queue<Integer> q = new ArrayDeque<>(); boş bir kuyruk oluşturur. ArrayDeque'te add arkaya ekler, poll öndeki öğeyi çıkarıp döndürür; ikisi de O(1)'dir.
• ziyaret[s] = true; q.add(s); başlangıç düğümünü işaretleyip kuyruğa koyar.
• Döngü, kuyruk boşalana kadar sürer. Her turda öndeki düğüm w çıkarılır ve yazdırılır.
• İç döngü w'nin komşu listesini gezer. Ziyaret edilmemiş her komşu u önce işaretlenir, sonra kuyruğa eklenir.

Kodun en ince noktası işaretin nerede konduğudur. Düğüm kuyruğa girerken işaretlenir, kuyruktan çıkarken değil. Böylece bir düğüm birden çok komşunun listesinde görünse bile kuyruğa yalnız bir kez girer. İşaret kuyruktan çıkarken konsaydı, aynı düğüm kuyrukta beklerken başka bir komşusu onu bir daha ekleyebilirdi.

Maliyet. Her düğüm kuyruğa en çok bir kez girer ve bir kez çıkar: toplam O(n). Her düğüm çıktığında komşu listesi bir kez taranır. Bütün listelerin toplam uzunluğu yönsüz çizgede 2m'dir; tarama toplamı O(m) eder. BFS'nin toplam süresi komşuluk listesiyle O(n + m)'dir. Komşuluk matrisiyle her düğümün satırı n hücre taranacağı için süre O(n²) olur. Ek bellek ziyaret dizisi ve kuyruk için O(n)'dir.

14.3.4Kod izleme: bfs(A)

Dokuz düğümlü bir çizge üzerinde bfs(A)'yı izleyelim. Düğümler A = 0, B = 1, …, I = 8 diye numaralanmıştır. Komşu listeleri alfabetik sıradadır: A: B, F, I · B: A, C, E · C: B, D, E · D: C, G, H · E: B, C, G · F: A, G · G: D, E, F · H: D · I: A. Çizgede 9 düğüm ve 11 kenar vardır.

İzlemenin önemli anları şunlardır. Başlangıçta A işaretlenir ve kuyruğa girer. Birinci turda A çıkar ve yazdırılır; komşuları B, F, I ziyaret edilmemiştir, üçü de işaretlenip sırayla kuyruğa eklenir. Bunlar seviye 1'dir.

İkinci turda kuyruğun önündeki B çıkar. B'nin ilk komşusu A'dır ve zaten işaretlidir; atlanır. Ziyaret işareti olmasaydı A burada kuyruğa ikinci kez girerdi. C ve E işaretlenip kuyruğun arkasına eklenir. Kuyruk artık [F, I, C, E]'dir: önde hâlâ seviye 1'in düğümleri, arkada seviye 2'nin düğümleri vardır. Kuyruk, seviyelerin karışmasını kendiliğinden önler.

Üçüncü turda F çıkar, G eklenir. Dördüncü turda I çıkar; tek komşusu A işaretli olduğu için kuyruğa bir şey eklenmez. Böylece seviye 1 biter. Beşinci turda C çıkar ve D'yi seviye 3 olarak ekler. E ile G çıkınca bütün komşuları işaretli bulunur. Sekizinci turda D, H'yi seviye 4 olarak ekler. H çıkınca kuyruk boşalır ve döngü biter.

Yazdırılan sıra A B F I C E G D H'dir. Seviyeler bu sırada ardışık bloklar hâlinde görülür: {A}, {B, F, I}, {C, E, G}, {D}, {H}. BFS ağacının kenarları A–B, A–F, A–I, B–C, B–E, F–G, C–D ve D–H'dir. Dokuz düğümlü bir ağaçta beklendiği gibi sekiz kenar vardır. Her düğüm kuyruğa bir kez girmiş, her komşu listesi bir kez taranmıştır; taranan toplam kayıt sayısı 2m = 22'dir.

14.3.5Derinlik öncelikli arama

Bir labirentte çıkış arayan biri genellikle şöyle davranır: bir koridora girer, sonuna kadar yürür. Çıkmaza girerse son yol ayrımına döner ve henüz denemediği bir koridora girer. Bu davranış DFS'nin ta kendisidir. DFS gidebildiği kadar derine iner. Ziyaret edilmemiş komşusu kalmayan bir düğüme gelince geri döner (backtracking) ve başka bir dalı dener.

Şekil 14.21'i Şekil 14.18 ile karşılaştıralım. Çizge aynıdır, ziyaret sıraları farklıdır. BFS s'den sonra a, b, c'yi, yani bütün komşuları ziyaret eder. DFS ise s'den a'ya, a'dan d'ye, d'den b'ye iner. b'nin bütün komşuları görülmüştür; DFS geri dönmek zorunda kalır. s'ye kadar geri çıkıp c'ye, oradan e'ye iner.

DFS'nin artıları şunlardır: bellekte yalnız o anki yol tutulur; geniş ama sığ çizgelerde BFS'den az bellek kullanır. Bir yolun sonuna kadar gitmek gereken problemlerde (labirent, oyun ağacı) doğal bir yöntemdir. Eksisi de açıktır: bulduğu yol en kısa yol olmak zorunda değildir. Şekil 14.21'de DFS b'ye s → a → d → b yoluyla, üç kenarla ulaşmıştır; oysa s–b kenarı doğrudan vardır. DFS'nin kullanıldığı başlıca yerler labirent çözme, döngü tespiti, bağlantılı bileşenleri bulma ve yönlü döngüsüz çizgelerde topolojik sıralamadır.

14.3.6DFS kodu: özyinelemeli ve açık yığınla

DFS'nin en kısa yazılışı özyinelemelidir.

void dfs(int v, boolean[] ziyaret) {
  ziyaret[v] = true;
  System.out.print(v + " ");
  for (int u : komsu.get(v))
    if (!ziyaret[u])
      dfs(u, ziyaret);
}

Metot önce v'yi işaretler ve yazdırır. Sonra v'nin komşularını sırayla dener; ziyaret edilmemiş ilk komşu için kendini çağırır. Bu çağrı dönmeden döngü devam etmez. Yani DFS, ilk komşunun altındaki her şeyi bitirmeden ikinci komşuya geçmez; “derine önce” davranışı buradan gelir. Komşuların hepsi denendiğinde metot döner ve çağıran düğüm kaldığı yerden devam eder. Bu dönüş, geri dönmenin kodda görünen biçimidir.

Özyineleme yığını bizim yerimize çağrı yığını ile tutar. Her etkin dfs çağrısı çağrı yığınında bir çerçevedir; çerçevelerin sırası, başlangıçtan o anki düğüme giden yoldur. Aynı algoritma açık bir yığınla da yazılabilir:

void dfsYigin(int s) {
  boolean[] ziyaret = new boolean[n];
  Deque<Integer> yigin = new ArrayDeque<>();
  yigin.push(s);  ziyaret[s] = true;
  while (!yigin.isEmpty()) {
    int v = yigin.peek();
    Integer yeni = null;
    for (int u : komsu.get(v))
      if (!ziyaret[u]) { yeni = u; break; }
    if (yeni == null) yigin.pop(); // geri
    else { ziyaret[yeni] = true;
           yigin.push(yeni); }
  }
}

Açık yığınlı sürüm özyinelemeyi adım adım taklit eder. Yığının üstü (peek) o anda bulunduğumuz düğümdür. Her turda üstteki düğümün ziyaret edilmemiş ilk komşusu aranır. Bulunursa işaretlenir ve yığına itilir; bu, özyinelemeli bir çağrıya karşılık gelir. Bulunamazsa (yeni == null) üstteki düğüm yığından çıkarılır; bu, bir çağrının dönmesine karşılık gelir. break önemlidir: ilk uygun komşu bulununca arama durur ve hemen o komşuya inilir.

Bu sürüm, derin çizgelerde özyinelemenin StackOverflowError vermesini önler. Java'nın çağrı yığını sınırlıdır; yüz binlerce düğümlü bir yol çizgesinde özyinelemeli DFS yığını taşırabilir. Açık yığın ise yığın belleğinde (heap) tutulur ve çok daha büyüyebilir.

Maliyet. Özyinelemeli sürümde her düğüm için dfs bir kez çağrılır ve o düğümün listesi bir kez gezilir: O(n + m). Açık yığınlı sürümde ise her peek turunda komşu listesi baştan taranır. Bir düğüm yığının üstüne birkaç kez geri geldiğinde listesinin başındaki işaretli komşular yeniden atlanır. Her düğüm yığının üstüne en çok derecesi kadar artı bir kez gelir; bu yüzden en kötü durumda tarama toplamı Σ deg(v)² mertebesine çıkabilir. Her liste için “nerede kaldım” bilgisi bir indis dizisinde tutulursa açık yığınlı sürüm de O(n + m) olur. Sunumdaki kod sadeliği öne çıkarır; küçük derecelerde bu fark önemsizdir.

14.3.7Kod izleme: özyinelemeli dfs(A)

Şekil 14.19'daki çizgede dfs(A, ziyaret) çağrısını izleyelim. Komşular yine alfabetik sıradadır.

Tablo, DFS'nin iki evresini açıkça gösterir. 1.–6. adımlarda algoritma hep ileri gider ve çağrı yığını her adımda bir çerçeve büyür: A → B → C → D → G → E. E'de bütün komşular işaretlidir; ilk geri dönüş burada olur. Geri dönen algoritma G'ye gelir ve G'nin listesinde kaldığı yerden devam eder: D ve E denenmiştir, sırada F vardır.

Dikkat edilecek bir nokta da şudur: bir düğüm döndükten sonra çağıran düğüm döngüsünü baştan değil, kaldığı yerden sürdürür. Örneğin 12. adımda C'ye dönülür; C'nin listesi B, D, E'dir ve sırada E kalmıştır. E ise G'nin altında zaten işaretlenmiştir. Her düğümün listesi tam bir kez gezilir.

Ziyaret sırası A B C D G E F H I'dır. DFS ağacının kenarları A–B, B–C, C–D, D–G, G–E, G–F, D–H ve A–I'dır. Çağrı yığınının en derin hâli altı çerçevedir. BFS ağacıyla karşılaştırıldığında DFS ağacı daha uzun ve daha ince bir yapıdadır: kökten E'ye BFS ağacında iki kenar, DFS ağacında beş kenar vardır.

14.3.8Kod izleme: dfsYigin(A)

Aynı çizgede açık yığınlı sürümü izleyelim. Her turda yığının üstüne bakılır, ziyaret edilmemiş ilk komşu aranır ve ya push ya da pop yapılır.

Döngü 17 tur döner: 8 push (A dışındaki sekiz düğüm) ve 9 pop (bütün düğümler). Push turları yeni bir düğümün ziyaret edildiği anlardır ve sıra A B C D G E F H I'dır; özyinelemeli sürümle tıpatıp aynıdır. Yığının her andaki içeriği de Tablo 14.11'deki çağrı yığınıyla aynıdır. İki kod aynı algoritmadır; yalnız yığını tutan taraf değişmiştir.

14.3.9BFS ile DFS'nin karşılaştırması

İkisi de O(n + m) zaman alır, çünkü her düğüm bir kez işlenir ve bütün komşuluk kayıtları bir kez taranır. Yönsüz çizgede her kenar iki listede göründüğü için taranan kayıt sayısı 2m'dir; sabit çarpan büyük-O gösteriminde düşer ve sonuç yine O(m)'dir.

Ek bellek ikisinde de en kötü durumda O(n)'dir, ama kötü durumlar farklıdır. BFS'yi zorlayan çizge geniştir: bir düğümün çok sayıda komşusu varsa hepsi aynı anda kuyruğa girer. DFS'yi zorlayan çizge derindir: uzun bir zincirde yığın zincirin boyu kadar büyür.

Tablodaki sıralar, komşuların alfabetik sırayla gezildiği varsayımıyla elde edilmiştir. Komşu listelerinin sırası değişirse ziyaret sırası da değişir; ama ziyaret edilen düğüm kümesi ve maliyet değişmez. Örneğin aynı çizgede H'den başlanırsa BFS H D C G B E F A I, DFS H D C B A F G E I sırasını verir. Bir başka gözlem de şudur: açık yığınlı DFS'deki yığın bir kuyrukla değiştirilirse ve komşuların hepsi birden eklenirse algoritma BFS'ye dönüşür. İki arama arasındaki fark, yardımcı yapının hangi ucundan okunduğudur.

14.3.10Bağlantılı bileşenler

Bağlantısız bir çizgede bir düğümden başlayan gezinme yalnız o düğümün bileşenini ziyaret eder. Bütün bileşenleri bulmak için gezinmeyi, henüz hiçbir bileşene atanmamış her düğümden yeniden başlatmak yeterlidir. Her yeni başlangıç yeni bir bileşen demektir.

int bilesenler(int[] bil) {
  Arrays.fill(bil, -1);
  int say = 0;
  for (int s = 0; s < n; s++)
    if (bil[s] == -1) dfs(s, say++, bil);
  return say;
}
void dfs(int v, int c, int[] bil) {
  bil[v] = c;
  for (int u : komsu.get(v))
    if (bil[u] == -1) dfs(u, c, bil);
}

bil dizisi her düğümün bileşen numarasını tutar. Başta bütün değerler −1'dir: “henüz atanmadı”. Bu dizi aynı zamanda ziyaret işareti görevi görür; ayrı bir boolean diziye gerek kalmaz. Dış döngü düğümleri 0'dan n − 1'e tarar. −1 değerli bir düğüm bulunca dfs(s, say++, bil) çağrılır. say++ sonradan artırma olduğu için çağrıya say'ın eski değeri gider; ilk bileşen 0 numarasını alır. dfs, ulaştığı her düğüme bileşen numarasını yazar.

dfs(0, 0)'ın içi şöyle yürür: 0 boyanır; 0'ın ilk komşusu 1 boyanır ve 1'in tek komşusu 0 zaten boyalı olduğu için 1'den dönülür. Sonra 0'ın ikinci komşusu 2 boyanır; onun da tek komşusu 0'dır. Metot sonunda 3 döndürür: çizgede üç bileşen vardır, {0, 1, 2}, {3, 4} ve {5}.

Maliyet O(n + m)'dir. Dış döngü n tur döner. Her düğüm tam bir kez boyanır ve listesi bir kez gezilir; her kenara iki ucundan birer kez bakılır. Bir kez hesaplanan bil dizisiyle “u ile v aynı bileşende mi?” sorusu bil[u] == bil[v] karşılaştırmasıyla O(1)'de yanıtlanır. Aynı soru her seferinde yeni bir gezinmeyle yanıtlansaydı her sorgu O(n + m) sürerdi.

14.3.11İki parçalı çizge testi

İki parçalı çizgeler eşleştirme problemlerinde doğal olarak ortaya çıkar. Öğrenciler bir grup, projeler öbür grup olsun; kenar “bu öğrenci bu projeyi istiyor” anlamına gelsin. Hiçbir kenar iki öğrenciyi ya da iki projeyi bağlamaz. İki vardiyalı çizelgeleme ve çakışmasız gruplama da aynı yapıdadır.

Grupları iki renk olarak düşünelim. Çizge iki parçalıysa her düğüme, komşularının hepsinin rengi kendisininkinden farklı olacak biçimde iki renkten biri verilebilir. Bunu BFS ile sınamak kolaydır: başlangıca 0 rengi verilir; her yeni keşfedilen düğüm, onu keşfeden düğümün zıt rengini alır. Daha önce boyanmış bir komşunun rengi şimdiki düğümün rengiyle aynıysa çizge iki parçalı değildir.

// renk[] = -1 ile başlar; s'den BFS
renk[s] = 0;  q.add(s);
while (!q.isEmpty()) {
  int w = q.poll();
  for (int u : komsu.get(w))
    if (renk[u] == -1) {
      renk[u] = 1 - renk[w];  q.add(u);
    } else if (renk[u] == renk[w]) return false;
}
return true;

renk dizisi −1 ile başlar; −1 “boyanmadı”, 0 ve 1 iki renktir. 1 - renk[w] ifadesi zıt rengi verir: 0'ın zıttı 1, 1'in zıttı 0'dır. Kod BFS'nin aynısıdır; tek fark, boyalı bir komşuda rengin denetlenmesidir.

Bu iki örnek genel bir kuralı yansıtır: bir çizgenin iki parçalı olması, tek uzunlukta döngü içermemesiyle eşdeğerdir. Bir döngü boyunca renkler 0, 1, 0, 1 diye değişir. Döngünün başladığı düğüme geri dönüldüğünde renk başlangıçtakiyle aynı olmalıdır; bu ancak döngünün kenar sayısı çiftse mümkündür. Örneğin 5 düğümlü döngü C₅ iki parçalı değildir, 6 düğümlü döngü C₆ ise iki parçalıdır. Testin maliyeti BFS'ninkiyle aynıdır: O(n + m). Çizge bağlantısızsa test, bileşenlerdeki gibi her boyanmamış düğümden yeniden başlatılır.

14.3.12Topolojik sıralama ve Kahn algoritması

Bir öğrencinin alacağı dersleri düşünelim. Bazı dersler başka derslerin ön koşuludur. Öğrenci dersleri öyle bir sırayla almalıdır ki her ders, ön koşullarının hepsinden sonra gelsin. Bu ilişki yönlü bir çizgedir: “u, v'nin ön koşulu” ise u → v oku vardır. Aranan sıraya topolojik sıra denir.

Döngülü bir çizgede neden topolojik sıra olamayacağı kolayca görülür. a → b → c → a döngüsü olsun. Sırada a, b'den; b, c'den; c de a'dan önce gelmelidir. Bu, a'nın kendisinden önce gelmesi demektir. Ders örneğinde her ders, döngüdeki bir başka dersin önce alınmasını bekler ve hiçbiri başlayamaz.

Topolojik sıra tek olmak zorunda değildir. Aynı anda hazır olan, yani ön koşulu kalmamış birden çok ders varsa bunlar herhangi bir sırayla alınabilir. Örneğin 0 → 1, 0 → 2, 1 → 3, 2 → 3 DAG'ında hem 0 1 2 3 hem de 0 2 1 3 geçerli sıralardır. Topolojik sıralama ders planlarında, görev bağımlılıklarında, derleme sırasının belirlenmesinde ve iş akışı planlamada kullanılır.

Kahn algoritmasının fikri basittir. Giriş derecesi 0 olan bir düğümün hiçbir ön koşulu yoktur; sırada ilk o gelebilir. Bu düğüm sıraya yazılınca ondan çıkan oklar “silinmiş” sayılır. Silinen her ok, hedefinin giriş derecesini bir azaltır. Giriş derecesi böylece 0'a düşen düğümler de hazır hâle gelir. Hazır düğümler bir kuyrukta bekletilir.

Kahn(G):
  q = girişDerecesi 0 olan düğümler
  sonuc = []
  while q boş değil:
    u = q'dan çıkar
    sonuc'a u ekle
    for u'dan çıkan her (u, v):
      girişDerecesi[v]--
      if girişDerecesi[v] == 0:
        q'ya v ekle
  if sonuc.size < n:
    döngü var
  return sonuc

List<Integer> kahn(List<List<Integer>> adj) {
  int n = adj.size();
  int[] giris = new int[n];
  for (List<Integer> l : adj)
    for (int v : l) giris[v]++;
  Queue<Integer> q = new ArrayDeque<>();
  for (int v = 0; v < n; v++)
    if (giris[v] == 0) q.add(v);
  List<Integer> sonuc = new ArrayList<>();
  while (!q.isEmpty()) {
    int u = q.poll();
    sonuc.add(u);
    for (int v : adj.get(u))
      if (--giris[v] == 0) q.add(v);
  }
  return sonuc;  // boyut < n → döngü
}

Java kodu üç evreden oluşur:

1. Sayma. İç içe iki döngü bütün listeleri gezer ve her okun hedefinin giris değerini bir artırır. Sonunda giris[v], v'nin giriş derecesidir. Bu evre O(n + m) sürer.
2. Başlatma. Giriş derecesi 0 olan bütün düğümler kuyruğa konur.
3. Ana döngü. Kuyruktan bir düğüm u çıkar ve sonuca eklenir. u'nun her okunun hedefi için --giris[v] yapılır. Ön ek azaltma önce azaltır, sonra yeni değeri verir; değer 0'a düşmüşse v kuyruğa eklenir.

Kuyruk boşaldığında sonuç listesinde n düğüm varsa bulunan sıra bir topolojik sıradır. n'den az düğüm varsa çizgede yönlü bir döngü vardır. Döngüdeki düğümlerin giriş dereceleri hiçbir zaman 0'a inmez, çünkü her biri döngüdeki bir önceki düğümü bekler. Algoritma bu düğümleri hiç kuyruğa koymaz.

14.3.13Kod izleme: kahn()

Altı dersli bir ön koşul çizgesi alalım. Oklar 0 → 3, 1 → 3, 1 → 4, 2 → 0, 2 → 4, 3 → 5, 4 → 5'tir. Komşu listeleri 0: [3] · 1: [3, 4] · 2: [0, 4] · 3: [5] · 4: [5] · 5: [] biçimindedir.

Sayma evresi. 0'ın listesi giris[3]'ü 1 yapar. 1'in listesi giris[3]'ü 2'ye, giris[4]'ü 1'e çıkarır. 2'nin listesi giris[0]'ı 1'e, giris[4]'ü 2'ye çıkarır. 3 ve 4'ün listeleri giris[5]'i 2'ye çıkarır. 5'in listesi boştur ve bir şey değiştirmez. Sonuç [1, 0, 0, 2, 2, 2]'dir. Giriş derecesi 0 olan 1 ve 2 kuyruğa girer.

İzlemede şu anlara dikkat etmek gerekir. 1 çıkınca 3 ve 4'ün giriş dereceleri azalır ama 0'a inmez: ikisi de hâlâ başka bir ön koşul bekler. 3, 0'ı; 4 ise 2'yi bekler. 2 çıkınca hem 0 hem 4 hazır olur. 0 çıkınca 3'ün son ön koşulu da tamamlanır. 5'in iki ön koşulu vardır (3 ve 4); 4 çıkınca giris[5] 1'e iner, 3 çıkınca 0 olur.

Sonuç 1 2 0 4 3 5'tir ve boyutu 6 = n'dir; çizgede döngü yoktur. Sıra gerçekten geçerlidir: her ok için kaynak hedeften önce gelir. Örneğin 2 → 0 okunda 2 ikinci, 0 üçüncü sıradadır. Her düğüm bir kez kuyruğa girmiş, her ok bir kez azaltılmıştır: maliyet O(n + m)'dir.

Topolojik sıralamanın bir başka yolu DFS'dir. DFS'de bir düğümün çağrısı, ondan ulaşılabilen her düğümün çağrısı bittikten sonra biter. Düğümler bitiş zamanlarına göre ters sırada dizilirse topolojik sıra elde edilir. Bu yöntemde döngü, bir sonraki kesimdeki geri kenar denetimiyle bulunur.

14.3.14Yönlü çizgede döngü tespiti

Yönsüz çizgede döngü bulmak görece kolaydır: DFS sırasında, ebeveyn dışında işaretli bir komşuya rastlamak döngü demektir. Yönlü çizgede ise işaretli bir düğüme ok gitmesi döngü için yeterli değildir. İşaretli düğümün o anki DFS yolunun üzerinde olup olmadığı önemlidir. Bu ayrımı yapmak için her düğüm üç renkten biriyle işaretlenir:

• beyaz (0): henüz ziyaret edilmedi;
• gri (1): ziyaret edildi ve şu anki DFS yolunun üzerinde; çağrısı henüz bitmedi;
• siyah (2): ziyaret edildi ve çağrısı bitti; ondan ulaşılabilen her şey incelendi.

// renk: 0 beyaz, 1 gri (yolda), 2 siyah
boolean donguVar(int v, int[] renk) {
  renk[v] = 1;
  for (int u : komsu.get(v)) {
    if (renk[u] == 1) return true;  // geri kenar
    if (renk[u] == 0 && donguVar(u, renk))
      return true;
  }
  renk[v] = 2;
  return false;
}

Bir okun hedefi gri ise, hedef düğümden şu anki düğüme bir yol vardır (DFS yolu boyunca). Bu yola okun kendisi eklenince döngü kapanır. Böyle bir oka geri kenar denir. Hedef siyah ise ondan şu anki düğüme dönen bir yol yoktur; olsaydı o düğümün çağrısı sırasında şu anki düğüm de ziyaret edilmiş olurdu. Siyah düğüme giden ok döngü kurmaz.

7. adım algoritmanın inceliğini gösterir. 3 → 2 okunda 2 daha önce ziyaret edilmiştir. Yalnız “ziyaret edildi mi?” diye bakan bir algoritma burada yanlışlıkla döngü ilan ederdi. Oysa 2'den 3'e dönen bir yol yoktur; 2 siyahtır, işi bitmiştir. 9. adımda ise 0 gridir: 0 → 3 → 4 yolu hâlâ çağrı yığınındadır ve 4 → 0 oku bu yolu kapatır. Bulunan döngü 0 → 3 → 4 → 0'dır. true değeri her düzeyde hemen döndürülür; geri kalan oklara bakılmaz.

Döngü tespitinin maliyeti DFS'ninkiyle aynıdır: her düğüm bir kez gri, bir kez siyah olur ve her ok bir kez incelenir. Çizge bağlantısızsa ya da 0'dan her düğüme ulaşılamıyorsa, donguVar beyaz kalan her düğümden yeniden çağrılır; toplam yine O(n + m)'dir.

14.4En kısa yol

Bir harita uygulaması iki nokta arasındaki en kısa güzergâhı, bir ağ yönlendiricisi bir paketin en hızlı yolunu, bir oyun karakteri hedefe giden en kısa rotayı arar. Bu soruların hepsi aynı çizge problemidir. Problemin iki sürümü vardır. Ağırlıksız çizgede yolun uzunluğu kenar sayısıdır ve problemi BFS çözer. Ağırlıklı çizgede uzunluk kenar ağırlıklarının toplamıdır ve problemi Dijkstra algoritması çözer.

14.4.1Ağırlıksız en kısa yol problemi

Ağırlıksız çizgede her kenarın ağırlığı 1 sayılır; yolun uzunluğu kenar sayısıdır. Bu durumda çözüm BFS'dir. BFS düğümleri seviye seviye keşfeder ve seviye k'deki bir düğümün uzaklığı tam olarak k'dir.

Şekil 14.28'de 7'ye iki en kısa yol vardır: 1 → 4 → 6 → 7 ve 1 → 3 → 8 → 7. İkisi de üç kenarlıdır. BFS bunlardan yalnız birini bulur; hangisini bulacağı komşu listelerinin sırasına bağlıdır. Uzunluk ise her durumda 3'tür. En kısa yol tek olmak zorunda değildir, ama en kısa uzunluk tektir.

14.4.2Algoritma ve kod

mesafe[tüm v] = ∞
mesafe[s] = 0
kuyruk.ekle(s)
while kuyruk boş değil:
  w = kuyruk.çıkar()
  for w'nin her komşusu u:
    if mesafe[u] == ∞:
      mesafe[u] = mesafe[w] + 1
      kuyruk.ekle(u)
return mesafe

Sözde kod BFS'nin küçük bir değişikliğidir. Ziyaret dizisinin yerini bir mesafe dizisi alır. “mesafe = ∞” aynı zamanda “ziyaret edilmedi” anlamına gelir; ayrı bir işaret dizisine gerek kalmaz. Bir düğüm ilk kez keşfedildiğinde mesafesi, onu keşfeden düğümün mesafesinin bir fazlası olarak yazılır. Teorem 14.2 bu ilk değerin doğru olduğunu söyler; değer bir daha değiştirilmez.

Map<Integer, Integer> enKisaYol(int s) {
  final int INF = Integer.MAX_VALUE;  // ∞
  Map<Integer, Integer> mesafe =
      new HashMap<>();
  for (int v : cizge.keySet())
    mesafe.put(v, INF);
  mesafe.put(s, 0);
  Queue<Integer> q = new ArrayDeque<>();
  q.offer(s);
  while (!q.isEmpty()) {
    int w = q.poll();
    for (int u : cizge.get(w))
      if (mesafe.get(u) == INF) {
        mesafe.put(u, mesafe.get(w) + 1);
        q.offer(u);
      }
  }
  return mesafe;
}

Java sürümünde çizge cizge adlı bir Map<Integer, List<Integer>> içinde tutulur: anahtar düğüm, değer onun komşu listesidir. Bu örnekte düğümler 1'den başlayarak numaralandığı için dizi yerine eşleme kullanılmıştır. Kod satır satır şunları yapar:

• INF, Integer.MAX_VALUE değeriyle ∞'u temsil eder.
• İlk döngü her düğümün mesafesini INF yapar; sonra kaynağın mesafesi 0 yapılır ve kaynak kuyruğa konur. offer, add ile aynı işi yapar; kuyruğun arkasına ekler.
• Ana döngü BFS'dir. Mesafesi hâlâ INF olan her komşu için mesafe mesafe.get(w) + 1 yapılır ve komşu kuyruğa eklenir.

Maliyet BFS'ninki gibidir: O(n + m). HashMap işlemleri ortalama O(1) kabul edilir.

14.4.3Kod izleme: enKisaYol(1)

Şekil 14.28'deki çizgede kaynak 1 olsun. Komşu listeleri küçükten büyüğe sıralıdır: 1: [2, 3, 4] · 2: [1, 5] · 3: [1, 8] · 4: [1, 6] · 5: [2, 8] · 6: [4, 7] · 7: [6, 8] · 8: [3, 5, 7].

İzlemenin üç noktası öğreticidir. Birincisi, 2 çıktığında komşusu 1'in mesafesi zaten 0'dır ve değişmez. BFS'de bir düğümün ilk bulunan mesafesi en kısadır; sonradan gelen hiçbir yol onu kısaltamaz. İkincisi, 5 çıktığında komşusu 8'in mesafesi 2'dir. 5 üzerinden 8'e gitmek 2 + 1 = 3 verirdi; bu daha uzundur ve kod ona bakmaz bile, çünkü 8'in mesafesi artık INF değildir.

Üçüncüsü, 7'nin mesafesini 8 yazmıştır. 8, kuyruğa 6'dan önce girmişti; bu yüzden 7'ye 6'dan önce o ulaşır. Bulunan yol 1 → 3 → 8 → 7'dir. Komşu sırası farklı olsaydı 1 → 4 → 6 → 7 bulunabilirdi; mesafe yine 3 olurdu. Son tabloda her düğümün mesafesi Şekil 14.28'deki değerlerle aynıdır.

Kod yalnız uzaklıkları verir, yolların kendisini vermez. Yolu da istemek için her düğümü ilk keşfeden düğüm bir onceki dizisinde saklanır. Dijkstra'da aynı yöntem kullanılır ve yolun hedeften geriye doğru nasıl kurulduğu 14.4.8'de ayrıntılı olarak izlenir.

14.4.4Ağırlıklı en kısa yol problemi

Ağırlıklı çizgede problem aynıdır: kaynaktan her düğüme en kısa yol aranır. Bu kez yolun uzunluğu kenar ağırlıklarının toplamıdır. Ağırlık uzaklık, süre ya da maliyet olabilir.

Çözüm, Edsger W. Dijkstra'nın 1956'da bulduğu ve 1959'da yayımladığı algoritmadır. Algoritmanın tek koşulu vardır: kenar ağırlıkları negatif olmamalıdır. Bu koşulun neden gerektiği algoritmanın doğruluk gerekçesinde görülür (14.4.9).

14.4.5Dijkstra algoritması: fikir ve sözde kod

Dijkstra algoritması, her düğüm için bir geçici mesafe tutar. Bu değer, o ana kadar bulunan en kısa yolun uzunluğudur ve başta kaynak için 0, öbür düğümler için ∞'dur. Algoritma her adımda şunları yapar:

1. Henüz kesinleşmemiş düğümler arasından geçici mesafesi en küçük olanı seçer. Bu düğümün mesafesi artık kesindir.
2. Seçilen düğümün komşularının mesafelerini gevşetme ile günceller.

“Gevşetme” adı, mesafe üst sınırının bir yay gibi gevşeyip küçülmesinden gelir. Geçici mesafe hiçbir zaman gerçek uzaklığın altına inmez; her gevşetme onu ya olduğu gibi bırakır ya da gerçek değere biraz daha yaklaştırır.

Dijkstra(G, s):
  for her düğüm v:
    mesafe[v] = ∞
    önceki[v] = tanımsız
  mesafe[s] = 0
  Q = tüm düğümler  // öncelikli kuyruk
  while Q boş değil:
    u = Q.çıkar()   // en küçük mesafe[u]
    for u'nun Q'daki her komşusu v:
      alt = mesafe[u] + ağırlık(u, v)
      if alt < mesafe[v]:
        mesafe[v] = alt
        önceki[v] = u
        // Q'da v'nin önceliğini azalt

Sözde kodda Q, kesinleşmemiş düğümlerin öncelikli kuyruğudur; öncelik, düğümün geçici mesafesidir. Q.çıkar() mesafesi en küçük düğümü verir. Bir düğümün mesafesi gevşetmeyle küçülünce kuyruktaki önceliği de küçültülmelidir. önceki[] dizisi her düğüm için en kısa yolda kendisinden önce gelen düğümü tutar; yol bu diziden geriye doğru okunarak kurulur.

14.4.6Dijkstra: Java

long[] dijkstra(List<List<int[]>> adj, int s, int[] onceki) { // ağırlıklar ≥ 0
    long[] d = new long[adj.size()];
    Arrays.fill(d, Long.MAX_VALUE);  d[s] = 0;  Arrays.fill(onceki, -1);
    PriorityQueue<long[]> pq =                     // {düğüm, mesafe}
        new PriorityQueue<>((a, b) -> Long.compare(a[1], b[1]));
    pq.add(new long[]{s, 0});
    while (!pq.isEmpty()) {
        long[] e = pq.poll();  int u = (int) e[0];
        if (e[1] > d[u]) continue;                   // bayat kayıt: atla
        for (int[] k : adj.get(u)) {
            int v = k[0];  long alt = d[u] + k[1];
            if (alt < d[v]) { d[v] = alt; onceki[v] = u; pq.add(new long[]{v, alt}); }
        }
    }
    return d;
}

Kodu parça parça inceleyelim:

• Girdi. adj.get(u), u'nun komşularını int[]{v, w} çiftleri olarak verir: komşu ve kenar ağırlığı. onceki dizisini çağıran metot ayırır; dijkstra onu doldurur.
• Başlangıç. d dizisi long türündedir ve Long.MAX_VALUE ile, yani ∞ ile doldurulur. d[s] = 0 yapılır, onceki −1 ile doldurulur; −1 “önceki yok” anlamındadır.
• Kuyruk. Kuyruğa {düğüm, mesafe} çiftleri girer. Karşılaştırıcı Long.compare(a[1], b[1]) mesafeye göre sıralar; poll en küçük mesafeli kaydı verir.
• Bayat kayıt denetimi. if (e[1] > d[u]) continue; satırı, kayıttaki mesafe düğümün güncel mesafesinden büyükse kaydı atlar.
• Gevşetme. Her komşu için alt = d[u] + k[1] hesaplanır. alt < d[v] ise mesafe ve onceki güncellenir, kuyruğa yeni bir {v, alt} kaydı eklenir.

Java'nın PriorityQueue sınıfında “önceliği azalt” işlemi yoktur. Sözde koddaki “Q'da v'nin önceliğini azalt” adımının yerine kod, v için yeni bir kayıt ekler. Eski kayıt kuyrukta kalır. Eski kayıt sonunda kuyruktan çıktığında, taşıdığı mesafe d[v]'den büyüktür, çünkü d[v] o arada küçülmüştür. Bu kayda bayat kayıt denir ve continue ile atlanır. Bu yönteme “tembel silme” de denir: eski kaydı hemen silmek yerine, çıktığında görmezden gelmek.

14.4.7Kod izleme: dijkstra(adj, A)

Gezinme örneklerindeki dokuz düğümlü çizgeye ağırlık verelim: A–B: 4, A–F: 7, A–I: 3, B–C: 1, B–E: 2, C–D: 7, C–E: 3, D–G: 3, D–H: 5, E–G: 2, F–G: 2. Çizge yönsüzdür; her kenar iki komşu listesinde de vardır. Kaynak A'dır.

Aşağıdaki tabloda her satır bir poll işlemidir. Kuyruk sütunu, o satırdaki gevşetmelerden sonra kuyrukta kalan kayıtları mesafeye göre sıralı gösterir.

İzlemenin kritik anı G'nin işlendiği satırdır. D'nin geçici mesafesi o ana kadar 12'dir; C üzerinden bulunmuştur (A → B → C → D: 4 + 1 + 7). G kesinleşince D–G kenarı gevşetilir: 8 + 3 = 11 < 12. D'nin mesafesi 11'e iner, onceki[D] = G olur ve kuyruğa {D, 11} eklenir. Eski {D, 12} kaydı kuyrukta kalır. Önce {D, 11} çıkar ve D kesinleşir. Hemen ardından {D, 12} çıkar; 12 > 11 olduğu için bayattır ve atlanır.

Bir başka gözlem: düğümler mesafe sırasıyla kesinleşir. Sıra A (0), I (3), B (4), C (5), E (6), F (7), G (8), D (11), H (16)'dır. Bu sıra Dijkstra'nın temel özelliğidir ve doğruluğunun da dayanağıdır. Toplam 10 poll, 10 ekleme (1 başlangıç ve 9 başarılı gevşetme) ve 22 gevşetme denemesi yapılmıştır; deneme sayısı 2m = 22'ye eşittir.

onceki dizisi en kısa yol ağacını tutar. H'den geriye doğru okunursa H ← D ← G ← E ← B ← A elde edilir. A'dan H'ye en kısa yol A → B → E → G → D → H'dir ve uzunluğu 4 + 2 + 2 + 3 + 5 = 16'dır. Bu yol beş kenarlıdır. A'dan H'ye en az kenarlı yollardan biri ise dört kenarlı A → F → G → D → H'dir; ama bu yolun uzunluğu 7 + 2 + 3 + 5 = 17'dir.

14.4.8Yolu geri kurma

Dijkstra'nın bıraktığı onceki dizisinden s'den t'ye yolu çıkarmak için t'den başlanır ve onceki zinciri −1'e kadar izlenir. Zincir hedeften kaynağa doğru ilerler; yol ise kaynaktan hedefe yazılmalıdır. Bu yüzden her düğüm listenin başına eklenir.

List<Integer> yol(int[] onceki, int s, int t) {
  LinkedList<Integer> y = new LinkedList<>();
  for (int v = t; v != -1; v = onceki[v])
    y.addFirst(v);
  if (y.getFirst() != s) return List.of();
  return y;                 // s ... t
}

Döngü v = t ile başlar, her turda v'yi listenin başına ekler ve v = onceki[v] ile bir adım geri gider. Kaynağın onceki değeri −1 olduğu için kaynak eklendikten sonra döngü biter. LinkedList.addFirst sabit sürelidir. Döngü, yoldaki düğüm sayısı kadar döner; maliyet O(yol uzunluğu)'dur ve en çok O(n)'dir.

Son satırdaki denetim ulaşılamayan hedefi yakalar. t'ye s'den ulaşılamıyorsa onceki[t] = −1 kalmıştır; zincir hemen biter ve listenin ilk öğesi t'nin kendisi olur. İlk öğe s değilse metot boş liste döndürür.

14.4.9Dijkstra'nın analizi ve doğruluğu

Zaman. İki gerçekleme yaygındır:

Heap'li sürümde her başarılı gevşetme kuyruğa bir kayıt ekler. Kuyrukta en çok m + 1 kayıt bulunur; her ekleme ve çıkarma O(log m)'dir. m ≤ n² olduğu için log m ≤ 2 log n'dir ve O(log m) = O(log n) yazılabilir. Toplam O((n + m) log n) eder.

Hangisinin seçileceği çizgeye bağlıdır. Seyrek çizgede (m ≈ n) heap'li sürüm O(n log n)'dir ve dizi taramasının O(n²)'sinden çok daha hızlıdır. Çok yoğun çizgede (m ≈ n²) heap'li sürüm O(n² log n)'ye çıkar; dizi taraması O(n²) ile daha iyi olabilir.

Kanıtın tek bir yerinde ağırlıkların negatif olmaması kullanılmıştır: “kalan kısmın uzunluğu ≥ 0”. Negatif bir kenar varsa, kesinleşmiş bir düğümün mesafesi sonradan negatif kenar üzerinden kısalabilir. Sözde koddaki Dijkstra bu durumda yanlış sonuç verir. Bayat kayıtlı Java sürümü bir düğümü yeniden işleyerek bazen doğru sonucu bulabilir, ama süre garantisi kaybolur; negatif ağırlıklı bir döngü varsa algoritma hiç bitmez. Negatif ağırlıklı çizgelerde Bellman-Ford algoritması kullanılır.

14.5Minimum kapsayan ağaç

Bir belediye, ilçedeki köylerin hepsine su götürmek istiyor. Her iki köy arasına boru döşemenin bir maliyeti var. Her köyün her köye doğrudan bağlanması gerekmez; suyun her köye bir yolla ulaşması yeterlidir. Toplam maliyeti en düşük boru ağı hangisidir? Bu soru, minimum kapsayan ağaç problemidir. Aynı problem elektrik ve iletişim ağlarının tasarımında, kümeleme yöntemlerinde ve başka algoritmaların alt adımı olarak karşımıza çıkar.

14.5.1Kapsayan ağaç ve MKA

Kapsayan ağaçta neden döngü istemiyoruz? Ağırlıklar pozitifse döngüdeki herhangi bir kenarı çıkarmak toplamı azaltır ve bağlantılılığı bozmaz: döngünün öbür kenarları iki ucu hâlâ birbirine bağlar. Bu yüzden en ucuz bağlantılı alt çizge her zaman döngüsüzdür, yani bir ağaçtır. n − 1 sayısı da 14.1.7'deki alt sınırdan gelir: n düğümü bağlamak için en az n − 1 kenar gerekir ve döngüsüz bağlantılı çizgede tam bu kadar kenar vardır.

Bu çizgenin kenar ağırlıklarının toplamı 62'dir. MKA ise yalnız dokuz kenar seçer ve toplamı 14'tür. Olası kapsayan ağaçların sayısı çok büyüktür; hepsini tek tek denemek pratik değildir. İki klasik algoritma, Kruskal ve Prim, MKA'yı açgözlü (greedy) bir yöntemle bulur: her adımda o an en iyi görünen seçimi yapar ve bu seçimden hiç geri dönmez. Açgözlü yöntemin bu problemde doğru sonuç vermesinin nedeni aşağıdaki özelliktir.

Kruskal ve Prim bu teoremin iki farklı kullanımıdır. Prim'de gruplardan biri o ana kadar kurulan ağaçtır. Kruskal'da ise seçilen kenarın iki ucunun ait olduğu ağaçlar ayrı gruplar olarak düşünülür.

14.5.2Ayrık kümeler (Union-Find)

Kruskal algoritması kenarları hafiften ağıra dener ve her kenar için aynı soruyu sorar: “Bu kenar, şimdiye kadar seçilenlerle bir döngü kurar mı?” Kenarın iki ucu seçilen kenarlarla zaten birbirine bağlıysa yeni kenar bir döngü kapatır. Bu soruyu hızlı yanıtlayan yapı ayrık kümeler (disjoint sets, union-find) yapısıdır.

Yapı, çakışmayan kümelerden oluşan bir aileyi iki işlemle yönetir:

• find(x): x'in kümesinin temsilcisini döndürür. İki öğe aynı kümedeyse find ikisi için aynı temsilciyi verir.
• union(u, v): u ile v farklı kümelerdeyse iki kümeyi birleştirir ve true döndürür. Zaten aynı kümedeyseler hiçbir şey yapmaz ve false döndürür.

Sunum yalnız bu iki işlemin davranışını kullanır; yapının iç ayrıntısını vermez. Aşağıdaki sınıf, sunumdaki izlemenin ebeveyn oklarını aynen üreten bir gerçeklemedir.

class UnionFind {
    private final int[] ebeveyn, boyut;
    UnionFind(int n) {                       // her düğüm kendi kümesi
        ebeveyn = new int[n];  boyut = new int[n];
        for (int i = 0; i < n; i++) { ebeveyn[i] = i; boyut[i] = 1; }
    }
    int find(int x) {                        // kökü bul, yolu kısalt
        if (ebeveyn[x] != x) ebeveyn[x] = find(ebeveyn[x]);
        return ebeveyn[x];
    }
    boolean union(int u, int v) {
        int a = find(u), b = find(v);
        if (a == b) return false;            // aynı küme: döngü kurar
        if (boyut[a] > boyut[b]) { int t = a; a = b; b = t; }
        ebeveyn[a] = b;  boyut[b] += boyut[a];  // küçük ağaç büyüğün altına
        return true;
    }
}

Her küme bir ağaç olarak tutulur. ebeveyn[x], x'in ağaçtaki ebeveynidir; kökün ebeveyni kendisidir ve kök, kümenin temsilcisidir. Başta her düğüm kendi kümesidir: n tane tek düğümlü ağaç vardır. İki iyileştirme yapının hızını belirler:

• Boyuta göre birleştirme. union, küçük ağacın kökünü büyük ağacın köküne bağlar. Böylece ağaçların yüksekliği en çok log n olur. Boyutlar eşitse u'nun kökü v'nin köküne bağlanır.
• Yol kısaltma (path compression). find kökü bulurken yol üzerindeki her düğümü doğrudan köke bağlar. Aynı düğüm bir daha sorulduğunda kök tek adımda bulunur.

İki iyileştirme birlikte kullanılınca bir dizi işlemin işlem başına maliyeti O(α(n)) olur. Buradaki α, ters Ackermann işlevidir ve son derece yavaş büyür. Evrendeki atom sayısı kadar büyük bir n için bile α(n) ≤ 4'tür. Pratikte find ve union sabit süreli kabul edilebilir.

14.5.3Kruskal algoritması

Kruskal(G):
  T = ∅          // seçilen kenarlar
  for her düğüm v: makeSet(v)
  kenarları ağırlığa göre sırala
  for her (u, v), küçükten büyüğe:
    if find(u) != find(v): // döngü yok
      T.ekle((u, v))
      union(u, v)
    if |T| == n − 1: break
  return T  // MST (bağlı değilse: orman)

Kruskal'ın kuralı tek cümledir: döngü oluşturmayan en hafif kenarı seç. Algoritma başta n ayrık küme ile başlar; her düğüm tek başına bir ağaçtır. Kenarlar ağırlığa göre küçükten büyüğe sıralanır ve sırayla denenir. Kenarın iki ucu farklı kümelerdeyse kenar T'ye eklenir ve iki küme birleşir. Aynı kümedeyse kenar bir döngü kapatır ve atlanır. n − 1 kenar seçilince ağaç tamamlanmıştır; kalan kenarlara bakılmaz.

Ara durumda seçilen kenarlar tek bir ağaç değil, birden çok ağaçtan oluşan bir ormandır. Ağaçlar algoritma ilerledikçe birleşir ve sonunda tek ağaç kalır. Çizge bağlantısızsa n − 1 kenara hiç ulaşılamaz. Bu durumda algoritma bütün kenarları dener ve her bağlantılı bileşen için bir ağaçtan oluşan minimum kapsayan ormanı döndürür.

Baskın terim sıralamadır. m ≤ n² olduğu için log m ≤ 2 log n'dir; bu yüzden O(m log m) = O(m log n) yazılır. Union-Find işlemleri neredeyse doğrusaldır ve toplamı değiştirmez. Döngü denetimi Union-Find yerine her kenar için bir DFS ile yapılsaydı, her denetim O(n) sürer ve toplam O(m · n)'ye çıkardı.

14.5.4Kruskal adım adım

Kruskal'ı Şekil 14.34'teki çizgede çalıştıralım. Eşit ağırlıklı kenarlar Şekil 14.34'ün altyazısındaki sırayla denenir.

C–J kenarının neden reddedildiğine bakalım. Daha önce C–I ve I–J kenarları seçilmiştir; C ile J, C–I–J yoluyla zaten bağlıdır. C–J eklenseydi C–I–J–C döngüsü oluşurdu. A–D de aynı nedenle reddedilir: A ile D, A–E–D yoluyla bağlıdır. B–C kabul edilince |T| = 9 = n − 1 olur ve algoritma durur. Toplam ağırlık 0 + 1 + 1 + 1 + 1 + 2 + 2 + 2 + 4 = 14'tür. C–H, G–I, A–B, D–F, H–I, F–G ve D–G kenarlarına, yani kalan yedi kenara hiç bakılmaz.

14.5.5Kod izleme: kruskal() ve Union-Find

List<int[]> kruskal(int n, List<int[]> E) {
  E.sort((a, b) ->          // {u, v, w}
      Integer.compare(a[2], b[2]));
  UnionFind uf = new UnionFind(n);
  List<int[]> T = new ArrayList<>();
  for (int[] e : E) {
    if (uf.union(e[0], e[1]))  // döngüsüz
      T.add(e);
    if (T.size() == n - 1) break;
  }
  return T;
}

Kod, sözde kodun doğrudan karşılığıdır. Kenarlar {u, v, w} dizileri olarak verilir. E.sort kenarları üçüncü öğeye, yani ağırlığa göre sıralar. Java'nın nesne listelerini sıralama yöntemi kararlıdır: eşit ağırlıklı kenarlar girdideki sıralarını korur. uf.union(e[0], e[1]) hem döngü denetimini hem birleştirmeyi tek çağrıda yapar: true dönerse kenar eklenir. |T| = n − 1 olunca döngü break ile kesilir.

Union-Find'ın içini izlemek için düğümleri A = 0, …, J = 9 diye numaralayalım. Aşağıdaki tabloda “bağlanan” sütunu, union içinde hangi kökün hangi köke bağlandığını gösterir.

Tablodaki iki an özellikle öğreticidir. C–J denendiğinde find(C), C → J okunu izleyip J'yi; find(J) doğrudan J'yi verir. Kökler aynıdır, union false döndürür ve kenar atlanır. Son adımda find(B), B → D → E yolunu izler ve yol kısaltma B'yi doğrudan E'ye bağlar. Sonra J'nin ağacı (3 düğüm) E'nin ağacının (7 düğüm) altına girer. Son ormanda tek kök E'dir; I ve C, J üzerinden, G ise H üzerinden E'ye ulaşır.

return T dokuz kenar döndürür; toplam ağırlık 14'tür. On sekiz kenardan on biri denenmiş, yedisine hiç bakılmamıştır. Sıralama yine de on sekiz kenarın hepsini kapsar; algoritmanın baskın maliyeti budur.

14.5.6İkinci örnek: havalimanları

Goodrich, Tamassia ve Goldwasser'in kitabındaki örnekte dokuz ABD havalimanı ve aralarındaki 19 uçuş hattı vardır; ağırlıklar mil cinsinden uzaklıklardır. Bütün havalimanlarını en kısa toplam hat uzunluğuyla birbirine bağlayan ağ aranıyor.

Toplam 144 + 184 + 187 + 337 + 621 + 802 + 946 + 1235 = 4456 mildir. On üç hat denenmiş, en uzun altı hat (1258, 1391, 1464, 1846, 2342, 2704) hiç denenmemiştir. Örnek, algoritmanın davranışını iyi gösterir: kısa hatlar önce birbirine yakın havalimanlarını gruplar; uzun hatlar yalnız gruplar arasında köprü gerektiğinde seçilir. LAX–DFW, batı grubu ile doğu grubu arasındaki en kısa köprüdür; kesim özelliğine göre MKA'da bulunmak zorundadır.

14.5.7Prim algoritması

Prim(G, s):
  ağaç = {s}, T = ∅
  s'nin kenarlarını kuyruğa ekle
  while |T| < n − 1:
    (u, v) = en hafif kenar  // u ağaçta
    if v ağaçta: atla        // döngü
    v'yi ağaca, (u, v)'yi T'ye ekle
    v'nin dışarı giden kenarlarını
      kuyruğa ekle
  return T

Prim algoritması Kruskal'dan farklı bir yol izler. Ağaç tek bir düğümle başlar ve her adımda bir düğüm büyür. Her adımda, ağaçtaki bir düğümü ağaç dışındaki bir düğüme bağlayan kenarların en hafifi seçilir. Kesim özelliği bu seçimin güvenli olduğunu söyler: ağaç ile dışarısı iki gruptur; ağaç dışarıya bir yolla bağlanmak zorundadır ve seçilen kenar bu bağlantıların en ucuzudur.

Prim'in Dijkstra'ya benzerliği dikkat çekicidir. İkisi de bir düğümden başlar, bir öncelikli kuyruk kullanır ve her adımda kuyruktan en küçük öğeyi alır. Fark kuyruğun anahtarındadır. Dijkstra'da anahtar düğümün kaynağa toplam uzaklığıdır. Prim'de anahtar, düğümü ağaca bağlayan tek kenarın ağırlığıdır. Kruskal'dan farkı ise ara durumdadır: Prim'de her an tek bir ağaç vardır. Bir kenarın döngü kurup kurmadığını anlamak için “hedef düğüm zaten ağaçta mı?” sorusu yeterlidir; Union-Find gerekmez.

14.5.8Prim: Java

Sunumdaki Java sürümü öncelikli kuyrukla yazılmış tembel sürümdür.

List<int[]> prim(List<List<int[]>> adj, int s) {
  int n = adj.size();                 // adj.get(u): {v, w}
  boolean[] agacta = new boolean[n];
  PriorityQueue<int[]> pq = new PriorityQueue<>(
      (a, b) -> Integer.compare(a[2], b[2]));  // {u, v, w}
  List<int[]> T = new ArrayList<>();
  agacta[s] = true;
  for (int[] e : adj.get(s)) pq.add(new int[]{s, e[0], e[1]});
  while (!pq.isEmpty() && T.size() < n - 1) {
    int[] e = pq.poll();               // en hafif aday
    if (agacta[e[1]]) continue;       // bayat: döngü kurar
    agacta[e[1]] = true;
    T.add(e);
    for (int[] f : adj.get(e[1]))
      if (!agacta[f[0]]) pq.add(new int[]{e[1], f[0], f[1]});
  }
  return T;
}

Kuyrukta {u, v, w} kayıtları bulunur: u ağaçtaki uç, v aday düğüm, w kenarın ağırlığıdır. Karşılaştırıcı yalnız ağırlığa bakar. agacta dizisi hangi düğümlerin ağaca girdiğini tutar. Kod şu adımları izler:

1. Başlangıç düğümü s ağaca konur; s'nin bütün kenarları kuyruğa eklenir.
2. Döngü, kuyruk boşalana ya da n − 1 kenar seçilene kadar sürer. Her turda en hafif kayıt alınır.
3. Kaydın aday ucu e[1] zaten ağaçtaysa kayıt bayattır: bu kenar iki ağaç düğümünü bağlar ve döngü kurar. continue ile atlanır.
4. Değilse aday ağaca alınır, kenar T'ye eklenir. Yeni düğümün ağaç dışına giden bütün kenarları kuyruğa eklenir.

“Tembel” sözcüğü bayat kayıtların ele alınış biçimini anlatır. v ağaca girdiğinde, v'ye giden ve kuyrukta bekleyen eski kayıtlar silinmez; kuyruktan çıktıklarında atlanırlar. Dijkstra'daki bayat kayıt yöntemiyle aynı fikirdir.

Maliyet. Her kenar en çok iki kez kuyruğa girer, her ucundan bir kez. Kuyrukta en çok 2m ekleme ve 2m çıkarma yapılır; her biri O(log m)'dir. Toplam O(m log m) = O(m log n), ek bellek ise kuyruk için O(m)'dir. Komşuluk matrisiyle ve kuyruksuz, dizi taramalı bir sürümle Prim O(n²)'de çalışır; çok yoğun çizgelerde bu sürüm daha iyidir.

14.5.9Prim adım adım

Prim'i Şekil 14.34'teki çizgede A'dan başlatalım. Elle çalıştırırken eşit ağırlıklı kayıtlar alfabetik sırayla alınsın: önce ağaçtaki uç, sonra aday uç alfabeye göre karşılaştırılır.

3. adımda D ağaca girer. Bu anda kuyruktaki A–D 4 ve F–D 5 kayıtları bayatlamıştır: ikisinin de iki ucu ağaçtadır. Kuyruktan hemen silinmezler. 7. adımda en hafif kayıtlar dörder ağırlıklıdır ve alfabetik sırada önce A–D gelir; A–D bayat olduğu için atlanır, ardından B–C seçilir. 9. adımda J ağaca girer, n − 1 = 9 kenar seçilmiştir ve algoritma durur. Kuyrukta hâlâ sekiz kayıt vardır; bunlara bakılmaz.

Prim ağacı A–E, E–F, E–D, D–B, D–H, H–G, B–C, C–I, I–J'dir. Kenar kümesi Kruskal'ınkiyle aynıdır, yalnız kenarlar farklı sırada seçilmiştir. Kruskal işe ağırlığı 0 olan I–J ile başlamıştı; Prim bu kenarı ancak en son, I ağaca girdikten sonra görebilir.

Alfabetik sıra elle izleme için seçilmiş bir kuraldır. Sunumdaki Java kodu eşit ağırlıklı kayıtları PriorityQueue'nun iç düzenine göre çıkarır ve bu düzen hiçbir sıra garantisi vermez. Kodun eşit ağırlıklarda hangi kaydı önce çıkaracağı, kayıtların kuyruğa hangi sırayla girdiğine, dolayısıyla komşu listelerinin sırasına bağlıdır. Kod bu çizgede çalıştırıldığında komşu listeleri alfabetik sıralıysa 7. adımda B–C yerine G–I seçilir, ardından I–J ve I–C gelir; ağaç A–E, E–F, E–D, D–B, D–H, H–G, G–I, I–J, I–C olur. Kenarlar listelere Şekil 14.34'ün altyazısındaki sırayla eklenmişse 7. adımda H–C seçilir. Bu ağaçların her biri bir MKA'dır ve toplamları yine 14'tür. Eşit ağırlıklı kenarlar varsa birden çok MKA olabilir; toplam ağırlık ise her zaman aynıdır.

14.5.10Kruskal ile Prim'in karşılaştırması

İki algoritma da açgözlüdür ve kesim özelliğine dayanır. Aynı çizgede aynı toplam ağırlığı bulurlar; örneğimizde ikisi de 14'tür. Eşit ağırlıklı kenarlar varsa buldukları ağaçlar farklı olabilir. Seçim, verinin elde hangi biçimde olduğuna da bağlıdır. Kenarlar bir dosyadan liste olarak okunuyorsa Kruskal doğaldır. Çizge zaten komşuluk listesiyle tutuluyorsa ve bir düğümden başlamak anlamlıysa Prim doğaldır.

14.6Özet

• Çizge G = (V, E), düğümler ve onları bağlayan kenarlardan oluşur; n düğüm, m kenar sayısıdır. Ağaçtan farklı olarak kökü yoktur, döngü içerebilir ve bir düğüme birden çok yoldan ulaşılabilir. Kenarlar yönlü ya da yönsüz, ağırlıklı ya da ağırlıksız olabilir.
• Derece bir düğüme bağlı kenar sayısıdır. El sıkışma lemmasına göre Σ deg(v) = 2m'dir; yönlü çizgede giriş ve çıkış derecelerinin toplamlarının ikisi de m'dir. Basit yönsüz çizgede m ≤ n(n − 1)/2, bağlantılı çizgede m ≥ n − 1'dir.
• Yol kenarlarla bağlı düğüm dizisi, döngü aynı düğümde başlayıp biten yoldur. Her iki düğümü arasında yol olan çizge bağlantılıdır; birbirine ulaşabilen düğümlerin en büyük grubu bir bağlantılı bileşendir.
• Komşuluk matrisi O(n²) bellek kullanır; kenar sorgusu O(1), komşuları gezmek O(n)'dir. Komşuluk listesi O(n + m) bellek kullanır; komşuları gezmek O(deg v)'dir. Seyrek çizgede liste, yoğun çizgede ve sık kenar sorgusunda matris seçilir.
• BFS kuyrukla seviye seviye, DFS yığınla ya da özyinelemeyle derine doğru ilerler. İkisi de komşuluk listesiyle O(n + m)'dir. Düğüm kuyruğa ya da yığına girerken işaretlenir; işaret olmadan gezinme döngülerde sonsuza kadar döner.
• Üç uygulama bu gezinmelerin üzerine kurulur. Bağlantılı bileşenler, boyanmamış her düğümden yeni bir gezinme başlatılarak bulunur. İki parçalılık testi BFS ile 2-renklemedir; tek uzunlukta döngü yoksa çizge iki parçalıdır. Yönlü döngü tespiti üç renkli DFS'dir; gri düğüme giden ok bir geri kenardır.
• Topolojik sıralama yalnız DAG'lerde vardır. Kahn algoritması giriş derecesi 0 olan düğümleri kuyruktan sırayla çıkarır ve oklarını siler; sonuçta n'den az düğüm varsa döngü vardır. Maliyet O(n + m)'dir.
• Ağırlıksız en kısa yolu BFS bulur: ilk bulunan mesafe en kısadır. Ağırlıklı en kısa yolu, ağırlıklar negatif değilse Dijkstra bulur: mesafesi en küçük kesinleşmemiş düğümü seçer ve komşularını gevşetir. Heap ile O((n + m) log n), dizi taramasıyla O(n²)'dir. Yol, onceki dizisinden hedeften geriye okunarak kurulur.
• Minimum kapsayan ağaç, bütün düğümleri en düşük toplam ağırlıkla bağlayan n − 1 kenarlı ağaçtır. Kruskal kenarları sıralayıp döngü kurmayanları Union-Find ile seçer; Prim tek ağacı her adımda en hafif dış kenarla büyütür. İkisi de O(m log n)'dir ve kesim özelliğine dayanır.

Tablo, bölümün ortak dersini de özetler: veri yapısı algoritmanın davranışını belirler. Aynı gezinme iskeleti kuyrukla BFS, yığınla DFS, mesafeye göre sıralı öncelikli kuyrukla Dijkstra, kenar ağırlığına göre sıralı öncelikli kuyrukla Prim olur.

14.7Kavram listesi

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

• çizge graph
• düğüm vertex, node
• kenar edge
• komşu adjacent
• derece degree
• giriş derecesi in-degree
• çıkış derecesi out-degree
• yönlü çizge directed graph (digraph)
• ağırlıklı çizge weighted graph
• yol path
• döngü cycle
• bağlantılı bileşen connected component
• tam çizge complete graph
• kenar listesi edge list
• komşuluk listesi adjacency list
• komşuluk matrisi adjacency matrix
• gezinme traversal
• genişlik öncelikli arama breadth-first search (BFS)
• derinlik öncelikli arama depth-first search (DFS)
• iki parçalı çizge bipartite graph
• yönlü döngüsüz çizge directed acyclic graph (DAG)
• topolojik sıralama topological sort
• gevşetme relaxation
• öncelikli kuyruk priority queue
• kapsayan ağaç spanning tree
• minimum kapsayan ağaç minimum spanning tree (MST)
• ayrık kümeler disjoint sets (union-find)
• yol kısaltma path compression
• Kruskal algoritması Kruskal's algorithm
• Prim algoritması Prim's algorithm

14.8Kendini Dene

1. 8 düğümlü basit, yönsüz ve bağlantılı bir çizgede en az ve en çok kaç kenar bulunabilir?

   Cevap

   En az n − 1 = 7 kenar (bu durumda çizge bir ağaçtır), en çok n(n − 1)/2 = 8 · 7 / 2 = 28 kenar (tam çizge K₈).

2. Okları 0 → 1, 0 → 2, 2 → 1, 3 → 0 olan yönlü çizgenin komşuluk matrisinde kaç hücre 1'dir? 0'ın çıkış derecesi ve 1'in giriş derecesi matristen nasıl okunur?

   Cevap

   Her ok bir hücre doldurur: 4 hücre 1'dir. 0'ın çıkış derecesi 0. satırın toplamıdır: m[0][1] + m[0][2] = 2. 1'in giriş derecesi 1. sütunun toplamıdır: m[0][1] + m[2][1] = 2.

3. Gezinme örneklerindeki dokuz düğümlü çizgede (komşular alfabetik) bfs(E) hangi sırayı yazdırır? A, E'den kaç kenar uzaktadır?

   Cevap

   Sıra E B C G A D F I H'dir. E'nin komşuları B, C, G seviye 1'dir; B'den A, C'den D, G'den F seviye 2'ye girer; A'dan I ve D'den H seviye 3'tür. A seviye 2'dedir: E'den 2 kenar uzaktadır (E → B → A).

4. Aynı çizgede özyinelemeli dfs(F) hangi sırayı yazdırır?

   Cevap

   F A B C D G E H I. F'nin ilk komşusu A, A'nın ilk ziyaret edilmemiş komşusu B, sonra C, D, G'ye inilir. G'nin komşusu E ziyaret edilir. E'den ve G'den geri dönülür; D'nin altında H ziyaret edilir. En sonda A'ya dönülünce A'nın son komşusu I ziyaret edilir.

5. Komşu listeleri 0: [1, 2] · 1: [4] · 2: [4] · 3: [1] · 4: [] olan DAG için kahn() hangi sırayı döndürür?

   Cevap

   Giriş dereceleri [0, 2, 1, 0, 2]'dir; kuyruk 0, 3 ile başlar. 0 çıkar: giris[1] = 1, giris[2] = 0 ve 2 kuyruğa girer. 3 çıkar: giris[1] = 0 ve 1 girer. 2 çıkar: giris[4] = 1. 1 çıkar: giris[4] = 0 ve 4 girer. Sonuç 0 3 2 1 4'tür; boyut 5 = n, döngü yok.

6. Okları 0 → 1, 1 → 2, 2 → 3, 3 → 1 olan çizgede donguVar(0, renk) hangi oku incelerken true döndürür? O anda renk dizisi nedir?

   Cevap

   0, 1, 2, 3 sırayla gri olur: renk = [1, 1, 1, 1]. 3 → 1 oku incelenirken 1 gridir, yani şu anki yolun üzerindedir. Bu bir geri kenardır; bulunan döngü 1 → 2 → 3 → 1'dir.

7. Yönsüz kenarları A–B 1, A–C 4, B–C 2, B–D 6, C–D 3 olan çizgede Java Dijkstra A'dan çalıştırılırsa son d ve onceki değerleri ne olur? Kuyruktan kaç bayat kayıt çıkar?

   Cevap

   d = [0, 1, 3, 6] (A, B, C, D) ve onceki = [–, A, B, C]. A işlenince C 4, B 1 olur. B işlenince C 3'e iner ({C, 3} eklenir) ve D 7 olur. C işlenince D 6'ya iner ({D, 6} eklenir). Eski {C, 4} ve {D, 7} kayıtları bayat olarak çıkar ve atlanır: 2 bayat kayıt.

8. Kenarları A–B 3, A–C 1, B–C 3, B–D 2, C–D 4, C–E 5, D–E 6 olan çizgede Kruskal'ın seçtiği kenarlar ve toplam ağırlık nedir? Eşit ağırlıklı A–B ile B–C'nin deneme sırası değişirse ne olur?

   Cevap

   Sıra A–C 1 (kabul), B–D 2 (kabul), A–B 3 (kabul: {A, C} ile {B, D} birleşir), B–C 3 (ret), C–D 4 (ret), C–E 5 (kabul). Dört kenar seçilmiştir, D–E'ye bakılmaz. Toplam 1 + 2 + 3 + 5 = 11'dir. B–C önce denenirse B–C kabul, A–B ret olur. Ağaç farklıdır (A–C, B–D, B–C, C–E), toplam yine 11'dir.

9. Bir önceki sorudaki çizgede tembel Prim A'dan başlatılırsa (eşitlikte alfabetik sıra) kenarlar hangi sırayla seçilir ve kaç bayat kayıt atlanır?

   Cevap

   A–C 1, A–B 3, B–D 2, C–E 5. A–B seçildikten sonra kuyrukta C–B 3 kalır; B ağaçta olduğu için bu kayıt bayattır. D girince C–D 4 de bayatlar. C–E'den önce bu iki kayıt çıkar ve atlanır: 2 bayat kayıt. Toplam yine 11'dir.

10. Bütün kenarlarının ağırlığı 5 olan bir çizgede tek kaynaklı en kısa yollar için Dijkstra yerine hangi algoritma kullanılabilir? Neden?

    Cevap

    BFS. Bütün ağırlıklar eşit olduğunda bir yolun uzunluğu 5 × kenar sayısı'dır; en az kenarlı yol aynı zamanda en kısa yoldur. BFS'nin bulduğu mesafeler 5 ile çarpılır. BFS O(n + m)'dir; heap'li Dijkstra'nın log n çarpanından kurtulunur.

14.9İleri okuma

• M. T. Goodrich, R. Tamassia ve M. H. Goldwasser, Data Structures and Algorithms in Java (6. baskı, 2014), Bölüm 14: çizge ADT'sini, gösterimleri, DFS ve BFS'yi, topolojik sıralamayı, Dijkstra'yı, Kruskal ve Prim'i Java koduyla anlatır; havalimanı örneği bu bölümdendir.
• R. Sedgewick ve K. Wayne, Algorithms (4. baskı, 2011), Bölüm 4: yönsüz ve yönlü çizgeleri, MKA'yı ve en kısa yolları ayrı kesimlerde işler; tembel ve istekli Prim sürümlerini karşılaştırır.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms (4. baskı, 2022), Bölüm 20–22: BFS ve DFS'nin doğruluk kanıtlarını, kesim özelliğini ve Bellman-Ford algoritmasını biçimsel bir dille verir; ayrık kümeler yapısının analizi Bölüm 19'dadır.

14.10Kaynaklar

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022.
2. E. W. Dijkstra, “A note on two problems in connexion with graphs”, Numerische Mathematik, 1, 269–271, 1959.
3. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6. baskı, Wiley, 2014.
4. A. B. Kahn, “Topological sorting of large networks”, Communications of the ACM, 5(11), 558–562, 1962.
5. J. B. Kruskal, “On the shortest spanning subtree of a graph and the traveling salesman problem”, Proceedings of the American Mathematical Society, 7(1), 48–50, 1956.
6. R. C. Prim, “Shortest connection networks and some generalizations”, Bell System Technical Journal, 36(6), 1389–1401, 1957.
7. R. Sedgewick, K. Wayne, Algorithms, 4. baskı, Addison-Wesley, 2011.

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