Bölüm 4.1: Çizge Gezinme Algoritmaları

4.1.1Çizgeler ve gösterimleri

Dünyadaki pek çok düzen bir ağ gibidir. Şehirler yollarla, insanlar tanışıklıklarla, bilgisayarlar kablolarla birbirine bağlanır. Bu ağların ortak yanı, birkaç nesne ve bu nesnelerin bazı çiftleri arasındaki bağlantılardır. Nesnelerin ne olduğu ya da bağlantının fiziksel mi, mantıksal mı olduğu önemli değildir. Matematikte bu ortak yapıya çizge denir. Çizge algoritmaları da bu ağlar üzerinde sorulan soruları yanıtlar: İki şehir arasında yol var mı? En kısa yol hangisi? Ağ hangi gruplara ayrılır? Bir kablo koparsa ağ ikiye bölünür mü?

4.1.1.1Çizge nedir?

Algoritmaların maliyeti çizgenin iki büyüklüğüne bağlıdır. Bu notta V harfi hem düğüm kümesini hem de düğüm sayısını, E harfi de hem kenar kümesini hem de kenar sayısını gösterir. Hangisinin kastedildiği bağlamdan anlaşılır. Karmaşıklıklar bu iki sayı cinsinden yazılır: O(V + E), O(V²) gibi. Tek bir n yerine iki ayrı sayı kullanılmasının nedeni, aynı düğüm sayısında kenar sayısının çok farklı olabilmesidir. On düğümlü bir çizgede hiç kenar olmayabilir, ama kırk beş kenar da olabilir.

Şekil 4.1.1 küçük bir yol ağını gösterir. Ordu'dan Erzurum'a gitmek için Ordu–Giresun–Trabzon–Erzurum ya da Ordu–Samsun–Sivas–Erzurum gibi birkaç yol izlenebilir. Bir düğümden başlayıp her adımda bir kenar boyunca komşuya geçerek oluşturulan düğüm dizisine yol (path) denir. Yolun uzunluğu, içerdiği kenar sayısıdır; Ordu–Giresun–Trabzon–Erzurum yolunun uzunluğu 3'tür. Başladığı düğüme geri dönen ve kenar tekrarlamayan yola döngü (cycle) denir. Şekildeki Ordu–Giresun–Sivas–Samsun–Ordu dizisi bir döngüdür.

Bir düğüme bağlı kenar sayısına o düğümün derecesi (degree) denir. Şekilde Giresun'un derecesi 3'tür (Ordu, Trabzon, Sivas), Samsun'unki 2'dir. Derecelerin toplamı her zaman kenar sayısının iki katıdır, çünkü her kenar iki ucundaki düğümün derecesine birer katkı yapar. Şekilde dereceler 2, 3, 2, 2, 3, 2'dir; toplamları 14 = 2 · 7 eder. Bu basit gözlem, gezinme algoritmalarının maliyet hesabında doğrudan kullanılacak: komşu listelerinin toplam uzunluğu yönsüz bir çizgede 2E'dir.

Herhangi iki düğümü arasında bir yol bulunan çizgeye bağlı (connected) çizge denir. Şekildeki ağ bağlıdır: her şehirden her şehre gidilebilir. Bağlı olmayan bir çizge, kendi içinde bağlı olan ve birbirine hiç kenarla bağlanmayan parçalara ayrılır. Bu parçaların her birine bağlı bileşen (connected component) denir.

4.1.1.2Çizge türleri

Kenarların bir yönü, bir ağırlığı ya da özel bir düzeni olabilir. Bu özellikler hangi algoritmanın kullanılacağını belirler. Şekil 4.1.2 en sık karşılaşılan sekiz türü küçük örneklerle gösterir.

• Yönlü çizge (directed graph): Her kenarın bir başlangıcı ve bir bitişi vardır; kenar yalnız ok yönünde geçilir. u → v kenarı u'dan v'ye gitmeyi sağlar, ama tersini sağlamaz. Tek yönlü sokaklar, bir web sayfasından ötekine verilen bağlantılar ve “A görevi B'den önce bitmeli” türünden bağımlılıklar yönlü çizgedir. Yönlü çizgede bir düğüme giren kenar sayısına giriş derecesi, düğümden çıkan kenar sayısına çıkış derecesi denir.
• Yönsüz çizge (undirected graph): Kenarlar iki yönde de geçilir. Arkadaşlık ilişkisi simetrik olduğu için bir sosyal ağ yönsüz çizgeyle anlatılır. Yönsüz bir kenar, iki yönlü iki kenar gibi düşünülebilir; bellekte de çoğu zaman böyle tutulur.
• Ağırlıklı çizge (weighted graph): Her kenara bir sayı atanır. Bu sayı bir uzaklık, süre, maliyet ya da kapasite olabilir. Yol ağında kilometreler, bilgisayar ağında gecikme süreleri ağırlıktır. Ağırlıklı çizgede bir yolun uzunluğu kenar sayısıyla değil, ağırlıkların toplamıyla ölçülür.
• İki parçalı çizge (bipartite graph): Düğümler iki kümeye ayrılabilir ve her kenar farklı kümelerdeki iki düğümü bağlar; aynı kümedeki iki düğüm arasında kenar yoktur. Öğrenciler ile dersler, işçiler ile işler arasındaki eşleştirmeler bu yapıdadır.
• Döngülü çizge (cyclic graph): En az bir döngü içerir. Şekildeki örnekte A–D–C–B–A, başladığı yere dönen bir yoldur. Döngü içermeyen çizgeye döngüsüz (acyclic) denir. Döngüsüz yönlü çizgeler (directed acyclic graph, DAG) görev planlamada özel bir yer tutar.
• Ağaç (tree): Bağlı ve döngüsüz yönsüz çizgedir. Ağaçta herhangi iki düğüm arasında tam bir yol vardır ve V düğümlü bir ağacın kenar sayısı her zaman V − 1'dir. İkili arama ağacı, öbek ve dosya sistemi dizinleri bu yapının bilinen örnekleridir.
• Tam çizge (complete graph): Her düğüm çifti bir kenarla bağlıdır. n düğümlü tam çizgede n(n − 1)/2 kenar vardır. Her düğüm öteki n − 1 düğüme bağlanır; her kenar böylece iki kez sayıldığı için toplam ikiye bölünür. Dört düğümde 4 · 3/2 = 6, on düğümde 10 · 9/2 = 45 kenar eder. Yönsüz basit bir çizgenin kenar sayısı bu değeri aşamaz.
• Basit olmayan çizge: Aynı iki düğüm arasında birden çok kenar (çoklu kenar) ya da bir düğümü kendisine bağlayan kenar (öz döngü, self-loop) içerir. Bu ikisini içermeyen çizgeye basit çizge denir. Aksi belirtilmedikçe bu notta çizgeler basittir; tek istisna, güçlü bağlantılı bileşen örneğindeki öz döngüdür.

Bu türler birbirini dışlamaz. Bir yol haritası hem yönlü (tek yönlü sokaklar), hem ağırlıklı (uzunluklar), hem de döngülü olabilir. Bir ağaç her zaman iki parçalıdır: kökten uzaklığı çift olan düğümler bir kümeye, tek olanlar öteki kümeye konursa her kenar farklı kümeleri bağlar. Bu gözlem, iki parçalılık testinin de temelidir.

4.1.1.3Çizge algoritmalarının çeşitleri

Çizgeler üzerinde çalışan algoritmalar, yanıtladıkları soruya göre dört büyük gruba ayrılır:

1. Gezinme (graph traversal): Bir düğümden başlayıp ulaşılabilen bütün düğümleri düzenli bir sırayla dolaşmak. Derinlik öncelikli arama bir daldan sonuna kadar ilerler, genişlik öncelikli arama ise ağı katman katman tarar. Bu notun konusu bu gruptur.
2. En kısa yol (shortest path): Bir başlangıçtan öteki düğümlere giden en kısa yolları bulmak. Ağırlıklı çizgede Dijkstra algoritması bu işi yapar.
3. Minimum kapsayan ağaç (minimum spanning tree, MST): Bütün düğümleri en az toplam maliyetle birbirine bağlayan kenarları seçmek. Kruskal algoritması bunun bilinen bir örneğidir.
4. Ağ akışı (network flow): Kenarları kapasiteli bir ağda kaynaktan hedefe en çok ne kadar akış gönderilebileceğini bulmak.

Gezinme bu gruplar arasında en temel olanıdır, çünkü öteki algoritmaların çoğu içinde bir gezinme taşır. Dijkstra algoritması, kuyruğu öncelikli kuyrukla değiştirilmiş bir genişlik öncelikli aramaya benzer. Akış algoritmaları her turda bir gezinmeyle artırılabilir yol arar. Tablo 4.1.1 üç algoritmanın gündelik hayattaki karşılığını verir.

4.1.1.4Çizgeyi bellekte tutmak

Bir çizgeyle çalışan programın ilk kararı, çizgeyi bellekte nasıl tutacağıdır. Bu karar algoritmanın hızını doğrudan etkiler. İki yaygın gösterim vardır: komşuluk listesi ve komşuluk matrisi. İkisinde de düğümler 0, 1, …, V − 1 diye numaralanır; böylece bir düğüm, bir dizinin indisi olarak kullanılabilir.

Şekil 4.1.3'teki çizgenin komşuluk listesi şöyledir:

0: 1, 2
1: 0, 2
2: 0, 1, 3
3: 2

Yönsüz çizgede her kenar iki listede görünür. 0–1 kenarı hem 0'ın listesine 1 olarak, hem de 1'in listesine 0 olarak yazılır. Bu yüzden listelerin toplam uzunluğu 2E = 8'dir. Yönlü çizgede ise u → v kenarı yalnız u'nun listesine eklenir ve toplam uzunluk E olur. Aynı çizgenin komşuluk matrisi Tablo 4.1.2'de verilmiştir.

Yönsüz çizgenin matrisi köşegene göre simetriktir: M[u][v] = M[v][u]. Basit çizgede öz döngü olmadığı için köşegen sıfırdır. Matrisin bir satırındaki 1'lerin sayısı o düğümün derecesine eşittir; 2. satırda üç tane 1 vardır ve 2'nin derecesi 3'tür.

Java'da komşuluk listesi bir liste dizisi olarak kurulur. Aşağıdaki parça, kenarları {u, v} çiftleri hâlinde veren bir kenarlar dizisinden yönsüz bir çizgenin listesini oluşturur:

List<Integer>[] komsu = new List[n];
for (int v = 0; v < n; v++)
  komsu[v] = new ArrayList<>();
for (int[] k : kenarlar) {
  komsu[k[0]].add(k[1]);
  komsu[k[1]].add(k[0]);  // yönsüz: ters yön de eklenir
}

İlk döngü her düğüme boş bir liste açar: O(V). İkinci döngü her kenar için iki ekleme yapar: O(E). Kurulum O(V + E) zaman alır. Kenarlar (0, 1), (0, 2), (1, 2), (2, 3) sırasıyla verilirse sonuç tam olarak yukarıdaki listedir. Yönlü çizgede ikinci add satırı yazılmaz. Bu notun bütün Java kodları bu biçimdeki List<Integer>[] komsu dizisini kullanır.

İki gösterimin maliyetleri Tablo 4.1.3'te karşılaştırılmıştır.

Tablodaki her satırın bir gerekçesi vardır. Liste, düğüm başına bir liste başı ve kenar başına bir ya da iki öğe tutar; bu yüzden belleği V + E ile orantılıdır. Matris ise kenar sayısından bağımsız olarak V² hücre ayırır. Bir düğümün komşularını gezmek, listede yalnız o düğümün listesini okumak demektir. Matriste ise satırın bütün V hücresine bakmak gerekir, çünkü hangi hücrelerin 1 olduğu önceden bilinmez. Belirli bir kenarın varlığını sormak matriste tek bir hücre okumaktır; listede ise u'nun listesini baştan taramak gerekir.

Bir çizgenin kenar sayısı olabilecek en büyük değer olan V(V − 1)/2'nin çok altındaysa çizgeye seyrek (sparse), bu değere yakınsa yoğun (dense) denir. Gerçek ağların çoğu seyrektir. Bir yol ağında bir kavşağa bağlanan yol sayısı birkaç taneyle sınırlıdır; bir milyon kavşaklı ağda yaklaşık üç milyon yol olabilir. Komşuluk listesi bu ağı birkaç milyon öğeyle tutar. Matris ise 10¹² hücre ister; her hücre tek bir bit olsa bile 125 gigabayt eder. Bu yüzden gezinme algoritmalarında varsayılan gösterim komşuluk listesidir. Matris, çizge küçük ve yoğunsa ya da “bu iki düğüm komşu mu?” sorusu çok sık soruluyorsa tercih edilir.

4.1.2Çizge gezinme

4.1.2.1Gezinme problemi

Gezinmenin amacı, çizgenin yapısını sistemli biçimde keşfetmektir. Hangi düğümlere ulaşılabildiği, kaç bileşen olduğu, bir döngü bulunup bulunmadığı gibi sorular bir gezinmeyle yanıtlanır. “Tam bir kez” koşulu iki şey söyler. Birincisi, ulaşılabilen hiçbir düğüm atlanmamalıdır. İkincisi, hiçbir düğüm iki kez işlenmemelidir.

İkinci koşul ağaçlarda kendiliğinden sağlanır. Bir ağacı kökten gezerken her düğüme tek bir yoldan ulaşılır, çünkü ağaçta döngü yoktur. Çizgede ise bir düğüme birçok yoldan ulaşılabilir ve döngüler bulunabilir. Şekil 4.1.3'teki çizgede 0'dan 1'e geçilir, 1'den 2'ye, 2'den yeniden 0'a. Hangi düğümlerin daha önce görüldüğü hatırlanmazsa algoritma 0–1–2 döngüsünde sonsuza kadar döner. Bu yüzden her gezinme algoritması bir ziyaret dizisi tutar: ziyaret[v], v'nin daha önce işaretlenip işaretlenmediğini söyleyen bir boolean dizisidir. Bir düğüme ancak işaretli değilse ilerlenir.

Gezinme yalnız başlangıçtan ulaşılabilen düğümleri görür. Yönlü bir çizgede 0'dan 5'e yol yoksa 0'dan başlayan gezinme 5'i hiç ziyaret etmez. Bağlı olmayan bir çizgenin bütün düğümlerini gezmek için gezinme, henüz ziyaret edilmemiş her düğümden yeniden başlatılır. Yönsüz çizgede her başlatma yeni bir bağlı bileşeni keşfeder.

4.1.2.2İki yaklaşım: yığın ve kuyruk

Gezinme sırasında algoritmanın önünde her an keşfedilmiş ama henüz işlenmemiş düğümlerden oluşan bir “bekleme listesi” vardır. Sıradaki düğüm bu listeden seçilir. Seçimin nasıl yapıldığı, gezinmenin karakterini belirler. İki temel yaklaşımın tek farkı, bekleme listesini tutan veri yapısıdır.

• Derinlik öncelikli arama (depth-first search, DFS) bekleme listesini bir yığında (stack) tutar. Yığın son giren ilk çıkar (LIFO, last in, first out) kuralıyla çalışır. En son keşfedilen düğüm ilk işlenir; bu yüzden algoritma bir düğümden onun komşusuna, oradan da komşunun komşusuna doğru mümkün olduğunca derine iner. İlerleyecek yer kalmayınca bir önceki düğüme geri döner. Bu geri dönüşe geri izleme (backtracking) denir.
• Genişlik öncelikli arama (breadth-first search, BFS) bekleme listesini bir kuyrukta (queue) tutar. Kuyruk ilk giren ilk çıkar (FIFO, first in, first out) kuralıyla çalışır. Önce keşfedilen önce işlenir; bu yüzden algoritma önce başlangıca bir kenar uzaklıktaki düğümleri, sonra iki kenar uzaklıktakileri ziyaret eder. Gezinme seviye seviye ilerler.

Yığın ve kuyruk iki temel veri yapısıdır; ikisinde de ekleme ve çıkarma O(1) zaman alır. Java'da yığın için ArrayDeque'in push ve pop metotları, kuyruk için Queue arayüzünün add ve poll metotları kullanılır. Özyinelemeli yazılan DFS'te yığın açıkça görünmez. Onun yerine çağrı yığını kullanılır: her özyinelemeli çağrı yığına bir çerçeve iter, her dönüş bir çerçeve çeker.

4.1.3Derinlik öncelikli arama (DFS)

Derinlik öncelikli arama, çizge algoritmalarının belki de en çok kullanılan yapı taşıdır. Döngü bulma, topolojik sıralama, güçlü bağlantılı bileşenler ve köprü bulma gibi pek çok algoritma, bir DFS'in üzerine birkaç satır eklenerek elde edilir. Bu kesim DFS'i önce bir benzetmeyle, sonra bir ağaç üzerinde, ardından özyinelemeli ve yığınlı iki Java koduyla ele alır.

4.1.3.1Fikir: önce derine

DFS'in davranışı bir labirentteki gezgine benzer. Gezgin bir koridora girer ve çıkmaza varana kadar ilerler. Çıkmazda son geçtiği yol ayrımına geri döner ve oradan henüz denemediği bir koridora sapar. O koridor da bitince bir önceki ayrıma döner. Labirentin bütün koridorları denenene kadar bu böyle sürer. Gezginin işini kolaylaştıran iki şey vardır: geçtiği yerlere tebeşirle işaret koyar ki aynı koridoru iki kez dolaşmasın; geri dönüş noktalarını da sırasıyla aklında tutar.

Benzetmedeki tebeşir işaretleri ziyaret[] dizisidir. Geri dönüş noktalarını ise bir yığın hatırlar. Özyinelemeli sürümde bu yığın, programın çağrı yığınıdır: bir düğümün işi bitince onun çağrısı döner ve kontrol kendiliğinden bir önceki düğüme geçer. Yinelemeli sürümde açık bir Deque nesnesi kullanılır.

DFS sırasında bir düğüm üç durumdan birindedir. Bu durumlar renklerle anlatılır ve bu notun şekillerinde de aynı renkler kullanılır:

• Beyaz: düğüm henüz keşfedilmedi.
• Sarı: düğüm keşfedildi, ama işi sürüyor. Çağrısı yığında durur; komşularının bir kısmı henüz incelenmedi.
• Koyu: düğümün işi bitti; bütün komşuları incelendi ve çağrısı döndü.

Bir düğüme ilk kez ulaşılırken kullanılan kenarlar bir ağaç oluşturur. Bu ağaca DFS ağacı denir. Kökü başlangıç düğümüdür; her düğümün ebeveyni, onu keşfeden düğümdür. Şekil 4.1.5'te a–b, b–d ve b–e kenarları DFS ağacına aittir. Çizgenin öteki kenarları ağaca girmez, ama yine de incelenir ve önemli bilgiler taşır. Örneğin sarı bir düğüme giden kenar bir döngünün işaretidir.

DFS'in ziyaret sırası komşuların hangi sırayla denendiğine bağlıdır. Aynı çizgede komşu listeleri farklı sıralanırsa farklı ama yine geçerli bir DFS sırası çıkar. Bu notta aksi söylenmedikçe komşular, komşu listesindeki sırayla denenir. Yönsüz örneklerde listeler artan ya da alfabetik sıradadır.

4.1.3.2Bir ağaçta ziyaret sırası

DFS'in “derine inip geri dönme” düzenini en açık gösteren örnek bir ağaçtır, çünkü ağaçta döngü yoktur ve hiçbir düğüme iki yoldan ulaşılmaz. Şekil 4.1.6 on düğümlü bir ağaçta kökten başlayan DFS'in üç anını gösterir. Düğümlerin üstündeki numaralar, DFS'in onları ziyaret ettiği sıradır.

Örnekte yığının en çok dört düğüm tuttuğu görülür. Bu sayı kökten en uzak yaprağa giden yolun düğüm sayısıdır. DFS'in yığını hiçbir zaman en uzun yoldan daha derine inmez, çünkü yığında her an kökten şu anki düğüme giden ağaç yolu durur.

4.1.3.3Özyinelemeli sözde kod

DFS'in tanımı kendisini kullanır: bir düğümden DFS yapmak, onu işaretleyip her keşfedilmemiş komşusundan DFS yapmaktır. Bu yüzden algoritma en doğal hâliyle özyinelemeli yazılır. Kaynaklarda iki yazım yaygındır. İlki, İngilizce kaynaklarda sık görülen biçimdir:

procedure DFS(G, v) is
  label v as discovered
  for all directed edges from v to w
      that are in G.adjacentEdges(v) do
    if vertex w is not labeled
        as discovered then
      call DFS(G, w)

İkincisi, aynı fikrin denetimi çağrının başına taşıyan Türkçe yazımıdır:

DFS(düğüm, ziyaretEdilenler):
  eğer düğüm ziyaretEdilenler
        içinde değilse:
    düğüm'ü ziyaretEdilenler'e ekle
    düğüm'ü işle (örneğin, yazdır)
    her bir komşu düğüm için:
      DFS(komşu, ziyaretEdilenler)

İki sürüm aynı ziyaret sırasını üretir. Fark, “ziyaret edildi mi?” denetiminin nerede yapıldığıdır. İlk sürüm bir komşuyu çağırmadan önce denetler; işaretli komşu için hiç çağrı yapılmaz. İkinci sürüm her komşu için çağrı yapar ve denetimi çağrının başında yapar; işaretli bir düğüm için açılan çağrı hemen döner. İkinci sürüm daha kısa görünür, ama gereksiz çağrılar yapar. Her kenar için bir çağrı açılır ve çağrı sayısı O(E) olur. Mertebe değişmez, ama sabit çarpan büyür. Java kodu ilk sürümü izler.

Sözde kodlar tek bir başlangıç düğümünden ulaşılabilen düğümleri gezer. Bağlı olmayan bir çizgenin bütün düğümlerini gezmek için DFS, ziyaret edilmemiş her düğümden yeniden başlatılır. Yönsüz çizgede her başlatma bir bağlı bileşeni bütünüyle gezer.

4.1.3.4Kod: dfs()

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

Kod, sözde kodun ilk sürümünün Java karşılığıdır ve satır satır şöyle çalışır:

• ziyaret[v] = true; düğümü işaretler. İşaret, düğüm ziyaret edilir edilmez konur. Böylece komşulardan biri v'ye geri dönen bir kenar taşısa bile v ikinci kez çağrılmaz.
• System.out.print(v + " "); düğüm üzerindeki işi yapar; burada iş, düğümü yazdırmaktır. Bu satır, çağrının başında olduğu için düğümler keşif sırasıyla yazılır. Aynı satır döngüden sonraya konsaydı düğümler bitiş sırasıyla yazılırdı; topolojik sıralamada bu ikinci sıra kullanılır.
• for (int w : komsu[v]) v'nin komşu listesini baştan sona dolaşır.
• if (!ziyaret[w]) dfs(w, ziyaret); keşfedilmemiş komşuya iner. Özyinelemeli çağrı döndüğünde w'den ulaşılabilen her düğüm ziyaret edilmiştir ve döngü sıradaki komşuyla sürer. Geri dönüş tam olarak bu çağrı dönüşüdür.

Metot ziyaret dizisini parametre olarak alır. Dizi bir kez oluşturulur ve bütün çağrılar aynı diziyi paylaşır. Bu, bağlı olmayan çizgede DFS'i yeniden başlatmayı kolaylaştırır: aynı dizi, ikinci başlatmada birinci başlatmanın işaretlerini korur.

4.1.3.5Kod izleme: dfs(0)

İzlemede kullanılan çizge yönlüdür. Kenarları 0→1, 0→2, 0→7, 1→2, 2→0, 2→3, 2→4, 3→5, 4→6 ve 5→6'dır. Komşu listeleri bu sırayla dolar: komsu[0] = [1, 2, 7], komsu[2] = [0, 3, 4]. 6 ve 7'nin çıkan kenarı yoktur. Çizgede 0 → 1 → 2 → 0 ve 0 → 2 → 0 döngüleri vardır; ziyaret dizisi olmadan DFS bu döngülerde sonsuza kadar dönerdi.

İzlemenin üç anı ayrıca dikkat ister. 4. adımda 2'den 0'a giden kenar incelenir. 0 işaretlidir, üstelik hâlâ çağrı yığınındadır, yani sarıdır. Bu kenar bir döngünün kanıtıdır: yığında 0'dan 2'ye giden bir ağaç yolu (0 → 1 → 2) vardır ve 2 → 0 kenarı bu yolu kapatır. Kod burada yalnız atlar; döngü bulan sürüm burada “döngü var” diyebilir.

8. adımda üç çağrı art arda döner. 6'nın hiç çıkan kenarı yoktur; 5'in tek komşusu 6, 3'ün tek komşusu 5'tir. Kontrol 2'deki for döngüsüne, kaldığı yere döner ve sıradaki komşu 4 denenir. Geri dönüşün koddaki karşılığı budur: ayrı bir “geri dön” komutu yoktur, çağrıların dönmesi yeterlidir.

10. adımda 4'ten 6'ya giden kenar incelenir. 6 işaretlidir, ama yığında değildir; işi çoktan bitmiştir. Bu kenar bir döngü oluşturmaz: 6'dan 4'e dönen bir yol yoktur. Yönlü çizgede yalnız yığındaki düğüme giden kenar döngü belirtisidir; işi bitmiş düğüme giden kenar döngü belirtisi değildir.

Çıktı 0 1 2 3 5 6 4 7'dir. Çağrı yığını en çok altı çerçeveye ulaşmıştır (7. adım: 0, 1, 2, 3, 5, 6). DFS ağacında 0'dan 6'ya giden yol 0 → 1 → 2 → 3 → 5 → 6'dır ve beş kenar uzunluğundadır. Oysa çizgede 0'dan 6'ya üç kenarlık bir yol vardır: 0 → 2 → 4 → 6. Bu fark, DFS'in en kısa yolu bulmadığının ilk işaretidir.

4.1.3.6Yığınla DFS

Özyinelemeli DFS kısa ve anlaşılırdır, ama bir zayıflığı vardır: çağrı yığınının derinliği DFS yolunun uzunluğu kadardır. Çok uzun bir yol içeren çizgede bu derinlik on binleri bulabilir. Çağrı yığını sınırlı bir bellek alanıdır ve aşıldığında Java StackOverflowError fırlatır. JDK 21'in varsayılan ayarlarıyla yapılan bir denemede, 100 000 düğümlü bir yol çizgesinde özyinelemeli DFS yaklaşık 10 000 çağrı derinliğinde bu hatayla durmuştur. Çözüm, çağrı yığınının işini programın kendi oluşturduğu açık bir yığın nesnesine devretmektir. Bu nesne dinamik bellekte durur ve boyu yalnız toplam bellekle sınırlıdır. Önce İngilizce kaynaklardaki yaygın sözde kod:

procedure DFS_iterative(G, v) is
  let S be a stack
  S.push(v)
  while S is not empty do
    v = S.pop()
    if v is not labeled as discovered then
      label v as discovered
      for all edges from v to w
          in G.adjacentEdges(v) do
        S.push(w)

Aynı algoritmanın Türkçe yazımı:

DFS(başlangıç_düğüm):
  boş bir yığın oluştur
  başlangıç_düğüm'ü yığına ekle
  döngü yığın boş değilken:
    mevcut_düğüm = yığından çıkar
    eğer mevcut_düğüm ziyaretEdilenler
          içinde değilse:
      mevcut_düğüm'ü ziyaretEdilenler'e ekle
      her bir komşu_düğüm için:
        komşu_düğüm'ü yığına ekle

Java karşılığı:

void dfsYigin(int s) {
  boolean[] ziyaret = new boolean[n];
  Deque<Integer> yigin = new ArrayDeque<>();
  yigin.push(s);
  while (!yigin.isEmpty()) {
    int v = yigin.pop();
    if (!ziyaret[v]) {
      ziyaret[v] = true;
      System.out.print(v + " ");
      for (int w : komsu[v])
        yigin.push(w);
    }
  }
}

Kod üç noktada özyinelemeli sürümden ayrılır:

• Bekleme listesi açıktır. ArrayDeque bir yığın olarak kullanılır: push tepeye ekler, pop tepeden çeker. Döngü, yığın boşalana kadar sürer.
• İşaretleme çekerken yapılır. Bir düğüm yığına itilirken değil, yığından çekildiğinde işaretlenir. Bu yüzden henüz çekilmemiş bir düğüm, farklı komşulardan birden çok kez itilebilir. Çekildiğinde işaretliyse hiçbir şey yapılmaz. Yığına toplam 1 + Σ derece itme yapılır; bu da yönlü çizgede 1 + E, yönsüz çizgede 1 + 2E eder. Yığının boyu O(E)'ye kadar çıkabilir.
• Sıra terse döner. Komşular listedeki sırayla itilir, ama yığından en son itilen önce çıkar. Listesi [1, 2, 7] olan 0'dan sonra ilk çekilen düğüm 7'dir, 1 değil. Bu yüzden ziyaret sırası özyinelemeli sürümün sırasından farklıdır.

İşaretlemenin neden çekerken yapıldığını küçük bir örnek gösterir. 0'ın komşuları 1 ve 2, 2'nin komşusu da 1 olsun. Düğümler itilirken işaretlenseydi 0 işlenirken 1 ve 2 birlikte işaretlenirdi. 2 çekildiğinde komşusu 1 zaten işaretli olduğu için yığına girmezdi ve 1, 2'nin altından değil, 0'ın ikinci çocuğu olarak işlenirdi. Gezinme her düğümü yine bir kez ziyaret ederdi, ama 2'den başlayan dal sonuna kadar izlenmemiş olurdu; sıra artık derinlik öncelikli değildir. Çekerken işaretlemek, bir düğümün en son keşfedildiği yerden işlenmesini sağlar. DFS'in “önce derine” kuralı da budur.

4.1.3.7Kod izleme: dfsYigin(0)

Aynı yönlü çizgede dfsYigin(0) çağrısını izleyelim. Tabloda yığın soldan sağa, alttan tepeye doğru yazılmıştır; en sağdaki öğe tepedir.

Çıktı 0 7 2 4 6 3 5 1'dir. Özyinelemeli sürüm aynı çizgede 0 1 2 3 5 6 4 7 yazmıştı. İki sıra farklıdır, ama ikisi de geçerli bir DFS sırasıdır: yığınlı sürüm, komşu listelerinin ters çevrildiği bir çizgede özyinelemeli DFS'in vereceği sırayı verir. Yığına toplam 11 itme yapılmıştır: başlangıçtaki 0 ve on kenarın her biri için bir itme (1 + E = 11). 6, 0 ve 2 yığına ikişer kez girmiştir. Yığın en çok dört öğe tutmuştur.

Özyinelemeli sürümle aynı sıra istenirse komşular ters sırada itilir. 0'ın komşuları 7, 2, 1 sırasıyla itilirse tepeye 1 gelir ve ilk çekilen 1 olur. Bu durumda iki sürüm aynı ziyaret sırasını üretir.

4.1.3.8Karmaşıklık

O(V + E), çizgenin kendisini okumak için gereken zamandır. Her düğüme ve her kenara en az bir kez bakmadan bütün çizge hakkında bir şey söylenemez. Bu yüzden bu sınır gezinme için en iyisidir ve bu tür algoritmalara doğrusal zamanlı çizge algoritmaları denir.

Ek bellek de iki kalemdir. ziyaret[] dizisi O(V) yer tutar. Yığının boyu sürüme göre değişir. Özyinelemeli sürümde çağrı yığını en çok DFS ağacındaki en uzun yol kadar derinleşir; bu en kötü durumda V'dir, yani O(V). Örneğin bir yol çizgesinde (0–1–2–…) yığın bütün düğümleri tutar. Çekerken işaretleyen yığınlı sürümde ise bir düğüm birden çok kez itilebildiği için yığın O(E)'ye kadar büyüyebilir. Yoğun bir çizgede E, V² mertebesinde olabileceğinden bu fark önemsiz değildir. Yığındaki tekrarları önleyen daha ayrıntılı bir sürüm de yazılabilir. O sürümde yığının her öğesi, düğümle birlikte “sıradaki komşunun indisini” tutar. Böylece özyinelemeli DFS birebir taklit edilir ve O(V) ek bellek yeter.

4.1.3.9DFS ne işe yarar, ne yapamaz?

DFS'in gücü, gezinme sırasında topladığı yapısal bilgiden gelir. Bir düğümün ne zaman keşfedildiği, ne zaman bittiği ve bir kenarın sarı mı yoksa koyu bir düğüme mi gittiği, pek çok soruyu yanıtlamaya yeter:

• Ulaşılabilirlik ve bağlı bileşenler. s'den DFS yapıldıktan sonra ziyaret[t] doğruysa t'ye ulaşılabilir. DFS'in kaç kez başlatıldığı, yönsüz çizgedeki bağlı bileşen sayısını verir.
• Döngü tespiti. Yönlü çizgede çağrı yığınındaki (sarı) bir düğüme giden kenara geri kenar (back edge) denir. Geri kenar, hedef düğümden kaynak düğüme inen ağaç yoluyla birlikte bir döngü oluşturur. Tersine, çizgede bir döngü varsa döngüde ilk keşfedilen düğüm bitmeden döngünün öteki bütün düğümleri keşfedilir ve döngünün o düğüme dönen kenarı bir geri kenar olur. Dolayısıyla yönlü bir çizgede döngü olması, DFS'te geri kenar bulunmasıyla eşdeğerdir.
• Topolojik sıralama. Döngüsüz yönlü bir çizgede düğümlerin bitiş sırası tersine çevrilince bir topolojik sıra elde edilir.
• Güçlü bağlantılı bileşenler. Tarjan ve Kosaraju algoritmaları DFS üzerine kuruludur.
• Köprü ve eklem noktaları, bulmaca çözme. Köprüler Tarjan'ın enDüşükBağ fikriyle bulunur. Sudoku ve sekiz vezir gibi bulmacaları çözen geri izleme (backtracking) algoritmaları da örtük bir çizgede yapılan DFS'tir.

DFS'in yapamadığı da bir o kadar önemlidir: DFS en kısa yolu bulmaz. DFS bir hedefe ilk ulaştığında izlediği yol, uzun bir dolambaç olabilir. Yönlü örnekte DFS 6'ya 0 → 1 → 2 → 3 → 5 → 6 yoluyla, beş kenarda ulaşmıştı; en kısa yol üç kenarlıktı. Örnek 4.1.3'teki yönsüz çizgede DFS ağacı A'dan G'ye A–B–D–C–E–F–G yolunu, yani altı kenarı izler; en kısa yol ise A–B–D–F–G'dir ve dört kenarlıktır. En az kenarlı yolu bulmak için genişlik öncelikli arama gerekir.

4.1.4Genişlik öncelikli arama (BFS)

DFS bir dalı sonuna kadar izlerken BFS bütün dalları aynı anda, adım adım ilerletir. Bu fark küçük görünür, ama önemli bir sonucu vardır: BFS, ağırlıksız bir çizgede başlangıçtan her düğüme giden en az kenarlı yolu bulur. Navigasyonda “en az aktarmalı güzergâh”, sosyal ağda “iki kişi arasındaki tanışıklık zincirinin uzunluğu” ve oyunlarda “en az hamlede çözüm” bu özellikle hesaplanır.

4.1.4.1Fikir: katman katman

Durgun bir suya atılan taşın oluşturduğu dalgalar BFS'i iyi anlatır. Dalga önce taşın hemen çevresine ulaşır, sonra bir halka dışarı, sonra bir halka daha. Bir haberin yayılması da böyledir: haberi alan kişi onu bütün arkadaşlarına söyler, onlar da kendi arkadaşlarına. Haberi ilk duyanlar başlangıca bir adım uzaktakilerdir, sonra iki adım uzaktakiler duyar.

BFS'in iki kuralı vardır. Birincisi, kuyruk sırayı korur: önce keşfedilen önce işlenir. L₁'deki bütün düğümler kuyruğa L₂'dekilerden önce girdiği için önce çıkar. İkincisi, düğüm kuyruğa girerken işaretlenir. Böylece birden çok komşusu bir düğümü görse bile düğüm kuyruğa en fazla bir kez girer. Bu kural yığınlı DFS'teki “çekerken işaretle” kuralının tersidir; amacı kuyruğun gereksiz yere büyümesini önlemektir.

4.1.4.2Katmanlara ayrılan bir örnek

Sekiz düğümlü yönsüz bir çizge alınsın: 1 düğümü 2, 3, 4 ve 5'e; 2 düğümü 6 ve 7'ye; 3 düğümü 8'e bağlıdır. BFS 1'den başlar. Tablo 4.1.6 her adımda kuyruktan alınan düğümü, kuyruğa eklenen düğümleri ve kuyruğun durumunu gösterir.

Ziyaret sırası 1, 2, 3, 4, 5, 6, 7, 8'dir. Önce uzaklığı 1 olanlar (2, 3, 4, 5), sonra uzaklığı 2 olanlar (6, 7, 8) gelir. 6 ve 7, 3'ten önce keşfedilmiştir, ama kuyruğun sonuna eklendikleri için 3, 4 ve 5 işlendikten sonra işlenirler. Bir katmanın hepsi bitmeden sonraki katmana geçilmez; BFS'in “katman katman” ilerlemesi budur. Bu örnekte çizge bir ağaçtır ve her düğümü keşfeden kenarlar çizgenin bütün kenarlarıdır.

4.1.4.3Sözde kod

procedure BFS(G, root) is
  let Q be a queue
  label root as explored
  Q.enqueue(root)
  while Q is not empty do
    v := Q.dequeue()
    for all edges from v to w
        in G.adjacentEdges(v) do
      if w is not labeled as explored then
        label w as explored
        w.parent := v
        Q.enqueue(w)

Türkçe yazımı:

BFS(başlangıç_düğüm):
  boş bir kuyruk oluştur
  başlangıç_düğüm'ü keşfedildi işaretle
  başlangıç_düğüm'ü kuyruğa koy
  döngü kuyruk boş değilken:
    mevcut_düğüm = kuyruktan al
    her bir komşu_düğüm için
      eğer komşu_düğüm keşfedilmemiş ise
        komşu_düğüm'ü keşfedildi işaretle
        komşu_düğüm'ün ebeveyni = mevcut_düğüm
        komşu_düğüm'ü kuyruğa koy

Sözde kodda iki ayrıntı önemlidir. Birincisi w.parent := v satırıdır: her düğüm, onu keşfeden düğümü ebeveyni olarak kaydeder. Bu ebeveyn bağlantıları bir ağaç oluşturur; bu ağaca BFS ağacı denir. Hedeften ebeveynler boyunca köke doğru gidilince başlangıçtan hedefe giden en kısa yol tersten elde edilir. İkincisi, işaretleme kuyruğa eklerken yapılır, kuyruktan çıkarırken değil. Aksi hâlde bir düğümü, kuyruktan çıkana kadar geçen sürede onu gören her komşusu yeniden ekler.

4.1.4.4Kod: bfs()

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

• boolean[] ziyaret = new boolean[n]; bütün düğümleri işaretsiz başlatır. Java dizileri false ile dolu oluşturulur.
• Queue<Integer> kuyruk = new LinkedList<>(); kuyruğu oluşturur. LinkedList, Queue arayüzünü uygular; add sona ekler, poll baştan çıkarır, ikisi de O(1)'dir. ArrayDeque de aynı işi görür.
• ziyaret[s] = true; kuyruk.add(s); başlangıcı işaretler ve kuyruğa koyar. İşaret, kuyruğa girişle aynı anda konur.
• int v = kuyruk.poll(); kuyruğun başındaki düğümü çıkarır; ardından düğüm yazdırılır. Düğümler kuyruktan çıktıkları sırayla yazıldığı için çıktı, BFS ziyaret sırasıdır.
• İç döngü v'nin komşularını dolaşır. İşaretsiz komşu işaretlenir ve kuyruğun sonuna eklenir; işaretli komşu atlanır.

Zaman çözümlemesi DFS'inkiyle aynıdır. Her düğüm kuyruğa en fazla bir kez girer ve bir kez çıkar: O(V). Her düğümün komşu listesi, düğüm kuyruktan çıktığında bir kez dolaşılır: toplam O(E). BFS komşuluk listesiyle O(V + E), matrisle O(V²) zamanda çalışır. Ek bellek ziyaret[] için O(V), kuyruk için en geniş katman kadardır; bu da en kötü durumda O(V)'dir.

4.1.4.5Kod izleme: bfs(0)

Kodu DFS izlemesinde kullanılan yönlü çizgede çalıştıralım: komsu[0] = [1, 2, 7], komsu[1] = [2], komsu[2] = [0, 3, 4], komsu[3] = [5], komsu[4] = [6], komsu[5] = [6]; 6 ve 7'nin komşusu yoktur.

Çıktı 0 1 2 7 3 4 5 6'dır ve katmanlar {0}, {1, 2, 7}, {3, 4}, {5, 6}'dır. 2, 1'in komşusu olarak da görülür, ama 0 işlenirken zaten işaretlendiği için kuyruğa ikinci kez girmez. Aynı durum 6 için de geçerlidir: 4 onu işaretleyip eklemiştir, 5 onu yalnız görür. Kuyruk en çok üç düğüm tutmuştur. 6'nın uzaklığı 3'tür (0 → 2 → 4 → 6); DFS ağacı aynı düğüme beş kenarda ulaşmıştı.

4.1.4.6Uzaklık ve ebeveyn dizileri

BFS'in en kısa yol özelliğini kullanmak için ziyaret dizisi yerine iki dizi tutulur. uzaklik[v], s'den v'ye en az kenar sayısını; ata[v] ise BFS ağacında v'nin ebeveynini, yani v'yi keşfeden düğümü tutar. uzaklik[v] == -1 “henüz keşfedilmedi” anlamına gelir; bu yüzden ayrı bir ziyaret[] dizisine gerek kalmaz.

void bfsUzaklik(int s) {
  Arrays.fill(uzaklik, -1);
  Arrays.fill(ata, -1); uzaklik[s] = 0;
  Queue<Integer> kuyruk = new LinkedList<>();
  kuyruk.add(s);
  while (!kuyruk.isEmpty()) {
    int v = kuyruk.poll();
    for (int w : komsu[v])
      if (uzaklik[w] == -1) {  // yeni
        uzaklik[w] = uzaklik[v] + 1;
        ata[w] = v;
        kuyruk.add(w);
      }
  }
}

• Arrays.fill(uzaklik, -1); bütün düğümleri keşfedilmemiş sayar.
• Arrays.fill(ata, -1); uzaklik[s] = 0; bütün ebeveynleri “yok” (−1) yapar ve başlangıcın uzaklığını 0'a çeker. Başlangıcın ebeveyni de −1 kalır; yol kurulurken bu değer köke varıldığını gösterir. ata[]'nın tamamının doldurulması, ulaşılamayan düğümlerin de −1 taşımasını sağlar; bunun neden gerektiği yol kurulurken görülecek.
• if (uzaklik[w] == -1) komşunun yeni olup olmadığını sorar. Yeni komşu için uzaklik[w] = uzaklik[v] + 1 yazılır: w, v'nin katmanının bir sonraki katmanındadır. ata[w] = v, w'ye v'den gelindiğini kaydeder.

Kodu 1'den 8'e numaralı yönsüz örnek çizgede izleyelim (1–2, 1–3, 1–4, 1–5, 2–6, 2–7, 3–8). Tabloda diziler 1–8 indisleriyle yazılmıştır; “—” henüz keşfedilmemiş düğümdür (uzaklik = −1, ata = −1).

2 kuyruktan alındığında komşusu 1 zaten keşfedilmiştir (uzaklik[1] = 0), bu yüzden atlanır. 6 ve 7 ise yenidir ve uzaklik[2] + 1 = 2 değerini alır. Kuyruk boşaldığında sonuç Tablo 4.1.9'daki gibidir.

Kuyruktan çıkan düğümlerin uzaklıkları sırasıyla 0, 1, 1, 1, 1, 2, 2, 2'dir; dizi hiç azalmaz. Bu, BFS'in temel özelliğidir ve en kısa yol teoreminin ispatında kullanılır.

4.1.4.7Ağırlıksız en kısa yol

Teoremin günlük dildeki karşılığı şudur: BFS bir düğüme ilk ulaştığı anda ona en kısa yoldan ulaşmıştır. Daha kısa bir yol olsaydı, o yolun son düğümünden önceki düğüm daha önce kuyruktan çıkardı ve hedefi daha önce keşfederdi. Bu yüzden BFS bir düğümün uzaklığını bir kez yazar ve hiçbir zaman düzeltmez.

Yolun kendisi ebeveyn dizisinden geri kurulur:

List<Integer> yol(int[] ata, int s, int t) {
  LinkedList<Integer> yol = new LinkedList<>();
  for (int v = t; v != -1; v = ata[v])
    yol.addFirst(v);   // hedeften geriye
  if (yol.getFirst() != s)
    return null;       // t'ye ulaşılamadı
  return yol;
}

Döngü hedef t'den başlar ve her adımda ebeveyne geçer; −1'e gelince durur. Düğümler hedeften kaynağa doğru bulunduğu için listenin başına eklenir (addFirst); böylece liste kaynaktan hedefe doğru sıralı çıkar. Kaynak 1, hedef 8 için döngü 8'i ekler, ata[8] = 3'e geçer, 3'ü ekler, ata[3] = 1'e geçer, 1'i ekler ve ata[1] = −1 ile durur. Liste [1, 3, 8]'dir; ilk öğe kaynaktır ve yol döndürülür. Yolun düğüm sayısı uzaklik[t] + 1 olduğu için yol kurma O(uzaklik[t]) zaman alır.

Son if, hedefe hiç ulaşılamadığı durumu yakalar. t keşfedilmediyse ata[t] = −1'dir; döngü yalnız t'yi ekleyip durur. Listenin ilk öğesi t'dir, s değil; metot null döndürür. Bu denetimin doğru çalışması, ata[]'nın BFS başında −1 ile doldurulmasına bağlıdır.

Teorem yalnız ağırlıksız çizgede, ya da bütün ağırlıkların eşit olduğu çizgede geçerlidir. BFS kenar sayısını en aza indirir, ağırlık toplamını değil. Kenarları s → t (ağırlık 10), s → a (ağırlık 1) ve a → t (ağırlık 1) olan bir çizge alınsın. BFS t'yi ilk katmanda, s'nin doğrudan komşusu olarak bulur. Bulunan yol tek kenarlıdır, ama maliyeti 10'dur. En ucuz yol s → a → t'dir ve maliyeti 2'dir. Ağırlıklı çizgede en kısa yol için Dijkstra algoritması gerekir.

4.1.4.8BFS ile labirent çözmek

Kareli bir labirent doğrudan bir çizgeye çevrilebilir. Her boş hücre bir düğümdür. Yukarı, aşağı, sağa ya da sola bitişik iki boş hücre arasında bir kenar vardır. Duvar hücreleri çizgeye hiç girmez. Böylece “girişten çıkışa en az adım” sorusu, “bu çizgede iki düğüm arasındaki en kısa yol” sorusuna dönüşür. Çizge ağırlıksızdır, çünkü her adımın maliyeti aynıdır; doğru araç BFS'tir.

Şekil 4.1.14'teki labirent 9 × 9 hücreliktir. Hücrelerin 47'si duvar, 34'ü boştur; bitişik boş hücre çiftlerinin sayısı da 34'tür. Çizgede 34 düğüm ve 34 kenar vardır. Giriş sol üstte, çıkış sağ alttadır. Bir düğümün komşuları, dört yöndeki boş hücrelerdir. Komşular kod içinde ayrıca bir listeye yazılmaz; bir hücrenin dört komşusunun satır ve sütun numarası doğrudan hesaplanır. Böyle tanımlanan çizgeye örtük çizge denir.

Gezinme şöyle ilerler. Giriş hücresi uzaklık 0 ile kuyruğa konur. İlk adımlarda labirent tek bir koridordur ve dalga aşağı doğru iner; her hücreye yazılan sayı bir öncekinden bir fazladır. Uzaklık 5'teki hücrede yol çatallanır. Dalga artık iki kola ayrılır: biri sağa ve oradan yukarıdaki odaya, öteki aşağıya ilerler. BFS bu iki kolu sırayla değil, aynı anda ilerletir; kuyrukta iki kolun uzaklığı 6 olan hücreleri, ardından uzaklığı 7 olan hücreleri yan yana bekler. Bu yüzden BFS'e “var olan bütün yolları eşzamanlı deneyen” arama da denir.

Uzaklık 10'da dalga hem yukarıdaki koridora, hem de aşağıdaki alt koridora ulaşır. Üst kol bir süre çıkmaz sokaklarda dolaşırken alt koridor çıkışa yaklaşır. Çıkış hücresine 14 adımda ulaşılır. Teorem gereği bu değer kesin olarak en kısadır; daha kısa bir yol olsaydı çıkış daha önceki bir katmanda keşfedilirdi. Arama bu noktada durdurulabilir. Durdurulmazsa uzaklığı 15, 16 ve 17 olan altı hücre daha keşfedilir; bu hücreler en kısa yol için gereksizdir. En kısa yol, çıkıştan başlayıp ebeveyn bağlantıları girişe kadar izlenerek bulunur. Yol 15 hücreden, yani 14 adımdan oluşur.

DFS aynı labirentte de çıkışı bulur, ama bulduğu yolun en kısa olduğu garanti değildir. Çatallanma noktasında önce yukarıdaki kola girerse, o kolun bütün çıkmazlarını dolaştıktan sonra çıkışa uzun bir dolambaçla varabilir. BFS'in bedeli ise bellektir: dalganın bütün sınırını aynı anda kuyrukta tutar.

4.1.4.9BFS ile DFS'in karşılaştırılması

Aynı yönlü çizgede, aynı kaynak 0'dan DFS 0 1 2 3 5 6 4 7, BFS ise 0 1 2 7 3 4 5 6 yazar. İkisi de bütün düğümleri bir kez ziyaret eder ve ikisinin de zamanı aynıdır; fark ziyaret sırasında ve ürettikleri ağaçtadır.

Bellek karşılaştırması çizgenin biçimine bağlıdır. 15 düğümlü tam bir ikili ağaç (dört seviye) kökten gezilsin. BFS'te son seviyedeki sekiz yaprak aynı anda kuyrukta bulunur; kuyruk en çok 8 düğüm tutar. Özyinelemeli DFS'te ise çağrı yığını kökten yaprağa giden yol kadar, 4 çerçeve derinleşir. Ağaç 20 seviyeli olsaydı, yani 1 048 575 düğümü olsaydı, BFS kuyruğu 524 288 düğüme ulaşırdı; DFS'in yığını ise 20 çerçevede kalırdı. Tersine, uzun bir yol çizgesinde DFS'in yığını bütün düğümleri tutar, BFS'in kuyruğu ise uçtan başlayınca tek düğümle yetinir. İkisinin de en kötü durumu O(V)'dir; hangisinin daha az bellek kullanacağını çizgenin derinliği ve genişliği belirler.

4.1.5Güçlü bağlantılı bileşenler

Yönsüz bir çizgede bağlılık basit bir kavramdır: u'dan v'ye yol varsa v'den u'ya da vardır. Yönlü çizgede bu simetri bozulur. Tek yönlü sokaklarla dolu bir şehirde bir mahalleden ötekine gidilebilir, ama aynı yoldan geri dönülemeyebilir. Hangi düğümlerin birbirine karşılıklı olarak ulaşabildiğini bulmak, yönlü çizgelerin yapısını anlamanın ilk adımıdır.

4.1.5.1Tanım

Şekil 4.1.15'teki çizgenin kenarları 1→2, 2→3, 3→1, 4→2, 4→3, 4→5, 5→6, 5→4, 6→3, 6→7, 7→6, 8→5, 8→7 ve 8→8'dir. 1, 2 ve 3 bir döngü üzerindedir (1 → 2 → 3 → 1); her biri ötekilere ulaşır. 4 ile 5 arasında iki yönde de kenar vardır; 6 ile 7 de öyle. 8 ise tek başına bir bileşendir: 8'den başka herkese ulaşılır, ama hiçbir düğümden 8'e ulaşılamaz.

Tanımdan birkaç sonuç çıkar. Karşılıklı ulaşılabilirlik bir denklik bağıntısıdır: her düğüm kendisine ulaşır (sıfır uzunluklu yol), bağıntı simetriktir ve geçişlidir (u ⇄ v ve v ⇄ w ise u ⇄ w). Bu yüzden güçlü bağlantılı bileşenler düğüm kümesini ayrık parçalara böler; her düğüm tam bir bileşene aittir. Tek bir düğüm de bileşen olabilir; döngüye hiç katılmayan her düğüm böyledir.

Sık karşılaşılan bir yanılgı, “bir düğüm ve ondan ulaşılabilen bütün düğümler” kümesini bileşen sanmaktır. 8'den bütün düğümlere ulaşılır, ama {1, …, 8} bir SCC değildir, çünkü örneğin 1'den 8'e dönülemez. SCC iki yönlü ulaşılabilirlik ister.

Her bileşen tek bir düğüme indirgenip bileşenler arasındaki kenarlar korunursa bileşen çizgesi elde edilir. Şekildeki örnekte bileşen çizgesinin kenarları şunlardır: {8} → {4, 5}, {8} → {6, 7}, {4, 5} → {1, 2, 3}, {4, 5} → {6, 7} ve {6, 7} → {1, 2, 3}. Bileşen çizgesi her zaman döngüsüzdür. İki bileşen arasında iki yönde de yol olsaydı, bu bileşenlerin düğümleri karşılıklı ulaşılabilir olurdu ve iki bileşen aslında tek bir bileşen olurdu. Bu yapı pek çok uygulamada kullanılır: sosyal ağlarda birbirini takip eden toplulukları bulmak, bir derleyicide birbirine karşılıklı bağımlı modülleri birlikte derlemek, mantıkta 2-SAT problemini çözmek bunlardan birkaçıdır.

Bileşenleri bulmanın en kaba yolu, her düğümden bir gezinme yapıp karşılıklı ulaşılabilirliği tek tek denetlemektir; bu O(V · (V + E)) zaman alır. Robert Tarjan 1972'de bütün bileşenleri tek bir DFS ile, O(V + E) zamanda bulan bir algoritma yayımladı.

4.1.5.2Tarjan algoritmasının fikri

Tarjan algoritması DFS sırasında her düğüme iki sayı atar ve keşfedilen düğümleri ayrı bir yığında tutar.

Yığın, DFS'in çağrı yığınından farklıdır. Bir düğüm keşfedildiğinde bu yığına itilir, ama işi bittiğinde hemen çekilmez. Bileşeni belirlenene kadar yığında kalır. Böylece yığında, o ana kadar keşfedilmiş ve henüz hiçbir bileşene atanmamış düğümler durur.

DFS bir v düğümünün kenarlarını incelerken üç durumla karşılaşır:

1. Ağaç kenarı v → w, w henüz keşfedilmemiş: w'den özyinelemeli olarak devam edilir. Çağrı dönünce enDüşükBağ(v) = min(enDüşükBağ(v), enDüşükBağ(w)) yapılır. w'nin alt ağacı eski bir düğüme ulaşabiliyorsa v de o düğüme ulaşabilir.
2. Yığındaki bir w'ye kenar: w keşfedilmiş ve henüz bir bileşene atanmamıştır. enDüşükBağ(v) = min(enDüşükBağ(v), indeks(w)) yapılır. v, kendisinden önce keşfedilmiş ve bileşeni hâlâ açık olan bir düğüme ulaşabiliyor.
3. Bileşeni bulunmuş bir w'ye kenar: w keşfedilmiş ve yığından çekilmiştir. Bu kenar yok sayılır. w'nin bileşeni kapanmıştır; w'den v'ye dönen bir yol yoktur ve v o bileşene katılamaz.

v'nin bütün kenarları incelendikten sonra karar verilir. enDüşükBağ(v) = indeks(v) ise v'nin alt ağacından v'den daha eski bir yığın düğümüne ulaşılamıyordur. v bir bileşenin köküdür, yani o bileşende ilk keşfedilen düğümdür. Yığından v'ye kadar (v dahil) çekilen bütün düğümler bir SCC oluşturur. enDüşükBağ(v) < indeks(v) ise v'nin alt ağacından daha eski bir yığın düğümüne geri dönülebiliyordur; v o düğümle aynı bileşendedir ve kök değildir. v yığında kalır ve bileşeni, kök bittiğinde birlikte çekilir.

Kök koşulunun neden doğru olduğunu kısaca şöyle gerekçelendirmek mümkün: Bir bileşende ilk keşfedilen düğüm r olsun. Bileşenin öteki bütün düğümleri r'den ulaşılabilir olduğu için r'nin alt ağacına düşer ve r bitmeden keşfedilir. Bileşenin hiçbir düğümü r'den eski bir yığın düğümüne ulaşamaz; ulaşsaydı o düğüm de r'ye ulaşır, r ondan ulaşılır ve aynı bileşende olurdu. Bu yüzden enDüşükBağ(r) = indeks(r) kalır. Bileşenin öteki düğümleri ise r'ye geri dönebildikleri için daha küçük bir enDüşükBağ değeri alır.

4.1.5.3Tarjan adım adım

Şekil 4.1.15'teki çizgede Tarjan algoritması düğümleri 1'den 8'e sırayla dener. İndeksler 1'den başlar. Her düğümün yanına “indeks, enDüşükBağ” çifti yazılır. Tablo 4.1.11 algoritmanın bütün adımlarını verir.

Tablodaki üç an algoritmanın bütün mantığını gösterir. 4. adımda 3 → 1 kenarı, yığındaki eski bir düğüme dönüşü yakalar ve 3'ün enDüşükBağ değerini 1'e indirir. Bu değer 5. ve 6. adımlarda çağrı dönüşleriyle 2'ye ve 1'e taşınır. Sonuçta yalnız 1'de indeks ile enDüşükBağ eşit kalır; 1 köktür ve yığında 1'in üstündeki her düğüm onun bileşenidir.

8. adımda 4 → 2 ve 4 → 3 kenarları yok sayılır. 2 ve 3 keşfedilmiştir, ama yığında değildir; bileşenleri kapanmıştır. Bu kenarlar dikkate alınsaydı 4'ün enDüşükBağ değeri 2'ye inerdi ve 4 kök sayılmazdı. Oysa 4, 2'ye ulaşsa da 2'den 4'e dönen bir yol yoktur; 4 yeni bir bileşenin ilk düğümüdür.

12. adımda 6 kök olarak bulunur ve {6, 7} çekilir, ama 5 ve 4 yığında kalır. 5 ile 4'ün bileşeni daha sonra, 14. adımda kapanır. Bileşenler bulunma sırasıyla {1, 2, 3}, {6, 7}, {4, 5}, {8}'dir. Bileşen çizgesindeki kenarlarla karşılaştırılınca bu sıranın ters topolojik sıra olduğu görülür: her bileşen, ondan kenar alan bütün bileşenlerden önce bulunur. {1, 2, 3}'ten çıkan hiçbir kenar yoktur ve ilk o bulunur; {8}'e ise hiçbir kenar girmez ve en son o bulunur. Bu bir rastlantı değildir: bir bileşen ancak ondan ulaşılabilen bütün bileşenler bulunduktan sonra kapanabilir.

4.1.5.4Sözde kod ve Java kodu

Algoritmanın sözde kodu iki parçadır. Dış döngü ziyaret edilmemiş her düğümden SCC çağırır:

TARJAN_SCC(G):
  indeks = 1
  yığın = [ ]
  SCCler = [ ]
  her bir v için V içinde:
    eğer v.indeks tanımlı değilse:
      SCC(v)
  döndür SCCler

Asıl iş özyinelemeli SCC yordamındadır:

SCC(v):
  v.indeks = v.enDüşükBağ = indeks++
  yığın.ekle(v)
  her bir (v, w) için E içinde:
    eğer w.indeks tanımlı değilse:
      SCC(w)
      v.enDüşükBağ = min(v.enDüşükBağ, w.enDüşükBağ)
    değilse eğer w yığında ise:
      v.enDüşükBağ = min(v.enDüşükBağ, w.indeks)
  eğer v.enDüşükBağ == v.indeks:
    scc = [ ]
    döngü w ≠ v olduğu sürece:  // en az bir kez
      w = yığın.çıkar()
      scc.ekle(w)
    SCCler.ekle(scc)

Java kodu sözde kodun birebir karşılığıdır:

void scc(int v) {
  indeks[v] = dusuk[v] = ++sayac;
  yigin.push(v); yiginda[v] = true;
  for (int w : komsu[v]) {
    if (indeks[w] == 0) {
      scc(w);
      dusuk[v] = Math.min(dusuk[v], dusuk[w]);
    } else if (yiginda[w])
      dusuk[v] = Math.min(dusuk[v], indeks[w]);
  }
  if (dusuk[v] == indeks[v]) {
    int w;
    do {
      w = yigin.pop(); yiginda[w] = false;
      System.out.print(w + " ");
    } while (w != v);
    System.out.println();
  }
}

• indeks[v] = dusuk[v] = ++sayac; keşif sırasını atar. sayac 0'dan başlar ve önce artırıldığı için ilk düğümün indeksi 1 olur. Bu tercih, indeks[w] == 0 denetimini “henüz keşfedilmedi” anlamında kullanmayı sağlar; ayrı bir ziyaret dizisine gerek kalmaz. İndeksleri 0'dan başlatmak da aynı bileşenleri verir; o durumda keşfedilmemiş düğüm için başka bir işaret, örneğin −1 gerekir.
• yigin.push(v); yiginda[v] = true; düğümü yığına iter. yiginda[] dizisi, “w yığında mı?” sorusunu O(1) zamanda yanıtlar. Yığını baştan sona aramak her kenarda O(V) sürerdi.
• if (indeks[w] == 0) dalı ağaç kenarıdır: özyinelemeli çağrıdan sonra dusuk[v], dusuk[w] ile güncellenir.
• else if (yiginda[w]) dalı yığındaki düğüme giden kenardır: dusuk[v], indeks[w] ile güncellenir. Bileşeni bulunmuş w için iki koşul da yanlıştır ve hiçbir şey yapılmaz.
• Son if kök denetimidir. do … while döngüsü yığından v'ye kadar bütün düğümleri çeker ve yazdırır. Döngü do … while biçimindedir, çünkü en az bir düğüm (v'nin kendisi) her zaman çekilir. Her bileşen ayrı bir satıra yazılır.

4.1.5.5Kod izleme: scc(0)

İzlemenin çizgesi beş düğümlüdür: 0→1, 1→2, 2→0, 2→3, 3→4, 4→3. komsu[2] = [0, 3]'tür.

Program iki satır yazar: önce 4 3, sonra 2 1 0. Bileşen içindeki düğümler yığından çekildikleri sırayla, yani keşif sırasının tersiyle yazılır. 4. adımdaki 2 → 0 kenarı bir geri kenardır ve dusuk[2]'yi 1'e indirir. 11. adımda scc(3) dönünce dusuk[3] = 4 değeri 2'nin değerini değiştirmez, çünkü 2 zaten 1'e ulaşmıştır. {3, 4} bileşeni 2'den ulaşılan ama 2'ye geri dönemeyen bir bileşendir ve ilk o kapanır.

4.1.5.6Karmaşıklık

4.1.5.7Kosaraju algoritması

Güçlü bağlantılı bileşenleri bulan ikinci klasik yöntem Kosaraju algoritmasıdır. Tarjan'dan daha kolay anlaşılır, ama iki DFS ve çizgenin bir kopyasını ister. Algoritma, bir çizgenin tersi (transpose) üzerinde çalışır: ters çizge aynı düğümleri içerir ve her u → v kenarı v → u olur. Bir çizge ile tersinin güçlü bağlantılı bileşenleri aynıdır, çünkü karşılıklı ulaşılabilirlik okların yönünden etkilenmez.

Algoritmanın üç adımı vardır:

1. Çizgede DFS yapılır ve her düğüm işi bittiğinde bir yığına itilir. Yığının tepesinde en son biten düğüm durur.
2. Çizgenin tersi oluşturulur.
3. Yığından düğümler sırayla çekilir. Çekilen düğüm henüz ziyaret edilmemişse ters çizgede ondan bir DFS yapılır. Bu DFS'in ulaştığı düğümler bir SCC'dir.

Ters çizgeyi kuran parça:

List<Integer>[] ters = new List[n];
for (int v = 0; v < n; v++)
  ters[v] = new ArrayList<>();
for (int v = 0; v < n; v++)
  for (int w : komsu[v])
    ters[w].add(v);       // v → w kenarı w → v olur

Algoritmanın Java kodu:

void kosaraju() {
  for (int v = 0; v < n; v++)  // 1. tur
    if (!ziyaret[v]) dfs1(v);
  Arrays.fill(ziyaret, false); // 2. tur
  while (!yigin.isEmpty()) {
    int v = yigin.pop();
    if (!ziyaret[v]) {   // yeni SCC
      dfs2(v); System.out.println(); }
  }
}
void dfs1(int v) {
  ziyaret[v] = true;
  for (int w : komsu[v])
    if (!ziyaret[w]) dfs1(w);
  yigin.push(v);       // v bitti
}

İkinci turdaki dfs2, ters çizgede çalışan sıradan bir DFS'tir:

void dfs2(int v) {     // ters çizgede DFS
  ziyaret[v] = true;
  System.out.print(v + " ");
  for (int w : ters[v])
    if (!ziyaret[w]) dfs2(w);
}

dfs1, dfs'ten tek bir satırla ayrılır: düğüm, komşularının hepsi bittikten sonra yığına itilir (yigin.push(v); // v bitti). Bu satır bitiş sırasını kaydeder. kosaraju() önce ziyaret edilmemiş her düğümden dfs1 başlatır. Sonra ziyaret dizisini temizler ve yığını boşaltır. Yığından çekilen ziyaret edilmemiş her düğüm yeni bir bileşenin başlangıcıdır.

Algoritmanın neden doğru çalıştığı bileşen çizgesiyle açıklanır. Birinci turda en son biten düğüm, bileşen çizgesinde hiç kenar almayan bir kaynak bileşendedir. Ters çizgede bu bileşenin bütün dış kenarları içe döner. Bu yüzden ters çizgede ondan başlayan DFS bileşenden dışarı çıkamaz ve tam olarak o bileşeni gezer. Yığından sonraki ziyaret edilmemiş düğüm, kalan bileşenler arasında yine bir kaynak bileşendedir. Ters çizgede ondan çıkan kenarlar ya kendi bileşenine ya da zaten bulunmuş bileşenlere gider; ziyaretli düğümlere de girilmez. Böylece her DFS tam bir bileşen bulur.

Kosaraju algoritmasını Tarjan izlemesindeki beş düğümlü çizgede (0→1, 1→2, 2→0, 2→3, 3→4, 4→3) izleyelim.

Program iki satır yazar: 0 2 1 ve 3 4. Ters çizgede 3'ün komşu listesi [2, 4]'tür; 2 → 3 kenarı ters çizgede 3 → 2 olmuştur. Bu kenar 3'ü bir önceki bileşene bağlar, ama 2 ziyaretli olduğu için DFS oraya geçmez. Birinci turda 0 en son bittiği için kaynak bileşen olan {0, 1, 2}'den başlanmıştır. Bu bileşen, asıl çizgede {3, 4}'e kenar verir; ters çizgede bu kenar içe döndüğü için dfs2(0) 3'e ulaşamaz.

Sekiz düğümlü örnekte Kosaraju algoritması da aynı dört bileşeni bulur. Birinci turun bitiş sırası 3, 2, 1, 7, 6, 5, 4, 8'dir. İkinci turda bileşenler {8}, {4, 5}, {6, 7}, {1, 2, 3} sırasıyla bulunur. Bu sıra Tarjan'ın sırasının tam tersidir: Kosaraju bileşenleri topolojik sırayla, Tarjan ters topolojik sırayla verir.

İki algoritmanın mertebesi aynıdır. Tarjan çizgeyi bir kez dolaşır ve kopya gerektirmez; pratikte genellikle daha hızlıdır. Kosaraju'nun mantığı daha kolay kavranır ve doğruluğu daha kolay gerekçelendirilir. Ters çizgeyi kurmak O(V + E) zaman ve bellek ister, ama mertebeyi değiştirmez.

4.1.6Gezinmenin uygulamaları

DFS ve BFS tek başlarına yalnız düğümleri bir sırayla dolaşır. Gezinmeye birkaç satır eklenince çizgenin yapısıyla ilgili pek çok soru aynı O(V + E) zamanda yanıtlanır. Bu kesim en sık kullanılan uygulamaları ele alır.

4.1.6.1Topolojik sıralama

Kenarlar “önce bu, sonra şu” türünden ön koşulları anlatır. Ön koşullu dersler, bir projenin derlenme sırası, bir tablolama programında hücrelerin hesaplanma sırası ve bir şantiyedeki işlerin planlanması topolojik sıralama problemleridir. Örneğin “Veri Yapıları” dersi “Programlama” dersinden sonra alınmalıysa, ders planı bu iki dersi bu sırayla içermelidir.

Topolojik sıra yalnız döngüsüz yönlü çizgede vardır. Çizgede u → v → … → u biçiminde bir döngü olsaydı, u'nun hem bu döngüdeki her düğümden önce hem de sonra gelmesi gerekirdi. Tersine, her DAG'ın en az bir topolojik sırası vardır. Ayrıca topolojik sıra çoğu zaman tek değildir: aralarında yol olmayan iki düğüm herhangi bir sırada yazılabilir.

Şekil 4.1.20'deki çizge, DFS izlemesindeki yönlü çizgeden 2 → 0 kenarı çıkarılarak elde edilmiştir. O kenar çizgeye bir döngü katıyordu; kenar çıkınca çizge döngüsüz olur. Topolojik sıralamanın iki klasik yöntemi vardır: BFS tabanlı Kahn algoritması ve DFS tabanlı ters bitiş sırası. Bu çizgede ikisinin sonucu farklıdır, ama ikisi de geçerlidir:

İki sırada da dokuz kenarın her biri soldan sağa gider. Örneğin 4 → 6 ve 5 → 6 kenarları için 6 iki sırada da en sondadır. 7 ise yalnız 0'dan sonra gelmek zorundadır; Kahn onu 1'den sonra, DFS 0'ın hemen arkasına yazar.

4.1.6.2Kahn algoritması ve kod izleme

Kahn algoritmasının fikri, ön koşulu kalmamış işleri sırayla yapmaktır. Giriş derecesi 0 olan bir düğümün hiçbir ön koşulu yoktur; ilk o yazılabilir. Yazılan düğüm ve kenarları çizgeden silinmiş sayılır. Bu silme, bazı düğümlerin giriş derecesini 0'a indirir; o düğümler de artık yazılabilir. Hazır düğümler bir kuyrukta bekler.

void kahn() {
  int[] giris = new int[n];
  for (int v = 0; v < n; v++)
    for (int w : komsu[v]) giris[w]++;
  Queue<Integer> kuyruk = new LinkedList<>();
  for (int v = 0; v < n; v++)
    if (giris[v] == 0) kuyruk.add(v);
  while (!kuyruk.isEmpty()) {
    int v = kuyruk.poll();
    System.out.print(v + " ");
    for (int w : komsu[v])
      if (--giris[w] == 0) kuyruk.add(w);
  }
}

• İlk iç içe döngü her kenarın hedefinin giriş derecesini bir artırır. Bütün komşu listeleri bir kez dolaşıldığı için bu kısım O(V + E)'dir.
• İkinci döngü giriş derecesi 0 olan bütün düğümleri kuyruğa koyar.
• Ana döngü kuyruktan bir düğüm alır ve yazar. Çıkan her kenar için hedefin derecesi azaltılır: --giris[w]. Kenarın kendisi silinmez, yalnız sayaç azaltılır. Derecesi 0'a inen hedef kuyruğa eklenir.

Çıktı 0 1 7 2 3 4 5 6'dır. 4 çıkarıldığında 6'nın derecesi yalnız 1'e iner: 6'nın iki ön koşulundan biri (4) tamamlanmış, öteki (5) hâlâ bekliyor. 6 ancak 5 çıkarıldıktan sonra kuyruğa girer. Kahn algoritmasının özü budur: bir düğüm, bütün ön koşulları yazılmadan yazılmaz.

Kahn algoritması aynı zamanda bir döngü testidir. Çizgede döngü varsa döngüdeki düğümlerin hiçbirinin derecesi 0'a inmez, çünkü her biri döngüdeki bir önceki düğümü bekler. Kuyruk, bütün düğümler yazılmadan boşalır. Bu yüzden yazılan düğüm sayısı V'den azsa çizgede döngü vardır. Örnek çizgeye 2 → 0 kenarı geri eklenirse 0'ın giriş derecesi 1 olur ve başlangıçta derecesi 0 olan hiçbir düğüm kalmaz. Kuyruk boş başlar, hiçbir düğüm yazılmaz ve algoritma döngüyü bildirir.

Algoritmanın zamanı O(V + E)'dir: her düğüm kuyruğa bir kez girip çıkar, her kenar bir kez sayılır ve bir kez azaltılır. Kuyruk yerine başka bir yapı da kullanılabilir. Örneğin hazır düğümler bir öncelikli kuyrukta tutulursa her adımda numarası en küçük hazır düğüm seçilir. Bu yolla sözlük sırasına göre en küçük topolojik sıra elde edilir; zaman ise O((V + E) log V)'ye çıkar.

4.1.6.3DFS ile topolojik sıralama

DFS tabanlı yöntemde düğümler, işleri bittiği anda bir yığına itilir. Gezinme bitince yığından çekilen sıra bir topolojik sıradır. Bu, Kosaraju algoritmasının birinci turuyla aynı iştir:

void dfsBitis(int v) {
  ziyaret[v] = true;
  for (int w : komsu[v])
    if (!ziyaret[w]) dfsBitis(w);
  yigin.push(v);           // bitince it
}

Ana program ziyaret edilmemiş her düğümden dfsBitis çağırır, sonra yığını boşaltarak düğümleri yazar. Şekil 4.1.20'deki çizgede dfsBitis(0) önce 1'e, oradan 2'ye, 3'e, 5'e ve 6'ya iner. 6'nın çıkan kenarı yoktur; ilk biten odur. Ardından 5 ve 3 biter. 2'nin sıradaki komşusu 4'tür; 4'ün komşusu 6 zaten bitmiştir ve 4 biter. Sonra 2, 1, 7 ve 0 biter. Bitiş sırası 6, 5, 3, 4, 2, 1, 7, 0'dır; yığından çekilen sıra bunun tersi olan 0 7 1 2 4 3 5 6'dır.

İspattaki “sarı olamaz” adımı aynı zamanda döngü testini verir: DFS sırasında sarı bir düğüme giden kenar bulunursa çizge döngülüdür ve topolojik sıra yoktur. DFS yöntemi de O(V + E) zamanda çalışır. Kahn yöntemi sırayı baştan sona üretir. Hazır işleri kuyrukta tuttuğu için paralel planlamaya da uygundur. DFS yöntemi ise mevcut bir DFS koduna tek satır eklenerek elde edilir.

4.1.6.4Bağlı bileşenler

Yönsüz bir çizgenin kaç bağlı bileşeni olduğu, gezinmenin kaç kez başlatıldığı sayılarak bulunur. Ziyaret edilmemiş her düğümden yeni bir DFS (ya da BFS) başlatılır; her başlatma yeni bir bileşeni bütünüyle gezer.

int bilesenSayisi() {
  boolean[] ziyaret = new boolean[n];
  int sayac = 0;
  for (int v = 0; v < n; v++)
    if (!ziyaret[v]) {   // yeni bileşen
      dfs(v, ziyaret);
      sayac++;
    }
  return sayac;
}

Bütün başlatmalar aynı ziyaret dizisini paylaştığı için her düğüm yalnız bir kez ziyaret edilir ve toplam zaman yine O(V + E)'dir. Dokuz düğümlü ve 0–1, 1–2, 3–4, 5–6, 6–7, 7–5 kenarlı bir çizgede metot 4 döndürür: bileşenler {0, 1, 2}, {3, 4}, {5, 6, 7} ve tek başına kalan {8}'dir. Her başlatmada ziyaret edilen düğümlere bir bileşen numarası yazılırsa “iki düğüm aynı bileşende mi?” sorusu sonradan O(1) zamanda yanıtlanır.

Aynı sayım yönlü çizgede bileşen sayısını vermez. Yönlü çizgede bir DFS'in ziyaret ettiği küme, başlangıç düğümünün seçimine bağlıdır. Kenarları 0→1, 2→0, 3→2, 5→4 olan altı düğümlü bir çizge alınsın. Düğümler 0'dan 5'e doğru denenirse DFS beş kez başlatılır: 0'dan yalnız 1'e ulaşılır, 2, 3, 4 ve 5 ayrı ayrı başlatılır. Düğümler 5'ten 0'a doğru denenirse iki başlatma yeter: 5'ten 4'e, 3'ten 2, 0 ve 1'e ulaşılır. Oysa bu çizgenin kenar yönleri göz ardı edildiğinde 2 bileşeni, güçlü bağlantılı bileşen olarak ise 6 bileşeni vardır. Yönlü çizgede doğru araç Tarjan ya da Kosaraju algoritmasıdır.

4.1.6.5İki parçalılık testi

Bir çizgenin iki parçalı olup olmadığını sınamak, düğümleri iki renge, komşu düğümler farklı renkte olacak biçimde boyamaya çalışmaktır. BFS bu boyamayı doğal olarak yapar: başlangıç bir renge, onun komşuları öteki renge, onların yeni komşuları yine ilk renge boyanır. Başka bir deyişle çift katmanlar bir renk, tek katmanlar öteki renk alır.

boolean ikiParcaliMi(int s) {
  Arrays.fill(renk, -1);
  renk[s] = 0; kuyruk.add(s);
  while (!kuyruk.isEmpty()) {
    int v = kuyruk.poll();
    for (int w : komsu[v])
      if (renk[w] == -1) {
        renk[w] = 1 - renk[v];
        kuyruk.add(w);
      } else if (renk[w] == renk[v])
        return false;  // aynı renk
  }
  return true;
}

renk[v] == -1 boyanmamış düğümdür. Boyanmamış komşu, 1 - renk[v] ile karşı renge boyanır ve kuyruğa eklenir; renk dizisi burada ziyaret dizisinin işini de görür. Boyanmış bir komşu v ile aynı renkteyse bir kenarın iki ucu aynı kümeye düşmüştür ve metot hemen false döndürür. Kuyruk sorunsuz boşalırsa boyama geçerlidir ve true döner. Metot yalnız s'nin bileşenini sınar; bütün çizge için her boyanmamış düğümden yeniden başlatılır.

İzlemenin çizgesi altı düğümlü ve yönsüzdür: kenarlar 0–1, 0–2, 1–3, 2–3, 3–4, 3–5, 4–5. Çizgede 0–1–3–2 döngüsü (dört kenar) ve 3–4–5 üçgeni (üç kenar) vardır.

0–1–3–2 döngüsü dört kenarlıdır ve boyamayı bozmaz: 0 ile 3 aynı renk, 1 ile 2 öteki renk alır. Sorun 3–4–5 üçgenindedir; üç kenarlık bir döngü iki renkle boyanamaz. 4–5 kenarı silinseydi metot true döndürürdü. Test bir BFS olduğu için O(V + E) zamanda çalışır.

4.1.6.6Döngü, köprü ve eklem noktası

Döngü tespiti iki çizge türünde farklı yapılır. Yönsüz çizgede DFS sırasında ziyaret edilmiş bir komşuya rastlanırsa ve bu komşu düğümün ebeveyni değilse bir döngü vardır. Ebeveyn istisnası gereklidir, çünkü yönsüz bir kenar iki yönde de listelenir ve çocuktan ebeveyne dönen kenar bir döngü değildir. Yönlü çizgede ise yalnız çağrı yığınındaki, yani sarı bir düğüme giden kenar döngü gösterir; işi bitmiş bir düğüme giden kenar döngü göstermez. DFS izlemesinde 2 → 0 kenarı sarı 0'a gidiyordu ve döngü belirtisiydi; 4 → 6 kenarı ise bitmiş 6'ya gidiyordu ve değildi.

Yönsüz bağlı bir çizgede silindiğinde çizgeyi ikiye bölen kenara köprü (bridge), silindiğinde çizgeyi bölen düğüme eklem noktası (articulation point) denir. Bir ağdaki köprüler ve eklem noktaları, tek bir arızanın ağı bölebileceği zayıf yerlerdir. İkisi de Tarjan'ın enDüşükBağ fikriyle tek bir DFS'te bulunur. Yönsüz çizgede keşif(v), v'nin keşif sırası; enDüşükBağ(w) ise w'nin alt ağacından tek bir geri kenarla ulaşılabilen en küçük keşif değeridir. DFS ağacındaki v–w kenarı (w çocuk) için:

• enDüşükBağ(w) > keşif(v) ise v–w bir köprüdür: w'nin alt ağacından v'ye ya da v'nin atalarına dönen bir geri kenar yoktur ve kenar silinince alt ağaç kopar.
• enDüşükBağ(w) ≥ keşif(v) ise v bir eklem noktasıdır (kök hariç; kök için iki ya da daha çok çocuğu olması koşulu aranır). Bu durumda alt ağaç en fazla v'ye dönebilir; v silinince yine kopar.

A–G harfli örnek çizgede tek köprü F–G'dir. DFS sırası A, B, D, C, E, F, G olduğundan keşif değerleri A 1, B 2, D 3, C 4, E 5, F 6, G 7'dir. G'nin tek komşusu F olduğu için enDüşükBağ(G) = 7 > keşif(F) = 6 olur ve F–G köprüdür. Öteki her kenar bir döngü üzerindedir; örneğin E–F kenarı, C–D–F–E döngüsünün parçasıdır ve silinse bile E'den F'ye C ve D üzerinden gidilebilir. F de bir eklem noktasıdır: silinirse G yalnız kalır.

4.1.6.7Yinelemeli derinleştirme ve rastgele yürüyüş

Yinelemeli derinleştirme (iterative deepening DFS, IDDFS), derinlik sınırı 0, 1, 2, … diye artırılan bir dizi DFS yapar. Her turda DFS, sınırdan daha derine inmez. Hedef ilk kez d sınırlı turda bulunursa en sığ çözüm d derinliktedir. Yöntem DFS'in az bellek kullanmasını BFS'in en sığ çözümü bulma güvencesiyle birleştirir. İlk bakışta üst katmanların her turda yeniden gezilmesi israf gibi görünür. Ama düğümlerin büyük çoğunluğu en derin katmandadır. Her düğümün 10 çocuğu olduğu bir ağaçta 5 derinliğe kadar BFS 111 111 düğüm ziyaret eder. IDDFS ise toplam 123 456 ziyaret yapar; fark yalnız yüzde on bir kadardır. Satranç ve bulmaca çözücüleri gibi devasa örtük çizgelerde bu yöntem yaygındır.

Rastgele yürüyüş (random walk), her adımda bulunulan düğümün komşularından birine rastgele geçer. Bir gezinme değildir, çünkü bütün düğümleri ziyaret etme güvencesi yoktur; ama çok büyük ağlarda örnekleme yapmanın ucuz bir yoludur. Bir web sayfasının PageRank değeri, web çizgesinde uzun süre rastgele yürüyen birinin o sayfada bulunma olasılığına dayanır.

4.1.7Sık yapılan hatalar

4.1.8Özet

• Çizge: G = (V, E), düğümler ve onları bağlayan kenarlar. Yönlü, yönsüz, ağırlıklı, iki parçalı, döngülü, tam çizge ve ağaç başlıca türlerdir. n düğümlü tam çizgede n(n − 1)/2 kenar vardır; yönsüz çizgede derecelerin toplamı 2E'dir.
• Gösterim: komşuluk listesi O(V + E), komşuluk matrisi O(V²) bellek ister. Gezinme listeyle O(V + E), matrisle O(V²) zaman alır. Seyrek çizgelerde liste tercih edilir.
• Gezinme: ulaşılabilen her düğümü tam bir kez ziyaret etmek. Döngüler yüzünden ziyaret dizisi şarttır. Bekleme listesi yığınsa DFS, kuyruksa BFS elde edilir.
• DFS: bir dalı sonuna kadar izler, sonra geri döner. Özyinelemeli sürümde geri dönüşü çağrı yığını yapar. Ziyaret sırası komşu sırasına bağlıdır; bir düğüme ilk ulaşılan kenarlar DFS ağacını oluşturur.
• Yığınla DFS: çekerken işaretler; bir düğüm yığına birden çok kez girebilir ve yığın O(E)'ye büyüyebilir. Komşular listedeki sırayla itilirse sıra özyinelemeli sürümün tersine döner. Derin çizgelerde StackOverflowError riskini ortadan kaldırır.
• BFS: kuyrukla katman katman ilerler; düğümü kuyruğa eklerken işaretler. uzaklik[] ve ata[] dizileriyle ağırlıksız çizgede en kısa yolları bulur; yol, ebeveynler hedeften geriye izlenerek kurulur. Ağırlıklı çizgede en kısa yolu bulmaz.
• Labirent: boş hücreler düğüm, bitişik boş hücreler kenardır. BFS bütün yolları eşzamanlı dener ve çıkışa ilk ulaştığında bulduğu yol en kısadır.
• Güçlü bağlantılı bileşen: karşılıklı ulaşılabilir düğümlerin maksimal kümesidir. Bileşenler düğümleri ayrık parçalara böler; bileşen çizgesi döngüsüzdür.
• Tarjan: indeks keşif sırasıdır; enDüşükBağ alt ağaçtan yığındaki düğümlere ulaşarak erişilen en küçük indekstir. enDüşükBağ(v) = indeks(v) ise v köktür ve yığından v'ye kadar çekilenler bir bileşendir. Bileşeni bulunmuş düğüme giden kenar yok sayılır. Zaman O(V + E)'dir; bileşenler ters topolojik sırada çıkar.
• Kosaraju: önce bitiş sırasını yığına kaydeden bir DFS, sonra ters çizgede yığın sırasıyla ikinci bir DFS. Her ikinci tur DFS'i bir bileşendir. Zaman yine O(V + E)'dir.
• Uygulamalar: topolojik sıra (Kahn ya da ters bitiş sırası; yazılan düğüm sayısı V'den azsa döngü vardır), bağlı bileşen sayısı, BFS ile iki renge boyayarak iki parçalılık testi, döngü tespiti, köprü ve eklem noktası, yinelemeli derinleştirme.

4.1.9Kavram listesi

• çizge graph
• düğüm vertex / node
• kenar edge
• yönlü çizge directed graph
• ağırlıklı çizge weighted graph
• iki parçalı çizge bipartite graph
• komşuluk listesi adjacency list
• komşuluk matrisi adjacency matrix
• çizge gezinme graph traversal
• derinlik öncelikli arama depth-first search (DFS)
• genişlik öncelikli arama breadth-first search (BFS)
• sözde kod pseudocode
• geri izleme backtracking
• geri kenar back edge
• ata ancestor
• ebeveyn parent
• en kısa yol shortest path
• bileşen connected component
• güçlü bağlantılı bileşen strongly connected component (SCC)
• topolojik sıralama topological sort

4.1.10Kendini Dene

1. Yönsüz bir çizgenin kenarları 0–1, 0–4, 1–2, 1–4, 2–3, 3–4, 3–5'tir; komşu listeleri artan sıradadır. dfs(0) ve bfs(0) ne yazdırır? BFS'e göre 0'dan 5'e en kısa yol hangisidir?

   Cevap

   Komşu listeleri 0: [1, 4], 1: [0, 2, 4], 2: [1, 3], 3: [2, 4, 5], 4: [0, 1, 3], 5: [3]'tür. DFS 0'dan 1'e, 2'ye, 3'e iner; 3'ün komşusu 2 işaretli olduğu için 4'e geçer. 4'ün bütün komşuları işaretlidir, 3'e dönülür ve 5 ziyaret edilir: 0 1 2 3 4 5. BFS önce 1 ve 4'ü, sonra 1'den 2'yi, 4'ten 3'ü, en son 3'ten 5'i keşfeder: 0 1 4 2 3 5. Uzaklıklar 0, 1, 2, 2, 1, 3'tür. 3'ü 2 değil 4 keşfeder, çünkü 4 kuyruktan 2'den önce çıkar. Ebeveynler izlenince en kısa yol 0–4–3–5 bulunur (3 kenar).

2. Yönlü çizge 0→1, 0→2, 1→3, 2→3, 3→4, 2→4 verilsin; komşu listeleri bu kenar sırasıyla dolar. dfsYigin(0) ne yazdırır ve kaç itme yapar? Özyinelemeli dfs(0) ne yazdırır?

   Cevap

   komsu[0] = [1, 2], komsu[2] = [3, 4]'tür. Yığınla DFS 0'dan sonra en son itilen 2'yi çeker; 2'den sonra en son itilen 4'ü, sonra 3'ü (3'ün komşusu 4 itilir, ama işaretlidir), en son 1'i yazar: 0 2 4 3 1. Toplam itme 1 + E = 7'dir. Özyinelemeli DFS 0 1 3 4 2 yazar. Yığınlı sürümde komşular ters sırada itilirse o da 0 1 3 4 2 yazar.

3. Yedi düğümlü yönsüz çizgenin kenarları 0–1, 0–2, 1–3, 2–3, 3–4, 5–6'dır. bfsUzaklik(0)'dan sonra uzaklik[] ne olur? yol(ata, 0, 4) ve yol(ata, 0, 6) ne döndürür?

   Cevap

   uzaklik = [0, 1, 1, 2, 3, −1, −1]; 5 ve 6 ulaşılamaz. ata[4] = 3, ata[3] = 1, ata[1] = 0 olduğundan yol(ata, 0, 4) [0, 1, 3, 4] döndürür. ata[6] = −1 olduğundan döngü yalnız 6'yı ekler; listenin ilk öğesi 0 değildir ve metot null döndürür. ata[] −1 ile doldurulmasaydı ata[6] = 0 kalır ve metot var olmayan [0, 6] yolunu döndürürdü.

4. Yönlü çizge 0→1, 1→2, 2→0, 2→3, 3→4, 4→5, 5→3, 4→6 verilsin (komsu[2] = [0, 3], komsu[4] = [5, 6]). scc(0) hangi satırları yazdırır? Her düğümün son indeks/dusuk değeri nedir?

   Cevap

   0, 1, 2, 3, 4, 5, 6 sırayla keşfedilir; indeksleri 1'den 7'ye kadardır. 2 → 0 kenarı dusuk[2]'yi 1'e, 5 → 3 kenarı dusuk[5]'i 4'e indirir. 6'nın çıkan kenarı yoktur ve ilk kök odur. Sonra 3 kök olur, en son 0. Çıktı üç satırdır: 6, 5 4 3, 2 1 0. Son değerler 0: 1/1, 1: 2/1, 2: 3/1, 3: 4/4, 4: 5/4, 5: 6/4, 6: 7/7'dir.

5. DAG 0→2, 1→2, 1→3, 2→4, 3→4, 4→5, 3→5 için Kahn algoritması ve ters bitiş sırası hangi sırayı verir? Çizgeye 5→1 kenarı eklenirse Kahn ne yazar?

   Cevap

   Başta 0 ve 1'in giriş derecesi 0'dır. Kahn 0 1 2 3 4 5 yazar: 0'dan sonra 2'nin derecesi 1'e iner, 1'den sonra 2 ve 3 hazır olur, 3'ten sonra 4, 4'ten sonra 5 hazır olur. DFS'te bitiş sırası 5, 4, 2, 0, 3, 1'dir; tersi 1 3 0 2 4 5'tir. 5→1 eklenince 1'in derecesi 1 olur. Kuyrukta yalnız 0 vardır; 0 yazılınca 2'nin derecesi 1'e iner ve kuyruk boşalır. Yalnız 0 yazılır; 6'dan az düğüm yazıldığı için çizgede döngü vardır (1 → 3 → 5 → 1).

6. Beş düğümlü bir halka (0–1–2–3–4–0) ile altı düğümlü bir halka (0–1–2–3–4–5–0) iki parçalı mıdır? ikiParcaliMi(0) ilkinde hangi kenarda false döndürür?

   Cevap

   Altı düğümlü halka iki parçalıdır: renkler 0, 1, 0, 1, 0, 1 sırasıyla değişir. Beş düğümlü halka tek uzunlukta bir döngüdür ve iki parçalı değildir. BFS 0'ı renk 0'a, 1 ve 4'ü renk 1'e, 2 ve 3'ü renk 0'a boyar. 2 kuyruktan alındığında komşusu 3 de renk 0'dadır: metot 2–3 kenarında false döndürür.

7. Beş düğümlü tam çizgede 0'dan BFS yapılıyor. Eklerken işaretleyen doğru sürüm ile çıkarırken işaretleyen sürüm kuyruğa kaçar ekleme yapar?

   Cevap

   Doğru sürüm her düğümü bir kez ekler: 5 ekleme. Çıkarırken işaretleyen sürümde 0 çıkınca 1, 2, 3, 4 eklenir; 1 çıkınca henüz işaretsiz 2, 3, 4 yeniden eklenir; 2 çıkınca 3 ve 4; 3 çıkınca 4. Toplam 1 + 4 + 3 + 2 + 1 = 11 ekleme yapılır ve kuyruk 7 öğeye ulaşır. Ziyaret sırası yine 0 1 2 3 4'tür, ama iş ve bellek boşa harcanmıştır.

8. V = 500 düğümlü, E = 2000 kenarlı yönsüz bir çizgede komşuluk listelerindeki toplam öğe sayısı ve komşuluk matrisinin hücre sayısı nedir? BFS'in yaklaşık iş miktarı iki gösterimde kaç kat farklıdır?

   Cevap

   Listelerde 2E = 4000 öğe, matriste V² = 250 000 hücre vardır. BFS listeyle yaklaşık V + 2E = 4500, matrisle V² = 250 000 adım yapar; oran yaklaşık 56'dır.

4.1.11İleri okuma

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (4. baskı, 2022), Bölüm 20: BFS ve DFS'i beyaz–gri–siyah renklendirmeyle, keşif ve bitiş zamanlarıyla, kenar sınıflandırmasıyla ve doğruluk ispatlarıyla verir; topolojik sıralama ve Kosaraju algoritması da buradadır.
• R. Sedgewick, K. Wayne, Algorithms (4. baskı, 2011), Kesim 4.1 ve 4.2: yönsüz ve yönlü çizgelerde gezinmeyi Java koduyla anlatır; labirent, bileşenler ve Kosaraju–Sharir algoritması için uygulamalı örnekler içerir.
• J. Kleinberg, É. Tardos, Algorithm Design (2006), Bölüm 3: BFS katmanlarını, iki parçalılık testini ve DAG'larda topolojik sıralamayı kısa ve okunaklı ispatlarla ele alır.
• R. E. Tarjan, “Depth-First Search and Linear Graph Algorithms” (1972): DFS'in doğrusal zamanlı çizge algoritmalarının temeli olduğunu gösteren ve enDüşükBağ fikrini tanıtan özgün makale.

4.1.12Kaynaklar

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022 (Bölüm 20: Elementary Graph Algorithms).
2. A. B. Kahn, “Topological Sorting of Large Networks”, Communications of the ACM 5(11), 1962.
3. J. Kleinberg, É. Tardos, Algorithm Design, Pearson, 2006 (Bölüm 3: Graphs).
4. R. Sedgewick, K. Wayne, Algorithms, 4. baskı, Addison-Wesley, 2011 (Bölüm 4.1–4.2).
5. R. E. Tarjan, “Depth-First Search and Linear Graph Algorithms”, SIAM Journal on Computing 1(2), 1972.

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