Bölüm 15: Çizgeler

15.1Giriş: köprüler, haritalar ve ağlar

Şimdiye kadarki veri yapılarında öğeler arasındaki ilişkinin bir biçimi vardı. Dizide ve bağlı listede her öğenin en çok bir öncesi ve bir sonrası bulunur. Ağaçta her düğümün tek bir ebeveyni vardır; çocuklar yukarıya dönmez. Gerçek dünyadaki pek çok ilişki bu kalıplara uymaz. Bir şehirden birçok yol çıkar ve bu yollar birbirine karışarak başka şehirlerde birleşir. Bir ağdaki bilgisayar birden çok bilgisayara bağlıdır; bağlantılar halkalar oluşturabilir. Böyle ilişkileri hiçbir kısıt koymadan tutan yapıya çizge (graph) denir.

15.1.1Königsberg'in yedi köprüsü

Çizge kuramının başlangıcı olarak 1736 yılı kabul edilir. Doğu Prusya'nın Königsberg şehri Pregel nehrinin iki yakasına kurulmuştu. Nehrin ortasında iki ada vardı. Şekil 15.1'in solundaki krokide adalar A ve D, kıyılar B (güney) ve C (kuzey) harfleriyle gösterilir. Bu dört kara parçası yedi köprüyle birbirine bağlanıyordu: A'dan C'ye iki, A'dan B'ye iki, A'dan D'ye bir, D'den C'ye bir ve D'den B'ye bir köprü.

Şehir halkının sorusu şuydu: Herhangi bir kara parçasından yola çıkıp her köprüden tam olarak bir kez geçerek başlanan yere dönülebilir mi? Deneme yanılmayla bir cevap bulunamıyordu. Leonhard Euler (“Oyler” diye okunur) soruyu çözmek için haritanın ayrıntılarını bir kenara bıraktı. Her kara parçasını bir nokta, her köprüyü iki noktayı birleştiren bir çizgi olarak çizdi. Noktalara bugün düğüm (vertex, node), çizgilere kenar (edge) denir. Ortaya çıkan çizim, şeklin sağındaki çizgedir. A ile C arasında iki ayrı kenar vardır, çünkü iki ayrı köprü vardır.

Bu soyutlamanın önemi şudur: Soruyu belirleyen, kara parçalarının büyüklüğü, köprülerin uzunluğu ya da nehrin kıvrımları değildir. Yalnız hangi parçanın hangisine kaç köprüyle bağlı olduğu önemlidir. Çizgede düğümlerin kâğıt üzerindeki yeri de önemsizdir; A düğümü sola ya da sağa çizilebilir. Aynı çizge birçok farklı biçimde çizilebilir. Çizim bir gösterimdir, çizgenin kendisi bağlantılardan ibarettir.

Euler soruyu bir sayıya bağladı. Bir düğüme değen kenarların sayısına o düğümün derecesi (degree) denir. Yürüyüş sırasında bir ara düğüme her girişte o düğümden bir de çıkılır. Giriş ve çıkış farklı köprülerden yapılmak zorundadır. Öyleyse her uğrayışta düğümün iki kenarı harcanır. Başlangıç düğümü de aynı durumdadır: yürüyüş ondan çıkar ve sonunda ona girer. Bütün köprüleri birer kez kullanan ve başa dönen bir yürüyüşte her düğümün kenarları ikişer ikişer tükenmelidir. Bu nedenle böyle bir yürüyüş ancak her düğümün derecesi çiftse bulunabilir. Königsberg'de dereceler 5, 3, 3 ve 3'tür; dördü de tek sayıdır. Aranan yürüyüş yoktur.

Euler'in vardığı sonuç bugün onun adıyla anılır. Bağlantılı bir çizgede her kenardan bir kez geçip başa dönen yürüyüşe Euler devresi denir. Böyle bir devre, ancak ve ancak bütün dereceler çiftse vardır. Koşulun gerekli olduğu yukarıdaki sayma kanıtından çıkar. Yeterli olduğunun kanıtı daha uzundur ve çizge kuramı derslerinin konusudur. Bu notta önemli olan, bir şehir haritası sorusunun yalnızca sayılar ve bağlantılar üzerinden cevaplanabilmesidir.

15.1.2Çizgeler nerelerde kullanılır

Königsberg'den bu yana çizgeler hemen her mühendislik alanına girdi. Kullanımları o kadar geniştir ki çizgenin kullanılmadığı bir alan bulmak, kullanıldığı alanları saymaktan zordur. Tablo 15.1 başlıca örnekleri toplar.

Tablodaki soruların bir kısmı adlarıyla bilinen klasik problemlerdir. En kısa yol problemi bir haritada iki şehir arasındaki en ucuz güzergâhı arar. En büyük akış (max flow) problemi bir boru ağından birim zamanda en çok ne kadar petrol ya da su taşınabileceğini sorar. Minimum kapsayan ağaç (minimum spanning tree) problemi bütün köyleri birbirine en az toplam kablo uzunluğuyla bağlamak ister. Ağaçların kendileri de birer çizgedir; topolojik sıralama ve sonlu özdevinirler (finite automata) da çizge üzerinde tanımlanır. Bu problemlerin hepsi aynı temel üzerine kurulur: çizgenin bellekte nasıl tutulacağı ve üzerinde nasıl gezinileceği. Bu not tam olarak bu temeli kurar.

15.2Tanımlar ve terimler

Çizgeyle ilgili her yordam birkaç temel kavrama dayanır. Bu kesim onları kesin biçimde tanımlar ve notun geri kalanında kullanılacak örnek çizgeleri tanıtır.

15.2.1Çizgenin tanımı

Düğüm kümesinin boş olmaması bir gerekliliktir: düğümsüz bir çizge üzerinde hiçbir işlem anlamlı değildir. Kenar kümesi ise boş olabilir. Tek bir düğümden oluşan ya da birbirine hiç bağlı olmayan düğümlerden oluşan çizgeler de geçerlidir. Aşağıdaki seyrek çizge örneğinde 11 düğümün 7'si hiçbir kenara değmez.

Kenarın iki ucunun sırası önemliyse çizge yönlüdür (directed graph, digraph); önemsizse yönsüzdür (undirected graph). Gösterimde bu fark parantez biçimiyle verilir:

• Yönsüz çizgede kenar sıradan bağımsız bir çifttir ve normal parantezle yazılır: (v0, v1) ile (v1, v0) aynı kenardır.
• Yönlü çizgede kenar sıralı bir çifttir ve açılı parantezle yazılır: <v0, v1> ≠ <v1, v0>. Okun çıktığı ilk düğüme kuyruk (tail), okun saplandığı ikinci düğüme baş (head) denir: <kuyruk, baş>.

Kenar kümesi, düğüm kümesinin kendisiyle kartezyen çarpımı V × V'nin bir alt kümesidir. Bu çarpım bütün sıralı ikilileri içerir; çizge bunlardan yalnız bazılarını seçer. Seçilen ikililer, hangi düğümün hangisine bağlı olduğunu söyler.

Not boyunca dört küçük örnek çizge kullanılır. Şekil 15.2 onları çizer, Tablo 15.2 de düğüm ve kenar kümelerini yazar.

G3'ün kenar kümesinde <0,1> ile <1,0> ayrı ayrı yazılır. Yönlü çizgede bunlar iki farklı kenardır; birinin varlığı ötekini gerektirmez. Yönsüz bir çizgede ise (0,1) yazmak yeter; (1,0) aynı kenarın öteki yazılışıdır.

Bu notta aksi söylenmedikçe çizgeler basittir: iki düğüm arasında en çok bir kenar bulunur ve hiçbir kenar bir düğümü kendisine bağlamaz. Düğümü kendisine bağlayan kenara öz döngü (self-loop) denir. Königsberg çizgesi basit değildir; A ile C arasında iki kenar vardır. Böyle çizgelere çoklu çizge (multigraph) denir.

15.2.2Komşu düğüm ve alt çizge

G1'de her düğüm öteki üçüyle komşudur. G2'de 0'ın komşuları 1 ile 2'dir; 3 ile 4 birbirine komşu değildir, çünkü aralarında kenar yoktur. İkisi de 1'e komşudur, ama bu onları birbirine komşu yapmaz.

Tanımın gizli bir koşulu vardır: G′ kendi başına bir çizge olmalıdır. Yani E(G′)'deki her kenarın iki ucu da V(G′)'de bulunmalıdır. Uçlarından biri seçilmemiş bir kenar alt çizgeye giremez. Kenar kümesi boş olabildiği için tek bir düğüm de geçerli bir alt çizgedir.

Bir çizgenin kaç alt çizgesi olduğu hızla büyür. G1'in yalnız kenar seçimleri için 2⁶ = 64 olasılık vardır, üstelik düğüm seçimleri de eklenir. Şekil bunlardan yalnız birkaçını gösterir.

15.2.3Yol, bağlantılılık ve derece

G2'de 3, 1, 0, 2, 5 dizisi 3'ten 5'e uzunluğu 4 olan bir yoldur. Bütün düğümleri birbirinden farklı olan yola basit yol denir. İlk ve son düğümü aynı olan, başka bir düğümü yinelenmeyen ve en az bir kenar içeren yola döngü (cycle) denir. G1'de 0, 1, 2, 0 bir döngüdür. G2 bir ağaç olduğu için hiç döngü içermez. Yönsüz basit çizgede bir döngü en az üç kenar içerir; 0, 1, 0 dizisi aynı kenardan gidip geri döner ve döngü sayılmaz.

G1 ve G2 bağlantılıdır. G4 bağlantılı değildir: 0'dan 5'e hiçbir yol yoktur. G4 iki ayrı parçadan oluşur. Bu parçalara bağlantılı bileşen denir; bileşenler bu notun son kesiminde ayrıntılı olarak ele alınır.

Yönsüz örneklerde G2'de d(0) = 2, G1'de d(1) = 3, G2'de d(4) = 1'dir. Yönlü G3'te her düğümün iki sayısı ayrı ayrı hesaplanır (Tablo 15.3).

Derece her zaman belirli bir düğüm için söylenir. “G3'ün derecesi 2'dir” gibi bir cümlenin anlamı yoktur; doğru ifade “G3'te 0 düğümünün derecesi 2'dir” biçimindedir. Bir çizge için söylenebilecek olanlar en büyük derece ya da derecelerin toplamıdır.

15.2.4Derecelerin toplamı

Derece ile kenar sayısı arasında basit ama çok kullanılan bir ilişki vardır.

Kanıt kenarların ayrı ayrı sayılmasına dayanır; iki düğüm arasında birden çok kenar olması bir şey değiştirmez. Teorem bu yüzden çoklu çizgelerde de geçerlidir. Königsberg çizgesinde 5 + 3 + 3 + 3 = 14 = 2 · 7'dir. Öz döngüye izin verilirse böyle bir kenar düğümün derecesine 2 katkı yapacak biçimde sayılır ve teorem yine bozulmaz.

Şekil 15.5 teoremi G1 üzerinde adım adım gösterir. Kenarlar boş bir çizgeye birer birer eklenir. Her eklemede iki ucun derecesi birer artar ve toplam 2 büyür. Altı kenar eklendiğinde toplam 12'ye varır.

Teoremin hemen çıkan bir sonucu vardır: Bir çizgede derecesi tek olan düğümlerin sayısı çifttir. Toplam 2e çift olduğuna göre tek terimlerin sayısı tek olamaz. Bu sonuç “şu derecelere sahip bir çizge var mı?” sorusuna hızlı bir ön cevap verir.

Teoremin veri yapısı açısından önemi de büyüktür. Yönsüz bir çizgenin komşuluk listesinde her kenar iki kez, bir ucunun listesinde ve öteki ucunun listesinde, görünür. Listelerdeki toplam öğe sayısı derecelerin toplamıdır, yani 2e'dir. Bütün listeleri tarayan bir yordamın maliyeti bu nedenle O(n + e) olur. Bu cümle aşağıdaki analizlerin neredeyse hepsinde yeniden karşılaşılan bir akıl yürütmedir.

15.3Çizgeyi bellekte gerçeklemek

Kavramlar kâğıt üzerinde çizilerek anlaşılır, ama program çizimi göremez. Bir program için çizge, bellekteki sayılardan ve işaretçilerden ibarettir. Bu kesimin konusu ayrık matematik değildir; konusu, “çizgeyi bellekte nasıl tutarız?” sorusudur. Aynı çizge için birçok gösterim vardır ve aralarındaki seçim, çizge üzerinde yapılacak işlemlerin hızını belirler. Burada beş gösterim ele alınır:

1. komşuluk matrisi,
2. komşuluk listesi ve onun tersi,
3. tek dizi ile sıralı gösterim,
4. yönlü çizgeler için ortogonal liste,
5. çok bağlı liste.

Bunlara kenarlara maliyet ekleyen ağırlıklı gösterim eklenir. Her gösterim için üç soru sorulur: Ne kadar bellek ister? “u ile v arasında kenar var mı?” sorusu ne kadar sürede cevaplanır? Bir düğümün bütün komşuları ne kadar sürede bulunur? Gezinme gibi algoritmaların hızı en çok bu son soruya bağlıdır.

15.3.1Komşuluk matrisi

C'de matris, en çok düğüm sayısına göre boyutlanmış bir tamsayı dizisiyle tutulur: int a[MAX_DUGUM][MAX_DUGUM];. Tablo 15.4 G1 ile G3'ün matrislerini yan yana verir.

G1'de (0,2) bir kenar olduğu için hem a[0][2] hem a[2][0] 1'dir. Yönsüz çizgenin her kenarı matrise iki kez, köşegene göre simetrik iki hücreye yazılır. Bu yüzden yönsüz çizgenin matrisi simetriktir: her i, j için a[i][j] = a[j][i]. Basit çizgede öz döngü olmadığından köşegen tamamen sıfırdır. G3'ün matrisi ise simetrik değildir: a[1][2] = 1 ama a[2][1] = 0.

Simetri yer kazanmak için kullanılabilir. Matrisin yalnız alt ya da üst üçgeni saklanırsa hücre sayısı yaklaşık yarıya iner. Ama bellek yine de n(n − 1)/2 hücreyle orantılıdır; asimptotik olarak O(n²) değişmez. Matrisin belleği kenar sayısına hiç bağlı değildir: hiç kenarı olmayan bir çizge de, tam çizge de aynı yeri kaplar. 50 düğümlük bir int matrisi, 4 baytlık int ile 10 000 bayt tutar.

Matrisle iki işlem çok kolaydır. (u, v) kenarının varlığı tek bir hücreye bakılarak O(1)'de öğrenilir. Kenar eklemek ya da silmek de bir hücreye 1 ya da 0 yazmaktır, yine O(1). Öteki işlemler satırları taramayı gerektirir:

• Derece. Yönsüz çizgede i'nin derecesi i. satırdaki 1'lerin sayısıdır (ya da aynı anlama gelen i. sütundakilerin). Satırda n hücre olduğu için maliyet O(n)'dir. Yönlü çizgede satır toplamı çıkış derecesini, sütun toplamı giriş derecesini verir; ikisi birlikte 2n hücre okur ve maliyet yine O(n) olur. G3'te 2'nin çıkış derecesi 0 (satır 2 boş), giriş derecesi 1'dir (sütun 2'de bir tane 1).
• Kenar sayısı. Bütün 1'ler sayılıp ikiye bölünür (Teorem 15.1). G1'de 12 tane 1 vardır; kenar sayısı 6'dır. Simetri yüzünden yalnız üst üçgene bakmak yeter, ama bu n(n − 1)/2 hücre demektir. Maliyet O(n²)'den aşağı inmez.
• Bir düğümün komşuları. Satırın n hücresi taranır: O(n). Düğümün tek komşusu olsa bile bütün satır okunur.

Son madde gezinme algoritmalarının maliyetini belirler ve matrisin asıl zayıflığıdır. Seyrek bir çizgede satırların çoğu sıfırdır, ama sıfırları atlamanın bir yolu yoktur.

G4'ün matrisi ve simetri denetimi

Matris elle yazılırken en sık hata, bir kenarı yalnız tek yönde işlemektir. Şekil 15.6 G4'ü, Tablo 15.5 doğru matrisini verir.

Matris bağlantılı bileşenleri bulmak için de kullanılabilir. Bunun için bir düğümden başlayıp ulaşılabilen bütün düğümler işaretlenir; işaretsiz kalan ilk düğümden yeniden başlanır. Ama her düğümün komşularını bulmak bir satır taraması, yani O(n) olduğundan toplam maliyet O(n²)'dir. Aynı iş komşuluk listesiyle çok daha ucuzdur.

Matriste derece: kod ve izleme

Yönlü bir çizgede bir düğümün derecesini hesaplayan yordam, satırı ve sütunu ayrı ayrı toplar:

int derece(int a[][MAX_DUGUM], int n, int v)
{
    int j, cikis = 0, giris = 0;
    for (j = 0; j < n; j++)
        cikis += a[v][j];      /* satir  */
    for (j = 0; j < n; j++)
        giris += a[j][v];      /* sutun */
    return cikis + giris;
}

• Satır 1. İki boyutlu dizi parametre olarak geçirilirken ikinci boyut yazılmak zorundadır: int a[][MAX_DUGUM]. Derleyici a[v][j]'nin adresini v · MAX_DUGUM + j ile hesaplar ve bunun için satır uzunluğunu bilmelidir. Birinci boyut boş bırakılabilir. n gerçek düğüm sayısıdır; dizinin yalnız sol üst n × n bölümü kullanılır.
• Satır 3. İki sayaç sıfırlanır. Başlangıç değeri unutulursa yerel değişkenler belirsiz değerle başlar ve sonuç rastgele olur.
• Satır 4–5. v. satır taranır: a[v][j], <v, j> kenarı varsa 1'dir. Toplam çıkış derecesidir.
• Satır 6–7. v. sütun taranır: a[j][v], <j, v> kenarı varsa 1'dir. Toplam giriş derecesidir.
• Satır 8. İkisinin toplamı döndürülür.

Yordam yönsüz bir çizgeye uygulanırsa satır ve sütun aynı olduğundan her kenar iki kez sayılır ve derecenin iki katı döner. Yönsüz çizgede yalnız ilk döngü yeter. Tablo 15.6 derece(a, 3, 1) çağrısını G3 matrisi üzerinde izler.

Her döngü tam n kez döner; toplam 2n hücre okunur. Maliyet O(2n) = O(n)'dir ve düğümün gerçek derecesinden bağımsızdır. Aynı yordam G3'ün öteki düğümleri için 2 (düğüm 0) ve 1 (düğüm 2) döndürür; bu değerler Tablo 15.3 ile örtüşür.

15.3.2Komşuluk listesi

Matrisin her satırı çoğunlukla sıfırlarla doludur. Komşuluk listesi bu sıfırları hiç saklamaz. Matrisin her satırı yerine bir bağlı liste tutulur ve listede yalnız 1 olan sütunların numaraları bulunur.

C bildirimi kendine başvuran bir yapıyla yapılır:

#define MAX_DUGUM 50   /* en fazla dugum sayisi */
typedef struct oge *oge_gost;
typedef struct oge {
    int dugum;         /* komsu dugumun numarasi */
    oge_gost bag;      /* listedeki sonraki komsu */
} oge;                 /* ';' ve typedef adi unutulmamali */
oge_gost baslik[MAX_DUGUM];   /* her dugume bir liste */

• Satır 1. MAX_DUGUM, programın tutabileceği en çok düğüm sayısıdır. Dizi boyutları bu sabitle belirlenir.
• Satır 2. oge_gost, henüz tanımı yazılmamış struct oge'yi gösteren işaretçi tipidir. C'de bir yapının işaretçisi, yapının tanımından önce bildirilebilir; yapının boyutunun bilinmesi gerekmez. Bu sıra, yapının içinde kendi tipini gösteren bir alan kullanmayı kolaylaştırır.
• Satır 3–6. Her liste öğesi iki alan taşır: komşunun numarası dugum ve listedeki sonraki öğeyi gösteren bag. Tanım } ve tip adı oge'den sonra ; ile biter. Noktalı virgül unutulursa derleyici hatayı çoğunlukla sonraki satırda bildirir ve hatanın yeri şaşırtıcı görünür.
• Satır 7. baslik dizisi her düğüme bir liste başı ayırır. Küresel bir dizi olduğu için bütün öğeleri program başlarken NULL'dır; yani başta her liste boştur.

Şekil 15.8'de her düğümün üç komşusu vardır ve her liste üç öğelidir. Toplam 12 öğe bulunur; G1'in 6 kenarı vardır. Yönsüz çizgede her kenar iki ucunun listesinde birer kez görünür. Bu, gösterimin bir dezavantajıdır: aynı bilgi iki yerde saklanır ve kenar silinirken iki listenin de güncellenmesi gerekir.

Listelerin bellek ve zaman maliyetleri şöyledir:

• Bellek. n başlık ve yönsüz çizgede 2e öğe: O(n + e). x86-64 üzerinde bir oge 16 bayttır (4 baytlık int, 4 bayt dolgu, 8 baytlık işaretçi); bir başlık 8 bayttır.
• Derece. Yönsüz çizgede i'nin listesindeki öğeler sayılır: O(d_i). Matristeki O(n)'e göre derece küçükse büyük kazançtır.
• Kenar sayısı. Bütün listelerdeki öğeler sayılır ve ikiye bölünür: n başlığa bakmak ve 2e öğeyi saymak gerekir, toplam O(n + e). Matristeki O(n²)'den çok daha azdır, çünkü e çoğu çizgede n²'den çok küçüktür.
• (u, v) var mı? u'nun listesinde v aranır: O(d_u). Matriste bu soru O(1)'di; listenin kaybettiği tek yer burasıdır.

Çizge algoritmalarında karmaşıklık bu yüzden çoğunlukla hem n'ye hem e'ye bağlı yazılır. “O(n + e)” ifadesi, her düğüme ve her kenara sabit sayıda kez dokunan bir algoritmayı anlatır.

Yönsüz ve yönlü örnekler

Yönsüz G4'ün listeleri sıralı tutulursa kenarları saymak biraz kısalır. Her (i, j) kenarı hem i'nin hem j'nin listesinde bulunur. Yalnız j > i olan öğeler sayılırsa her kenar bir kez sayılır ve ikiye bölmeye gerek kalmaz. Sıralı listede j < i olan öğeler başta toplanır, örneğin 3'ün listesindeki 1 ve 2. Bu öğeler hızla geçilir, kalanlar sayılır. Taranan öğe sayısı azalır, ama asimptotik maliyet yine O(n + e)'dir.

Yönlü G3'te durum farklıdır. <0,1> ile <1,0> ayrı kenarlar olduğundan her öğe bir kenardır ve hepsi sayılmalıdır. Liste yalnız çıkan kenarları tutar: baslik[i]'deki öğe sayısı i'nin çıkış derecesidir ve O(d)'de bulunur. Giriş derecesi ise listede doğrudan yazmaz. i'ye gelen kenarları bulmak için bütün listeleri gezip i'yi içeren öğeleri saymak gerekir: O(n + e). Giriş derecesi sık soruluyorsa bu maliyet kabul edilemez. Çözüm, listenin tersini, yani gelen kenarların listesini de tutmaktır. Bu ters liste (inverse adjacency list) bir sonraki alt kesimde kurulur.

Seyrek bir çizge: G5

Matris ile liste arasındaki farkı en iyi seyrek bir çizge gösterir. G5'in 11 düğümü ve yalnız 2 kenarı vardır: (1, 4) ve (7, 8).

Komşuluk listesinde dört öğe bulunur: baslik[1] → 4, baslik[4] → 1, baslik[7] → 8 ve baslik[8] → 7. Kalan yedi başlık NULL'dır. Toplam 11 başlık ve 2e = 4 öğe tutulur. Matris ise 11 × 11 = 121 hücre ister; bunların yalnız 4'ü 1'dir ve 117 hücre boşa gider.

Buradan genel bir kural çıkar: seyrek çizgede (e, n²'ye göre küçükse) liste, yoğun çizgede (e, n²'ye yakınsa) matris düşünülür. Yoğun bir çizgede listenin işaretçileri matrisin bitlerinden çok daha fazla yer tutar. Ama karar yalnız yoğunluğa göre verilmez. Asıl ölçüt, çizge üzerinde yapılacak işlemlerdir. Program sürekli “bu iki düğüm komşu mu?” diye soruyorsa seyrek çizgede bile matris daha hızlı olabilir. Program her düğümün komşularında geziniyorsa yoğun bir çizgede bile liste daha uygun olabilir.

15.3.3Listeyi kurmak: kenar ekleme

Örneklerdeki listeleri bir kişi çizgeye bakarak çizdi. Program ise çizgeye bakamaz. Kenarlar programa bir dosyadan ya da kullanıcıdan birer birer gelir ve her biri geldiği anda yapıya eklenebilmelidir. Bu işi yapan yordam şudur:

void kenar_ekle(int u, int v)   /* u -> v */
{
    oge_gost p = malloc(sizeof(oge));
    if (p == NULL) exit(1);       /* bellek yok */
    p->dugum = v;
    p->bag = baslik[u];   /* basa ekle: O(1) */
    baslik[u] = p;
}

• Satır 1. Yordam u → v yönünde tek bir kenar ekler: u'nun listesine v'yi koyar. Yönsüz bir (u, v) kenarı için yordam iki kez, kenar_ekle(u, v) ve kenar_ekle(v, u) biçiminde çağrılır.
• Satır 3. Yeni öğe için heap bellekten yer alınır. malloc'un döndürdüğü void *, C'de dönüşüm yazmadan oge_gost'a atanabilir. sizeof(oge) yerine sizeof(oge_gost) yazmak sık bir hatadır: işaretçinin boyutu kadar (8 bayt) yer alınır, oysa öğe 16 bayttır ve sonraki atamalar ayrılmamış belleğe yazar.
• Satır 4. malloc bellek bulamazsa NULL döndürür. Denetim yapılmazsa bir sonraki satır NULL işaretçi üzerinden yazar ve program çöker. Burada en basit tepki seçilmiştir: program bir hata koduyla sonlanır.
• Satır 5. Komşu numarası öğeye yazılır.
• Satır 6. Yeni öğenin bağı, listenin şimdiki ilk öğesini gösterir. Liste boşsa bu değer NULL'dır ve yeni öğe listenin son öğesi de olur.
• Satır 7. Liste başı yeni öğeyi gösterir. Satır 6 ile 7'nin sırası önemlidir: önce 7 yazılsaydı eski liste başı kaybolur ve listenin geri kalanına ulaşılamazdı.

Yordam listeyi taramaz; her kenar sabit sayıda adımda, O(1)'de yerleşir. e kenarlı yönsüz bir çizge 2e çağrıyla kurulur; başlıkların sıfırlanması da eklenince kurulum O(n + e) sürer.

Tablo 15.7, kenarlar (0,1), (0,2), (1,2) sırasıyla geldiğinde listelerin nasıl oluştuğunu izler. Tabloda &oge(k), komşu numarası k olan öğenin adresini gösterir.

Sonuçta 0'ın listesi 2 → 1'dir; kenarlar 1, 2 sırasıyla gelmiştir. Başa ekleme, listeyi gelen sıranın tersine çevirir. Bu durum bir hata değildir, ama gezinme algoritmalarının çıktısını etkiler; çünkü gezinme komşuları listedeki sırayla ziyaret eder. Liste sırası değişince gezinme sırasının da değiştiği, gezinme kesimindeki örneklerde açıkça görülür.

Başa, sona ya da sıralı ekleme

Bir öğe listeye üç yerden girebilir. Seçim, istenen sıraya ve maliyete bağlıdır (Tablo 15.8).

Sıralı listeler çizgenin hangi sırayla kurulduğundan bağımsızdır; gezinme çıktısı yalnız çizgeye bağlı olur. Notun izleme örneklerinde listeler bu yüzden sıralıdır. Sıralı ekleme, bağlı listelerdeki işaretçinin işaretçisi tekniğiyle kısa yazılır:

void sirali_ekle(int u, int v)   /* u listesine v, artan sirada */
{
    oge_gost *pp = &baslik[u];   /* isaretcinin isaretcisi */
    oge_gost p;
    while (*pp && (*pp)->dugum < v)
        pp = &(*pp)->bag;
    p = malloc(sizeof(oge));
    if (p == NULL) exit(1);
    p->dugum = v;
    p->bag = *pp;
    *pp = p;
}

pp, değiştirilecek işaretçi alanının adresini tutar. Başta bu alan baslik[u]'dur. Döngü, v'den küçük öğeleri geçerken pp'yi her öğenin bag alanına ilerletir. Döngü bittiğinde *pp, yeni öğenin önüne gireceği öğeyi (ya da NULL'u) gösterir. Yeni öğe *pp'nin yerine yazılır. Listenin başına, ortasına ve sonuna ekleme aynı iki satırla yapılır; “liste boş mu, başa mı ekleniyor” gibi özel durumlar gerekmez.

Belleği geri vermek

Her malloc çağrısının karşılığında bir free çağrısı bulunmalıdır. Program sonunda ya da çizge artık gerekmediğinde her baslik[i] listesi gezilerek öğeler serbest bırakılır:

void listeleri_birak(oge_gost bas[], int n)
{
    int i;
    oge_gost p;
    for (i = 0; i < n; i++) {
        while (bas[i]) {
            p = bas[i];
            bas[i] = p->bag;   /* once bag saklanir */
            free(p);
        }
    }
}

Döngünün içindeki sıra bağlı listelerden bilinen kuraldır: öğe serbest bırakılmadan önce bağı saklanır. free(p) sonrasında p->bag'i okumak serbest bırakılmış belleğe erişmektir ve tanımsız davranıştır. Yordam her öğeye bir kez dokunur: O(n + e). Notun bütün C kodları sayaçlı bir malloc/free sarmalayıcısıyla çalıştırıldı; listeler bu yordamla bırakıldığında ayrılan ve geri verilen blok sayıları eşitti.

15.3.4Ters komşuluk listesi

Yönlü çizgede komşuluk listesi çıkan kenarları tutar. Ters liste ise gelen kenarları tutar: ters[j], j'ye kenar gönderen düğümlerin listesidir. Bu, çizgenin bütün oklarının ters çevrildiği transpoz çizgenin komşuluk listesidir. Ters liste, mevcut listeleri bir kez gezerek kurulur:

void devrik_kur(oge_gost bas[], oge_gost ters[],
               int n)
{
    int i;
    oge_gost p;
    for (i = 0; i < n; i++) ters[i] = NULL;
    for (i = 0; i < n; i++)
        for (p = bas[i]; p; p = p->bag)
            ekle(ters, p->dugum, i);  /* <j,i> */
}

Yordamın kullandığı ekle, kenar_ekle'nin herhangi bir başlık dizisi üzerinde çalışan biçimidir:

void ekle(oge_gost bas[], int u, int v)   /* bas[u] listesine v */
{
    oge_gost p = malloc(sizeof(oge));
    if (p == NULL) exit(1);
    p->dugum = v;
    p->bag = bas[u];
    bas[u] = p;
}

• Satır 6. Ters listenin bütün başlıkları NULL yapılır.
• Satır 7–8. Her i düğümünün listesi baştan sona gezilir. Listede j numaralı bir öğe <i, j> kenarı demektir.
• Satır 9. Bu kenar ters çizgede <j, i> olur: ters[j] listesine i eklenir. Açıklama satırındaki <j,i> bunu söyler.

Dış döngü n kez döner; iç döngüler toplamda her öğeye bir kez bakar. Her ekle çağrısı O(1)'dir. Ters liste bu yüzden O(n + e)'de kurulur. Kurulduktan sonra giriş derecesi de ters[i]'deki öğeleri saymakla, O(d)'de bulunur. Bedeli bellektir: her kenar iki kez, bir kez çıkış listesinde, bir kez giriş listesinde saklanır.

15.3.5Dizi ile sıralı gösterim

Komşuluk listesinin her öğesi bir işaretçi taşır. 64 bitlik bir makinede bu işaretçi, 4 baytlık komşu numarasının iki katı yer tutar. Çizge hiç değişmeyecekse işaretçilerden tümüyle kurtulmak mümkündür: bütün listeler tek bir diziye art arda yazılır.

Dizinin iki bölümü vardır. Baştaki n + 1 hücre bir içindekiler tablosu gibidir: dugum[i], i'nin komşularının dizide nereden başladığını söyler. Arkadaki 2e hücre komşu numaralarının kendisidir; düğümlerin listeleri sırayla, aralarında boşluk bırakılmadan yazılır. i'nin komşuları bir sonraki düğümün listesinin başladığı yerde biter. Son düğümün de bir bitiş sınırı olması için fazladan bir hücre, dugum[n], eklenir. Bu yüzden hücre sayısı n + 1 + 2e'dir.

G4 için n = 8 ve e = 7'dir; dizi 8 + 14 + 1 = 23 hücrelidir. Komşu kayıtları 9. indisten başlar. 0'ın iki komşusu 9 ve 10. hücrelere, 1'in iki komşusu 11 ve 12. hücrelere yazılır; bu böyle sürer. Tablo 15.10 diziyi okumayı örneklerle gösterir.

Bir düğümün komşularını yazan yordam iki sınır arasında yürür:

void komsulari_yaz(const int dugum[], int i)
{
    int k;
    for (k = dugum[i]; k < dugum[i + 1]; k++)
        printf("%d ", dugum[k]);
    printf("\n");
}

Dizi const int dugum[] olarak alınır; yordam diziyi yalnız okur ve derleyici yanlışlıkla yazılmasını engeller. Döngü değişkeni k, dugum[i]'den başlar ve dugum[i + 1]'e varmadan durur. Tablo 15.11 komsulari_yaz(dugum, 5) çağrısını izler.

Döngü düğümün derecesi kadar döner: O(d). Derecenin kendisi döngüye bile gerek kalmadan dugum[i+1] − dugum[i] farkıyla, O(1)'de bulunur. Bellek n + 2e + 1 tamsayıdır ve hiç işaretçi yoktur. G4 için 23 tamsayı, yani 92 bayt yeter. Aynı çizgenin komşuluk listesi 8 başlık (64 bayt) ve 14 öğe (224 bayt) ister.

Dizi var olan listelerden tek geçişte kurulabilir:

int sirali_kur(int dugum[], int n)   /* listelerden tek dizi */
{
    int i, k = n + 1;                /* komsular n+1'den baslar */
    oge_gost p;
    for (i = 0; i < n; i++) {
        dugum[i] = k;                /* i'nin ilk komsusunun yeri */
        for (p = baslik[i]; p; p = p->bag)
            dugum[k++] = p->dugum;
    }
    dugum[n] = k;                    /* son dugumun bitis siniri */
    return k;                        /* kullanilan hucre: n + 2e + 1 */
}

Yordam her düğüm için önce başlangıç indisini yazar, sonra listesindeki komşuları sıradaki boş hücrelere kopyalar. Döngü bitince k, kullanılan hücre sayısına, yani n + 2e + 1'e eşittir. Bu değer dugum[n]'e yazılarak son düğümün sınırı konur. G4'ün sıralı listelerine uygulandığında Şekil 15.13'teki dizinin aynısını üretir.

Gösterimin bedeli değişikliktir. Yeni bir kenar eklemek, iki listeye birer hücre açmak demektir. Bu da arkadaki bütün hücreleri kaydırmayı ve kaydırılan düğümlerin başlangıç indislerini güncellemeyi gerektirir: O(n + e). Çok sayıda ekleme ve silme yapılan bir çizge için bu yapı verimli değildir. Depolamak ayrı bir konudur, saklanan veri üzerinde çalışacak algoritmaların etkinliği ayrı bir konudur. Örneğin bir binadaki bilgisayar ağı neredeyse hiç değişmez. Problem yalnız bu ağı tutup üzerinde sorgu yapmaksa sıralı gösterim hem az yer kaplar hem de bellekte bitişik durduğu için hızlı okunur. Seyrek matrislerdeki sıkıştırılmış satır gösterimi (CSR) aynı fikrin matrise uygulanmış biçimidir.

15.3.6Yönlü çizgelerin ortogonal gösterimi

Yönlü çizgede hem çıkış hem giriş derecesi sık soruluyorsa komşuluk listesi ile tersini birlikte tutmak gerekir. Bu durumda her kenar iki öğeyle, toplam 2e öğeyle saklanır. Ortogonal gösterim her kenarı tek bir öğede tutar ve bu öğeyi aynı anda iki listeye bağlar.

Gösterimin adı yapının görünüşünden gelir: öğeler bir matrisin dolu hücreleri gibi satır ve sütunlara dizilir. Bir düğümün satırında gezinmek o düğümden nereye çıkıldığını, sütununda gezinmek o düğüme nereden gelindiğini verir. Aynı kenar için tek öğe yeter. G3'te <1,0> öğesi hem 1'in satırında hem 0'ın sütunundadır.

Bu yapı seyrek matrislerin bağlı gösterimine çok benzer. Seyrek matriste de her sıfır olmayan değer bir öğedir ve kendi satır ve sütun listelerine bağlanır. Yapı ihtiyaca göre döngülü, çift yönlü bağlı ya da başlık düğümlü kurulabilir. Çıkış ve giriş listeleri O(d)'de gezilir; başa ekleme O(1)'dir.

Bu gösterimin ortaya çıkışı öğretici bir düşünme biçimini gösterir. Liste ile tersini birlikte tutan çözüm doğrudur ama 2e öğe kullanır. Bu israf rahatsız edicidir ve “aynı işi daha az yerle yapabilir miyim?” sorusunu doğurur. Akla gelen ilk çözüme ve onun ilk koduna hiçbir zaman tam güvenilmemelidir. Arka plandaki veri yapısı başka bir şey olsaydı problem daha verimli çözülebilir miydi? Bu soruyu sormak, iyi bir veri yapısı tasarımının ilk adımıdır.

15.3.7Çok bağlı liste

Yönsüz çizgenin komşuluk listesinde de her kenar iki öğeyle saklanır. Kenarlara bir bilgi eklenecekse (örneğin “bu kenar işlendi” işareti) bu bilginin iki kopyasını tutarlı tutmak gerekir. Çok bağlı liste bu tekrarı kaldırır.

typedef struct kenar *kenar_gost;
typedef struct kenar {
    short isaret;        /* islendi mi */
    int dugum1, dugum2;  /* uclar */
    kenar_gost list1;    /* dugum1 sonraki */
    kenar_gost list2;    /* dugum2 sonraki */
} kenar;
kenar_gost baslik[MAX_DUGUM];

• Satır 3. isaret, kenarın işlenip işlenmediğini tutar. Kenar iki listede göründüğü için bir gezinme aynı kenara iki kez rastlar; işaret, ikinci rastlayışta kenarın yeniden ele alınmasını önler.
• Satır 4. dugum1 ve dugum2 kenarın iki ucudur.
• Satır 5–6. list1, dugum1'in listesindeki sonraki kenarı; list2, dugum2'nin listesindeki sonraki kenarı gösterir. Bir öğe iki ayrı listenin zincirinde aynı anda bulunur.
• Satır 8. baslik[v], v'nin kenar listesindeki ilk öğeyi gösterir. Hiç kenarı olmayan düğümün başlığı NULL'dır.

Düğüme veri taşımak gerekirse (örneğin şehir adı) yapıya ayrı bir düğüm dizisi ya da öğeye char veri gibi bir alan eklenir. x86-64 üzerinde bu kenar yapısı dolgu baytlarıyla 32 bayttır. Komşuluk listesinde aynı kenar iki öğeyle 2 · 16 = 32 bayt tutar. Kazanç bellekte değil, bilginin tek yerde durmasındadır.

Tablo 15.12 G1'in çok bağlı listesini verir. Altı kenar N0–N5 öğeleridir.

Tabloyu okumak için bir düğümün listesi izlenir. 1'in listesi baslik[1] = N0'dan başlar. N0'da 1, dugum2'dir; sonraki kenar list2 = N3'tür. N3'te 1, dugum1'dir; sonraki kenar list1 = N4'tür. N4'te 1 yine dugum1'dir ve list1 = NULL ile liste biter. 1'in kenarları N0, N3, N4; komşuları 0, 2 ve 3'tür.

Çok bağlı listede gezinme

Gezinmenin kuralı kısadır: v, öğenin dugum1 alanındaysa list1, dugum2 alanındaysa list2 izlenir. NULL görülünce liste biter.

void komsulari_yaz(int v)
{
    kenar_gost p = baslik[v];
    while (p) {
        if (p->dugum1 == v) {       /* v: dugum1 */
            printf("%d ", p->dugum2);  p = p->list1;
        } else {                    /* v: dugum2 */
            printf("%d ", p->dugum1);  p = p->list2;
        }
    }
}

Her öğede iki iş yapılır: öteki uç yazılır ve doğru bağ seçilir. v hangi uçta ise öteki uç komşudur ve izlenecek bağ v'nin tarafındaki bağdır. Tablo 15.13 komsulari_yaz(2) çağrısını izler.

Döngü v'nin her kenarı için bir kez döner: O(d_v). Her kenar bellekte yalnız bir kez saklanmıştır, ama iki ucunun listesinden de ulaşılabilir.

Çok bağlı listeye kenar eklemek

Yeni bir kenar iki listeye birden girer. Listelerin sonuna eklemek mümkündür, ama her iki listede NULL'a kadar yürümeyi gerektirir. Başa eklemek bu maliyeti ortadan kaldırır:

void ml_ekle(int u, int v)
{
    kenar_gost p = malloc(sizeof(kenar));
    if (p == NULL) exit(1);
    p->isaret = 0;
    p->dugum1 = u;  p->dugum2 = v;
    p->list1 = baslik[u];  /* u listesine */
    p->list2 = baslik[v];  /* v listesine */
    baslik[u] = baslik[v] = p;  /* ikisine de basa */
}

• Satır 3–4. Öğe için bellek alınır ve denetlenir.
• Satır 5–6. Kenar henüz işlenmemiştir; uçlar yazılır.
• Satır 7. list1, u'nun eski ilk kenarını gösterir. Bu eski kenarda u'nun hangi uçta olduğu önemli değildir; gezinme yordamı her öğede bunu kendisi belirler.
• Satır 8. list2, v'nin eski ilk kenarını gösterir.
• Satır 9. İki başlık da yeni öğeyi gösterir. Satır 7 ile 8, bu atamadan önce yapılmalıdır; yoksa eski listeler kaybolur.

Ekleme O(1)'dir. Yönsüz çizgede tek bir başlık dizisi yeter. Yönlü bir çizgede ise ortogonal gösterimdeki gibi bir baş dizisiyle birlikte bir kuyruk dizisi tutulur. G1'in kenarları (0,1), (0,2), …, (2,3) sırasıyla ml_ekle ile eklenirse listeler gelen sıranın tersi olur; komsulari_yaz(2) bu kez 3 1 0 yazar. Tablo 15.12 ise kenarların listelerin sonuna eklendiği düzeni gösterir; o düzende çıktı 0 1 3'tür. İki yapı da doğrudur, ama hangi kodun hangi çizimi ürettiği tutarlı olmalıdır. Kenarlar bu sırayla gelir ve “her biri O(1)'de yerleşsin” denirse liste başına eklenir. Bu durumda listeyi sona ekleniyormuş gibi çizmek, kodun yaptığıyla çelişen bir çizimdir.

15.3.8Uygulama: aynı çizgenin beş gösterimi

Matris. <i, j> varsa a[i][j] = 1 yazılır; satır kuyruğu, sütun başı gösterir (Tablo 15.14). Satır toplamları çıkış derecelerini (2, 1, 1, 1), sütun toplamları giriş derecelerini (1, 1, 2, 1) verir. İki toplamın her biri 5'tir; yönlü çizgede her kenar bir çıkış ve bir giriş derecesine katkı yapar.

Liste ve tersi. Çıkış listeleri: 0 → 1, 3; 1 → 2; 2 → 0; 3 → 2. Giriş listeleri (transpoz): 0 ← 2; 1 ← 0; 2 ← 1, 3; 3 ← 0. İkisinde toplam 2e = 10 öğe vardır.

Tek öğeli gösterim. Her kenar tek bir öğedir: N1 = <0,1>, N2 = <0,3>, N3 = <1,2>, N4 = <2,0>, N5 = <3,2>. Her öğe kuyruğunun çıkış listesinde ve başının giriş listesinde yer alır. Kuyruk bağı, aynı kuyruktan çıkan sonraki kenarı; baş bağı, aynı başa giren sonraki kenarı gösterir. Yalnız e = 5 öğe gerekir.

Sağlama için 2'nin giriş listesi izlenir: başlık N3'tür (<1,2>), N3'ün baş bağı N5'tir (<3,2>), N5'in baş bağı NULL'dır. 2'ye 1'den ve 3'ten gelinir; giriş derecesi 2'dir ve matrisin 2. sütunuyla örtüşür. 0'ın çıkış listesi N1'den başlar, kuyruk bağıyla N2'ye geçer ve biter: 0'dan 1'e ve 3'e gidilir.

15.3.9Gösterimlerin karşılaştırılması

Tablo 15.16 beş gösterimi aynı ölçütlerle yan yana koyar. d_u, u'nun derecesidir.

Tablonun hiçbir satırı her sütunda en iyi değildir. Matris kenar sorgusunda rakipsizdir ama komşu taramasında ve bellekte yavaştır. Listeler gezinmede hızlıdır ama kenar sorgusunda yavaştır. Sıralı dizi en az yeri tutar ama değişikliğe gelmez. Seçim, problemde hangi işlemin kaç kez yapılacağına bağlıdır.

Bu kesimin çıkarımı bir yöntemdir: önce verinin nasıl depolanacağı düşünülür, sonra kod yazılır. Akla gelen ilk çözüm iyi bir yöntem olmayabilir. Veri yapısı iyi tasarlanırsa n³ adımlı bir algoritmanın n adıma inmesi bile mümkün olabilir. Bunun ilk örneği hemen aşağıda görülür: aynı gezinme algoritması matrisle O(n²), listeyle O(n + e) sürer. Veriyi depolamak göründüğü kadar kolay bir iş değildir.

15.3.10Ağırlıklı çizgeler

Pek çok problemde kenarın yalnız var olması yetmez; bir de değeri vardır. Yol ağında bu değer mesafe, bilgisayar ağında gecikme, proje planında süre, kablo döşemede maliyettir. Kenarlarına sayı atanmış çizgeye ağırlıklı çizge (weighted graph), bu sayılara da ağırlık denir.

Her iki temel gösterim kolayca genişler. Matriste 1 yerine kenarın ağırlığı yazılır; böyle bir matrise maliyet matrisi denir. Kenar yoksa hücreye “sonsuz” anlamına gelen bir değer yazılır. Köşegen 0'dır: bir düğümden kendisine gitmenin maliyeti yoktur. Listede ise her öğeye bir agirlik alanı eklenir.

#define SONSUZ 1000000   /* INT_MAX degil: toplamda tasar */
int maliyet[MAX_DUGUM][MAX_DUGUM];

typedef struct aoge *aoge_gost;
typedef struct aoge {
    int dugum;
    int agirlik;        /* kenarin maliyeti */
    aoge_gost bag;
} aoge;
aoge_gost abaslik[MAX_DUGUM];

C'de sonsuz diye bir tamsayı yoktur; büyük bir sabit seçilir. Akla ilk gelen INT_MAX'tır, ama bu tehlikeli bir seçimdir. En kısa yol algoritmaları sürekli d + w biçiminde toplamlar hesaplar. d = INT_MAX iken herhangi bir pozitif w eklenirse işaretli tamsayı taşar. C'de işaretli taşma tanımsız davranıştır; pratikte sonuç çoğunlukla büyük bir negatif sayıdır ve algoritma “sonsuz uzaklıktaki” düğümü en yakın düğüm sanır. SONSUZ bu yüzden özenle seçilmiştir. Gerçek ağırlıkların hepsinden büyüktür, ama iki katı bile int'e sığar. 2 · 1 000 000, 32 bitlik int'in sınırının (yaklaşık 2,1 milyar) çok altındadır.

Liste öğesi aoge, oge'ye bir int agirlik eklenmiş hâlidir; x86-64 üzerinde iki int 8 bayt, işaretçi 8 bayt eder ve dolgu gerekmez: 16 bayt. Minimum kapsayan ağaç ve en kısa yol algoritmalarının hepsi bu iki gösterimden birini kullanır.

15.4Gezinmeler

Çizge üzerindeki en temel işlem gezinmedir. Yönsüz bir G = (V, E) çizgesi ve bir v düğümü verilsin. v'den ulaşılabilen bütün düğümlere birer kez uğramak istenir. “Uğramak” ya da ziyaret etmek, düğümle ilgili işi yapmak demektir; bu notta düğümün numarasını yazdırmaktır. Bileşen bulma, döngü arama, en kısa yol ve kapsayan ağaç gibi pek çok algoritma bir gezinmenin üzerine kurulur.

Ağaçlarda gezinme kolaydır, çünkü ağaçta döngü yoktur ve her düğüme kökten tek bir yolla varılır. Çizgede ise bir düğüme birçok yoldan varılabilir. Bu yüzden çizge gezinmesinin ilk kuralı şudur: ziyaret edilen düğüm işaretlenir ve işaretli bir düğüme yeniden girilmez. İşaretler olmazsa gezinme bir döngü üzerinde sonsuza dek döner.

İki temel gezinme yöntemi vardır:

• Önce derinliğine arama (depth first search, DFS; sözlükte “derinlik öncelikli arama” adıyla da geçer). Bir komşuya gidilir ve oradan olabildiğince derine inilir. Ağaçtaki kök önde gezinmeye benzer.
• Önce genişliğine arama (breadth first search, BFS; sözlükte “genişlik öncelikli arama”). Önce başlangıcın bütün komşularına, sonra onların komşularına uğranır. Ağaçtaki düzey düzey gezinmeye benzer.

İki yöntemde de çizge komşuluk listesiyle gerçeklenir ve listeler sıralıdır. Örnek olarak sekiz düğümlü bir çizge kullanılır (Şekil 15.19).

15.4.1Önce derinliğine arama

DFS'nin fikri bir labirentte ip çekerek ilerlemeye benzer. v ziyaret edilir. Sonra v'nin listesinden ziyaret edilmemiş bir w seçilir ve arama w üzerinden sürer. w'nin de ziyaret edilmemiş bir komşusu varsa ona geçilir. Ziyaret edilmemiş komşusu kalmayan bir u düğümüne gelindiğinde bir adım geri dönülür ve u'ya hangi düğümden gelindiyse onun listesinde kalınan yerden devam edilir.

Bu geri dönüşler için her düğümün listesinde nerede kalındığının hatırlanması gerekir. Son giren ilk çıktığı için bu bilgi bir yığında (stack) tutulur: derine inerken düğümler yığına konur, gidecek yer kalmayınca yığından bir düğüm alınıp devam edilir. Açık bir yığınla yazılmış DFS karmaşık görünür. Özyinelemeli yordam ise aynı işi çok kısa yapar, çünkü yığını derleyicinin çağrı yığını tutar. Her çağrının yerel w değişkeni, o düğümün listesinde nerede kalındığını saklar.

Önce ortak bildirimler:

#include <stdio.h>
#include <stdbool.h>
#define TRUE  true
#define FALSE false
bool ugranildi[MAX_DUGUM];   /* ';' unutulmamali */

stdbool.h, C99'dan beri bool tipini ve true/false değerlerini verir. TRUE ve FALSE makroları ders kitabındaki yazımı korumak içindir. ugranildi küresel bir dizidir; program başlarken bütün öğeleri false'tur. Gezinme yeniden başlatılacaksa dizinin elle sıfırlanması gerekir.

void dfs(int v)   /* once derinligine arama */
{
    oge_gost w;
    ugranildi[v] = TRUE;    /* ugradim */
    printf("%d ", v);
    for (w = baslik[v]; w; w = w->bag)
        if (!ugranildi[w->dugum])
            dfs(w->dugum);
}

• Satır 3. w, v'nin listesinde ilerleyen işaretçidir. Her özyinelemeli çağrının kendi w'si olur.
• Satır 4. v işaretlenir. İşaret, düğümün listesi taranmadan önce konur. Böylece v'nin komşularından birinin listesinde v görüldüğünde ona geri girilmez.
• Satır 5. Ziyaret: düğüm numarası yazılır.
• Satır 6. v'nin listesi baştan sona gezilir. for başlığındaki w koşulu w != NULL anlamına gelir.
• Satır 7–8. Komşu işaretli değilse arama onun üzerinden sürer. Özyinelemeli çağrı döndüğünde döngü, bu çağrının w'sinin gösterdiği yerden, yani kalınan yerden devam eder.

15.4.2DFS izlemesi

dfs(0) çağrısı örnek çizgede izlenir. Tablo 15.18'de çağrı yığını en alttaki dfs(0)'dan başlayıp en üstteki etkin çağrıya kadar yazılır. “Atlanır” satırlarında komşu zaten işaretlidir.

İzlemenin en önemli anları dönüşlerdir. 12. adımda arama 5'ten 2'ye geçer. 0 ile 2 arasında doğrudan bir kenar vardır. Yine de 2'ye 0 → 1 → 3 → 7 → 5 → 2 gibi uzun bir yoldan varılmıştır. DFS yakını değil, derini önce dener. 18. adımda dfs(5), 2'ye inmeden önceki yerinden, listesindeki ikinci öğe 7'den devam eder. Bunu sağlayan, dfs(5) çerçevesinde saklı duran w'dir. Yığının en derin anı 15. adımdır: yedi çağrı aynı anda açıktır.

Gezinme sırasında bir düğüme ilk kez girilen kenarlar bir ağaç oluşturur: 0–1, 1–3, 3–7, 7–4, 7–5, 5–2, 2–6. Yedi kenar sekiz düğümün hepsini döngüsüz bağlar. Bu ağaca önce derinliğine kapsayan ağaç (depth first spanning tree) denir. Ağaca kullanılmayan kenarlardan biri, örneğin 0–2, eklenirse bir döngü oluşur ve yapı ağaç olmaktan çıkar.

15.4.3DFS'nin sonucu neye bağlıdır

DFS'nin ürettiği sıra çizgenin kendisine ek olarak iki şeye bağlıdır.

Başlangıç düğümü. Başlangıcın 0 olması gerekmez. Aynı çizgede ve aynı listelerle dfs(6) 6 2 0 1 3 7 4 5, dfs(4) ise 4 1 0 2 5 7 3 6 yazar. Ziyaret edilen düğümler aynıdır, dizilişleri farklıdır. Bağlantılı bir çizgede her başlangıç bütün düğümlere ulaşır.

Listelerin sırası. 0'ın listesi {1, 2} yerine {2, 1} olsaydı dfs(0) önce 2'ye inerdi ve sıra 0 2 5 7 3 1 4 6 olurdu. Listenin başa mı sona mı eklenerek kurulduğu ya da sıralı tutulup tutulmadığı gezinmeyi doğrudan değiştirir. Bu nedenle bir DFS çıktısı ancak listelerin tam sırası bilindiğinde kesin olarak söylenebilir.

Örnek çizgede sayaçlı bir dfs 8 çağrı yaptı ve listelerde tam 20 öğeye baktı; bu değerler n = 8 ve 2e = 20 ile örtüşür. Kenar sayısı en çok n(n − 1)/2 olabilir. Tam çizgede e, n² mertebesine çıkar ve iki gösterimin maliyeti eşitlenir. Seyrek çizgelerde ise liste, gezinmeyi doğrusal zamanda yapar.

Ek bellek de hesaba katılmalıdır. ugranildi dizisi n öğelidir. Çağrı yığınının derinliği en kötü durumda n'dir: düğümleri bir zincir gibi dizilmiş bir çizgede her çağrı bir sonrakini açar. Çok büyük çizgelerde bu derinlik çağrı yığınını taşırabilir; o durumda DFS açık bir yığınla yazılır.

15.4.4Önce genişliğine arama

BFS, suya atılan taşın oluşturduğu halkalar gibi yayılır. v'den başlanır ve v işaretlenir. Sonra v'nin listesindeki düğümlerin hepsi ziyaret edilir. Ardından v'nin listesindeki ilk düğümün ziyaret edilmemiş komşuları, sonra ikinci düğümünkiler ziyaret edilir. Bu böyle sürer. Ziyaret edilen her düğüm bir kuyruğa (queue) konur. Bir düğümün listesi bitince kuyruğun önündeki düğüm alınır ve onun listesine geçilir. Kuyruk boşalınca arama biter.

Yöntemin doğası gereği kuyruk zorunludur, tıpkı DFS'de yığının zorunlu olması gibi. Önce ziyaret edilen düğümün komşuları önce ziyaret edilmelidir; “ilk giren ilk çıkar” kuralı tam olarak budur.

void bfs(int v)   /* once genisligine arama */
{
    oge_gost w;
    kuyruk_gost on = NULL, arka = NULL;
    printf("%d ", v);
    ugranildi[v] = TRUE;
    kuyruk_ekle(&on, &arka, v);
    while (on) {
        v = kuyruk_al(&on, &arka);
        for (w = baslik[v]; w; w = w->bag)
            if (!ugranildi[w->dugum]) {
                printf("%d ", w->dugum);
                kuyruk_ekle(&on, &arka, w->dugum);
                ugranildi[w->dugum] = TRUE;
            }
    }
}

• Satır 4. Kuyruk bağlı listeyle gerçeklenir; on ve arka başta NULL'dır, yani kuyruk boştur.
• Satır 5–7. Başlangıç düğümü yazılır, işaretlenir ve kuyruğa konur.
• Satır 8. Kuyruk boş değilken döner. Boş kuyrukta on NULL'dır.
• Satır 9. Kuyruğun önündeki düğüm alınır. Parametre v burada yeniden kullanılır; yordamın başındaki değeri artık gerekmez.
• Satır 10–15. v'nin listesi taranır. İşaretsiz her komşu yazılır, kuyruğun arkasına eklenir ve işaretlenir.

İşaretin zamanı önemlidir: düğüm kuyruğa eklenirken işaretlenir, kuyruktan çıkarken değil. Böylece bir düğüm kuyrukta beklerken başka bir düğümün listesinde yeniden görülse bile ikinci kez kuyruğa girmez. Bu ayrıntının değeri, hatalı biçimin sonucuna bakılınca anlaşılır.

Dinamik kuyruk

BFS'nin kullandığı kuyruk, bağlı listeyle gerçeklenmiş dinamik bir kuyruktur. Önden alınır, arkaya eklenir; iki uç için iki işaretçi tutulur.

typedef struct kuyruk *kuyruk_gost;
typedef struct kuyruk {
    int dugum;
    kuyruk_gost bag;
} kuyruk;
void kuyruk_ekle(kuyruk_gost *on,
                 kuyruk_gost *arka, int d)
{
    kuyruk_gost p = malloc(sizeof(kuyruk));
    if (p == NULL) exit(1);
    p->dugum = d;  p->bag = NULL;
    if (*on) (*arka)->bag = p;  else *on = p;
    *arka = p;
}

kuyruk_ekle, iki işaretçiyi de değiştirebilmek için onların adreslerini alır (kuyruk_gost *on). Bu, C'de bir işaretçiyi fonksiyon içinden değiştirmenin tek yoludur. Yeni öğenin bağı NULL'dır, çünkü kuyruğun sonuna girer. Kuyruk boş değilse eski son öğenin bağı yeni öğeyi gösterir; boşsa yeni öğe aynı zamanda ön öğedir. İki durumda da arka yeni öğeyi gösterir. İşlem O(1)'dir.

int kuyruk_al(kuyruk_gost *on,
              kuyruk_gost *arka)
{
    kuyruk_gost p = *on;   /* on != NULL */
    int d = p->dugum;
    *on = p->bag;
    if (*on == NULL) *arka = NULL;
    free(p);
    return d;
}

kuyruk_al boş olmayan bir kuyruk bekler; açıklama satırı bu ön koşulu söyler ve BFS yordamı onu while (on) ile sağlar. Önündeki öğenin değeri saklanır, ön işaretçi bir sonrakine geçer ve öğe serbest bırakılır. Kuyruk boşalınca arka da NULL yapılmalıdır. Yapılmazsa arka, az önce serbest bırakılmış öğeyi göstermeye devam eder. Sonraki kuyruk_ekle *on'u boş görür ve doğru davranır, ama aradaki sürede arka sarkan bir işaretçidir (dangling pointer). Bu yüzden int kuyruk_al(kuyruk_gost *) gibi yalnız ön işaretçiyi alan bir prototip yetmez; arka'nın da adresi geçirilir. İşlem O(1)'dir.

15.4.5BFS izlemesi

Tablo 15.19 bfs(0) çağrısını örnek çizgede izler. Kuyruk sütununda sol uç önü, sağ uç arkayı gösterir.

12. adımda 7 kuyruğa girer ve işaretlenir. 13. adımda 4'ün listesinde 7 yeniden görülür, ama işaretli olduğu için ikinci kez eklenmez. 5 ve 6'nın listelerinde de aynı şey olur. 7'ye dört farklı düğümden varılabilir, ama kuyruğa bir kez girer.

Çıktı 0 1 2 3 4 5 6 7'dir: düğümler başlangıca olan kenar sayısına göre düzey düzey ziyaret edilmiştir. 0 düzey 0'da; 1 ve 2 düzey 1'de; 3, 4, 5, 6 düzey 2'de; 7 düzey 3'tedir. Ağaç kenarları 0–1, 0–2, 1–3, 1–4, 2–5, 2–6 ve 3–7'dir. Bu önce genişliğine kapsayan ağaçta kökten her düğüme giden yol, çizgedeki en az kenarlı yoldur.

15.4.6BFS'nin analizi ve DFS ile karşılaştırılması

BFS'nin ek belleği ugranildi dizisi ve kuyruktur; kuyrukta aynı anda en çok n düğüm bulunur. BFS'nin verdiği sıra, başlangıca olan kenar sayısının sırasıdır. Ağırlıksız bir çizgede bu, en kısa yolların sırası demektir; BFS bu yüzden en az kenarlı yolu bulan algoritmadır.

Önce derinliğine ve önce genişliğine arama kavramları veri yapılarının dışında da karşılaşılan iki genel arama stratejisidir. Yapay zekâda bir problemin bütün durumları bir arama uzayı oluşturur ve bu uzay bir ağaç gibi düşünülerek gezilir. Min-max araması, B* araması ve dal-sınır (branch and bound) yöntemleri bu gezinmelerin üzerine kurulur. Bir oyun probleminde “olası hamleler şunlardır” denip her hamle ayrı ayrı açılıyorsa arama genişliğine ilerliyor demektir.

15.5Bileşenler, döngüler ve iki parçalılık

Gezinme yordamları tek başına yalnız düğüm numaralarını yazar. Asıl değerleri, üzerlerine kurulan algoritmalardadır. Bu kesim DFS ve BFS'yi üç soruyu cevaplamak için kullanır: Çizge kaç parçadan oluşur? Çizgede döngü var mı? Çizgenin düğümleri, her kenar iki gruba arasında kalacak biçimde ikiye ayrılabilir mi?

15.5.1Bağlantılı bileşenler

Her düğüm tam olarak bir bileşene aittir; bileşenler düğüm kümesini ayrık parçalara böler. G4'ün iki, G5'in dokuz bileşeni vardır. Bağlantılı bir çizgenin tek bileşeni kendisidir.

Bileşenleri bulmak için gezinmenin bir özelliği kullanılır: dfs(v), v'den ulaşılabilen bütün düğümleri, yani v'nin bileşenini tümüyle işaretler. Gezinme bittiğinde işaretsiz kalan bir düğüm varsa o başka bir bileşendedir ve oradan yeni bir gezinme başlatılır.

void bitisik_bilesenler(int n)
{
    int i;
    for (i = 0; i < n; i++)
        if (!ugranildi[i]) {   /* yeni */
            dfs(i);
            printf("\n");
        }
}

• Satır 4. Bütün düğümler sırayla denenir.
• Satır 5. İşaretsiz bir düğüm, daha önceki hiçbir gezinmenin ulaşamadığı yeni bir bileşenin ilk düğümüdür.
• Satır 6. dfs(i) bu bileşenin bütün düğümlerini yazar ve işaretler.
• Satır 7. Her bileşen ayrı satıra yazılır. Bu satıra bir sayaç artırımı (sayi++) eklenirse yordam bileşen sayısını da verir; sayı 1 ise çizge bağlantılıdır.

Yordam DFS yerine BFS ile de aynı biçimde yazılabilir. Yordamın çalışması için ugranildi dizisinin başta tamamen FALSE olması gerekir.

Alttaki örnekte ikinci satırın çıktısı 1 2 4 3'tür. 1'in listesi {2, 3} olduğu için DFS önce 2'ye, 2'nin listesindeki 4'e, oradan 3'e gider. 5 bu satırda görünmez; 5, 6, 7, 8 başka bir bileşendir. Yalnız 0'dan oluşan bileşen tek düğümlüdür; dfs(0) listesi boş olduğu için yalnız 0'ı yazar. Tablo 15.21 üstteki örneğin izlemesidir.

15.5.2Analiz: çarpım değil, toplam

Yordamın maliyeti ilk bakışta yanıltıcıdır. Dıştaki for n kez döner. İçteki dfs çağrısının maliyeti O(n + e)'dir. Bu iki sayı çarpılıp karmaşıklık O(n(n + e)) denebilir mi? Hayır. “Döngüleri bulur, maliyetlerini çarparım” kuralı burada yanlış sonuç verir, çünkü iç işin maliyeti her turda aynı değildir.

Uç durum bunu açıkça gösterir. Çizge bağlantılıysa ilk turda dfs(0) bütün çizgeyi O(n + e)'de gezer ve ugranildi dizisinin tamamı TRUE olur. i'nin geri kalan n − 1 değerinde if'e hiç girilmez. Çarpım ancak her turda dfs'nin bütün çizgeyi yeniden gezdiği durumda doğru olurdu; işaretler bunu engeller. Aynı türden akıl yürütme, döngülerin iç içe olduğu ama iç döngünün toplam işinin sınırlı olduğu pek çok algoritmada karşılaşılır.

15.5.3Bağlantılılık ve kenar sayısı

Bir çizgenin bağlantılı olabilmesi için kaç kenara ihtiyaç vardır?

Teorem tek yönlüdür. n − 1 kenar bağlantılılık için gereklidir ama yeterli değildir. 5 düğümlü bir çizgede 4 kenar bir zincir kurabilir; o zaman çizge bağlantılıdır. Aynı 4 kenar dört düğüm arasında bir döngü kurabilir; o zaman beşinci düğüm yalnız kalır ve çizge bağlantılı değildir. Kenar sayısı n − 1'den azsa ise çizge kesinlikle bağlantılı değildir; G5'te e = 2 < 10'dur.

Üst sınır, karmaşıklık ifadeleri açısından önemlidir. e, n² mertebesinde bir sayı olabilir. O(n + e) ifadesi bu yüzden tam çizgede O(n²)'ye eşittir; liste ancak seyrek çizgelerde matristen asimptotik olarak üstün olur. Bağlantılı ve tam n − 1 kenarlı bir çizge döngü içermez; böyle bir çizge bir ağaçtır. Gezinmelerin ürettiği kapsayan ağaçlarda da n − 1 kenar bulunur.

Oyun problemleri bu sınırların pratikteki önemini gösterir. Tic tac toe gibi bir oyunda her durum bir düğüm, her hamle bir kenardır. “Rakibin hamlesini nasıl bozarım?” sorusu bu çizgede bir arama yapmaktır. Durum sayısı hızla büyür ve aramanın maliyeti doğrudan düğüm ve kenar sayısına bağlıdır.

15.5.4Yönsüz çizgede döngü tespiti

DFS'nin bir yan ürünü, çizgede döngü olup olmadığıdır. DFS bir düğümün listesini tararken işaretli bir komşuya rastlayabilir. Yönsüz çizgede bunun iki nedeni olabilir. Birincisi, komşu düğüme hemen önceki adımda ondan gelinmiştir; bu, gelinen kenarın öteki ucudur ve döngü belirtisi değildir. İkincisi, komşu daha önce başka bir yoldan işaretlenmiştir. Bu durumda düğümden o komşuya hem ağaç kenarlarıyla hem de bu kenarla gidilebilir: bir döngü vardır. Böyle kenarlara geri kenar (back edge) denir.

bool dongu_var(int v, int ata)
{
    oge_gost w;
    ugranildi[v] = TRUE;
    for (w = baslik[v]; w; w = w->bag)
        if (!ugranildi[w->dugum]) {
            if (dongu_var(w->dugum, v)) return TRUE;
        } else if (w->dugum != ata)
            return TRUE;          /* geri kenar */
    return FALSE;
}

• Satır 1. Yordam düğümün yanında ata'yı, yani bu düğüme hangi düğümden gelindiğini alır. İlk çağrıda ebeveyn yoktur; -1 hiçbir düğümün numarası olmadığı için bu anlamda kullanılır.
• Satır 4. Düğüm işaretlenir.
• Satır 6–7. İşaretsiz komşuya inilir; ebeveyni şimdiki düğümdür. Alt çağrı döngü bulursa TRUE, çağrı zinciri boyunca hemen yukarı taşınır.
• Satır 8–9. Komşu işaretliyse ve ebeveyn değilse geri kenar bulunmuştur. else if, iç if'in değil dış if'in else'idir; süslü parantezler bunu açıkça belirler. Parantezler kaldırılırsa else en yakın if'e bağlanır ve yordamın anlamı değişir.
• Satır 10. Bütün komşular geçildi ve döngü bulunmadı.

Kenarları 0–1, 1–2, 2–3 ve 3–1 olan dört düğümlü çizgede sıralı listeler 0: {1}, 1: {0, 2, 3}, 2: {1, 3}, 3: {1, 2}'dir. Tablo 15.22 dongu_var(0, -1) çağrısını izler.

TRUE değeri 3'ten 2'ye, 2'den 1'e, 1'den 0'a taşınır ve yordam erken biter. Döngü yoksa yordam DFS'nin kendisi kadar, O(n + e) sürer. Çizgede birden çok bileşen varsa yordam, bileşen bulmadaki gibi her işaretsiz düğümden yeniden başlatılır. Ağaç olduğu bilinen G2 üzerinde yordam FALSE döndürür.

15.5.5Yönlü çizgede döngü

Yönlü çizgede ebeveyn denetimi yetmez. Daha önce işaretlenmiş bir düğüme giden bir kenar döngü kapatmayabilir: o düğüm başka bir dalda çoktan bitirilmiş olabilir. Örneğin 0 → 1, 0 → 2, 1 → 3, 2 → 3 kenarlarında DFS 0, 1, 3 sırasıyla iner, sonra 2'den 3'e giden kenarı görür. 3 işaretlidir, ama döngü yoktur. Ayırt edici soru şudur: işaretli düğüm şu anda yığında mı? Yığındaki bir düğüme giden kenar, o düğümden şimdiki düğüme inen yolu kapatır ve bir döngüdür.

Bu ayrım üç renkle yapılır: beyaz henüz girilmemiş, gri girilmiş ama bitmemiş (yığında), siyah bitmiş düğümdür.

enum { BEYAZ, GRI, SIYAH };
int durum[MAX_DUGUM];   /* hepsi basta BEYAZ */

bool yonlu_dongu(int v)
{
    oge_gost w;
    durum[v] = GRI;                  /* yigina girdi */
    for (w = baslik[v]; w; w = w->bag) {
        if (durum[w->dugum] == GRI)
            return TRUE;             /* yigindaki dugume kenar */
        if (durum[w->dugum] == BEYAZ && yonlu_dongu(w->dugum))
            return TRUE;
    }
    durum[v] = SIYAH;                /* bitti */
    return FALSE;
}

Düğüme girilince gri yapılır. Gri bir komşu görülürse döngü vardır. Beyaz komşuya inilir. Bütün komşular bitince düğüm siyah olur ve artık hiçbir döngünün parçası olarak görülmez. Yordam G3'te (0 → 1 → 0) ve uygulama çizgesinde (0 → 1 → 2 → 0) TRUE, yukarıdaki dört düğümlü örnekte FALSE döndürdü. Maliyet yine O(n + e)'dir; matrisle aynı DFS O(n²) olur. Topolojik sıralama yordamı da döngüyü kendiliğinden yakalar.

Döngü tespitinin pratik önemi büyüktür. İşler arasında öncelik ilişkisi tanımlanan bir projede yönlü döngü, “A, B'den önce; B, A'dan önce bitmeli” gibi bir çelişki demektir ve proje hiç bitmez. Minimum kapsayan ağaç kurulurken döngü kapatan bir kenar ise gereksiz bir kenardır ve ağaca alınmaz.

15.5.6İki parçalı çizge testi

Öğrenciler ve dersler iki parçalı bir çizge oluşturur: kenarlar yalnız bir öğrenciyi bir derse bağlar. K_3,3, üçer düğümlü iki grubun her düğümünün öteki gruptaki her düğüme bağlı olduğu iki parçalı çizgedir.

Test bir boyama problemidir. Başlangıç düğümü 0 rengine boyanır. BFS her işaretsiz komşuyu, kendisinin ters rengine boyar. Bir kenarın iki ucu aynı renge boyanmış çıkarsa çizge iki parçalı değildir. Hiç çelişki çıkmazsa renkler iki grubu verir.

int renk[MAX_DUGUM];   /* -1: boyanmadi, 0 ya da 1 */

bool iki_parcali_mi(int n)
{
    int i, v;
    oge_gost w;
    kuyruk_gost on = NULL, arka = NULL;
    for (i = 0; i < n; i++) renk[i] = -1;
    for (i = 0; i < n; i++) {
        if (renk[i] != -1) continue;      /* yeni bilesen */
        renk[i] = 0;
        kuyruk_ekle(&on, &arka, i);
        while (on) {
            v = kuyruk_al(&on, &arka);
            for (w = baslik[v]; w; w = w->bag)
                if (renk[w->dugum] == -1) {
                    renk[w->dugum] = 1 - renk[v];
                    kuyruk_ekle(&on, &arka, w->dugum);
                } else if (renk[w->dugum] == renk[v]) {
                    while (on) kuyruk_al(&on, &arka);   /* kuyrugu bosalt */
                    return FALSE;
                }
        }
    }
    return TRUE;
}

• Satır 1. renk dizisi hem işaret hem renk tutar: -1 henüz boyanmamış düğümdür. Ayrı bir ugranildi dizisi gerekmez.
• Satır 8–12. Bütün renkler silinir; her bileşen için BFS ayrı başlatılır; bir bileşenin rengi ötekini etkilemez.
• Satır 16–18. Boyanmamış komşu ters renge boyanır ve kuyruğa girer.
• Satır 19–21. Komşu boyanmış ve rengi aynıysa test başarısızdır. Yordamdan çıkmadan önce kuyruk boşaltılır; yoksa kuyrukta kalan öğeler hiç serbest bırakılmaz.

6 düğümlü döngüde BFS düğümleri 0, 1, 5, 2, 4, 3 sırasıyla boyar; renkler 0, 1, 1, 0, 0, 1'dir. Hiçbir kenarın iki ucu aynı renkte değildir. Üçgende ise 0'a renk 0, onun komşuları 1 ve 2'ye renk 1 verilir. 1'in listesi tarandığında 2 görülür; ikisi de 1 rengindedir ve test başarısız olur.

Testin maliyeti BFS'nin maliyetidir: O(n + e). Yordam 6 düğümlü döngü ve K_3,3 için TRUE, üçgen için FALSE döndürdü; örnek gezinme çizgesi de iki parçalıdır, çünkü bütün döngüleri 4 ya da 6 kenarlıdır.

15.6Karmaşıklık özeti

Tablo 15.23 bu notta incelenen işlemlerin maliyetlerini iki temel gösterim için bir arada verir. n düğüm sayısı, e kenar sayısı, d ilgili düğümün derecesidir. Bağlantılı basit bir çizgede n − 1 ≤ e ≤ n(n − 1)/2'dir.

Tablonun özü tek bir cümledir: komşuları bulmak matriste O(n), listede O(d)'dir. Bütün gezinme tabanlı algoritmalar bu farkı n düğüm üzerinden toplar; matriste n · n, listede Σd = 2e çıkar.

15.7Sık yapılan hatalar

1. Yönlü çizgeyi yönsüz sanmak. <u, v> varken <v, u>'yu da var saymak ya da yönlü çizgenin matrisini simetrik sanmak. G3'te a[1][2] = 1, a[2][1] = 0'dır.
2. BFS'de işareti geç koymak. Düğümü kuyruğa eklerken değil, çıkarırken işaretlemek. Aynı düğüm kuyruğa birden çok kez girer; örnek çizgede 7 dört kez yazılır.
3. İşaret dizisini sıfırlamamak. ugranildi küreseldir. İkinci bir gezinmeden önce FALSE yapılmazsa ikinci gezinme hiçbir düğüme giremez ve yalnız başlangıcı yazar.
4. Bileşen analizinde maliyetleri çarpmak. Dış for ile DFS'yi çarpıp O(n(n + e)) demek. İşaretler sayesinde bütün DFS çağrılarının toplamı O(n + e)'dir.
5. Belleği özensiz yönetmek. malloc sonucunu denetlememek; sizeof(oge_gost) ile işaretçi boyutunda yer almak; program sonunda listeleri free etmemek; free ettikten sonra öğenin bağını okumak.
6. Gereksiz yere sona eklemek. Kenarı listenin sonuna ekleyip her seferinde listeyi baştan yürümek. Sıra önemli değilse O(1)'lik başa ekleme yeter; çizim de bu durumda kodun ürettiği ters sırayı göstermelidir.
7. Matris parametresinde boyutu unutmak. int a[][] yazmak derlenmez; ikinci boyut verilmelidir: int a[][MAX_DUGUM].
8. Sonsuz için INT_MAX seçmek. Maliyet toplamlarında işaretli taşma olur; güvenli büyük bir sabit kullanılır.

15.8Alıştırmalar ve çözümleri

Bu kesimdeki alıştırmalar sunumdaki sırayla verilir; her birinin ardından çözüm gelir.

15.8.1Derece dizisi

Soru. Derece dizisi (3, 3, 2, 2, 1) olan basit, yönsüz bir çizge var mıdır? Kaç kenarı vardır?

Çözüm. Derecelerin toplamı 11'dir. Teorem 15.1'e göre toplam 2e, yani çift olmalıdır. Böyle bir çizge yoktur. Aynı sonuç, tek dereceli düğümlerin sayısından da çıkar: 3, 3 ve 1 olmak üzere üç tek dereceli düğüm vardır, oysa bu sayı çift olmalıdır.

15.8.2Sıralı gösterimde komşular

Soru. G4'ün dizi ile sıralı gösteriminde 5 numaralı düğümün komşularını hangi indisler tutar?

Çözüm. dugum[5] = 18 ve dugum[6] = 20'dir. Komşular 18 ve 19 indisli hücrelerdedir: dugum[18] = 4, dugum[19] = 6. 5'in komşuları 4 ve 6, derecesi 20 − 18 = 2'dir.

15.8.37'den başlayan gezinmeler

Soru. Sekiz düğümlü örnek çizgede DFS ve BFS 7'den başlatılırsa (listeler sıralı) çıktılar ne olur?

Çözüm. DFS: 7'nin listesi {3, 4, 5, 6}'dır; ilk komşu 3'e inilir. 3'ün işaretsiz ilk komşusu 1, 1'inki 0, 0'ınki 2, 2'ninki 5'tir. 5'in komşuları 2 ve 7 işaretlidir; 2'ye dönülür ve 6'ya inilir. Geri dönüşler 1'e kadar sürer ve 1'in listesindeki 4 bulunur. Çıktı 7 3 1 0 2 5 6 4'tür. BFS: 7'nin komşuları 3, 4, 5, 6 sırayla yazılır ve kuyruğa girer. 3 alınınca 1, 4 alınınca hiçbir şey, 5 alınınca 2 eklenir. 6'nın komşuları işaretlidir. 1 alınınca 0 eklenir. Çıktı 7 3 4 5 6 1 2 0'dır.

15.8.4İşaret satırını taşımak

Soru. BFS kodunda ugranildi[w->dugum] = TRUE satırı kuyruk_al'dan sonraya taşınırsa ne olur?

Çözüm. Bir düğüm kuyrukta beklerken işaretsiz kalır. Başka bir düğümün listesinde görülünce yeniden yazılır ve yeniden kuyruğa eklenir. Örnek çizgede 7, kuyruktan çıkmadan önce 3, 4, 5 ve 6 üzerinden dört kez eklenir; bfs(0) 0 1 2 3 4 5 6 7 7 7 7 yazar. 7'den başlanırsa 1, 2 ve 0 da yinelenir: 7 3 4 5 6 1 1 2 2 0 0 0 0. Çıktı yanlıştır ve iş O(n + e)'yi aşar.

15.8.5Matrisle bileşen sayısı

Soru. Komşuluk matrisiyle verilen bir çizgenin bileşen sayısını bulan yordamı yazınız; karmaşıklığı nedir?

Çözüm. DFS'nin matris biçimi, bir düğümün komşularını satırını tarayarak bulur:

void mdfs(int a[][MAX_DUGUM], int n, int v)
{
    int j;
    ugranildi[v] = TRUE;
    printf("%d ", v);
    for (j = 0; j < n; j++)            /* satirin tamami: O(n) */
        if (a[v][j] && !ugranildi[j])
            mdfs(a, n, j);
}

int matris_bilesen_sayisi(int a[][MAX_DUGUM], int n)
{
    int i, sayi = 0;
    for (i = 0; i < n; i++) ugranildi[i] = FALSE;
    for (i = 0; i < n; i++)
        if (!ugranildi[i]) {
            sayi++;
            mdfs(a, n, i);
            printf("\n");
        }
    return sayi;
}

mdfs, v'nin satırındaki her 1 için işaretsiz komşuya iner. matris_bilesen_sayisi işaretleri sıfırlar ve her işaretsiz düğümden yeni bir gezinme başlatıp sayacı artırır. G4'ün matrisine uygulandığında 0 1 3 2 ve 4 5 6 7 satırlarını yazar ve 2 döndürür. Her düğüm bir kez ziyaret edilir ve her ziyarette n hücrelik bir satır taranır: O(n²).

15.8.6Giriş derecesini O(1)'de vermek

Soru. Yönlü bir çizgede giriş derecesini O(1)'de verebilmek için hangi yapı tutulur ve nasıl güncellenir?

Çözüm. Her düğüm için bir giris[] sayacı tutulur. <u, v> kenarı eklenirken giris[v]++, silinirken giris[v]-- yapılır. Sorgu tek bir dizi okumasıdır. Gelen kenarların kendileri de gerekiyorsa ters liste ya da ortogonal liste tutulur; ters listenin uzunluğu giriş derecesidir, ama onu saymak O(d)'dir.

15.9Özet

• Çizge G = (V, E), boş olmayan bir düğüm kümesi ile boş olabilen bir kenar kümesidir. Yönsüzde (u, v) = (v, u); yönlüde <u, v> ≠ <v, u>.
• Komşu, alt çizge, yol, döngü, bağlantılılık ve derece temel kavramlardır. Derece her zaman belirli bir düğüm için söylenir; yönlüde giriş ve çıkış derecesinin toplamıdır.
• Derecelerin toplamı 2e'dir. Bağlantılı bir çizgede n − 1 ≤ e ≤ n(n − 1)/2; alt sınır gerekli ama yeterli değildir.
• Komşuluk matrisi O(n²) bellek ister; kenar sorgusu O(1), komşu taraması O(n)'dir. Komşuluk listesi O(n + e) bellek ister; komşu taraması O(d)'dir.
• Başa ekleme her kenarı O(1)'de yerleştirir ve listeyi gelen sıranın tersine çevirir. Yönlü çizgede giriş derecesi için ters liste O(n + e)'de kurulur.
• Sıralı dizi işaretçisiz, n + 2e + 1 tamsayılık bir gösterimdir ama değişikliğe uygun değildir. Ortogonal liste ve çok bağlı liste her kenarı tek öğede tutar.
• Ağırlıklı çizgede matrise ağırlık, listeye agirlik alanı eklenir; sonsuz için taşmayan büyük bir sabit seçilir.
• DFS özyineleme ya da yığınla derine iner; BFS kuyrukla katman katman ilerler. İkisi de listeyle O(n + e), matrisle O(n²)'dir. Sonuç sırası başlangıca ve liste sırasına bağlıdır.
• Bağlantılı bileşenler, her işaretsiz düğümden bir gezinme başlatılarak O(n + e)'de bulunur; dış döngü ile gezinmenin maliyetleri çarpılmaz.
• Yönsüz çizgede ebeveyn olmayan işaretli komşu, yönlü çizgede gri düğüme giden kenar döngü demektir. BFS ile iki renge boyama iki parçalılığı sınar; iki parçalı çizgede tek uzunlukta döngü yoktur.
• Yöntem: önce problem ve işlemler, sonra verinin nasıl depolanacağı, en son kod. İlk akla gelen gösterime güvenilmez.

15.10Kavram listesi

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

• çizge graph
• düğüm vertex
• kenar edge
• yönlü çizge directed graph
• komşu adjacent
• alt çizge subgraph
• yol path
• döngü cycle
• bağlantılı connected
• derece degree
• giriş derecesi in-degree
• çıkış derecesi out-degree
• tam çizge complete graph
• komşuluk matrisi adjacency matrix
• komşuluk listesi adjacency list
• ortogonal liste orthogonal list
• çok bağlı liste adjacency multilist
• önce derinliğine arama depth-first search
• önce genişliğine arama breadth-first search
• kapsayan ağaç spanning tree
• minimum kapsayan ağaç minimum spanning tree
• bağlantılı bileşen connected component
• döngü tespiti cycle detection
• iki parçalı çizge bipartite graph
• kuyruk queue
• çağrı yığını call stack
• en kısa yol shortest path

15.11Kendini Dene

1. 9 düğümlü, bağlantılı ve basit bir çizgede en az ve en çok kaç kenar bulunabilir?

   Cevap

   En az n − 1 = 8, en çok 9 · 8 / 2 = 36. 8 kenarlı bağlantılı çizge bir ağaçtır; 36 kenarlı çizge tam çizge K₉'dur.

2. Yönsüz bir çizgenin komşuluk listelerinde toplam 30 öğe vardır. Çizgenin kaç kenarı vardır? Aynı çizge komşuluk matrisiyle tutulsaydı matriste kaç tane 1 bulunurdu?

   Cevap

   Her kenar iki listede göründüğü için e = 30 / 2 = 15. Matriste de her kenar simetrik iki hücreye yazılır: 30 tane 1.

3. G2'nin listeleri sıralı tutuluyor. dfs(0) ve bfs(0) ne yazar?

   Cevap

   DFS: 0 1 3 4 2 5 6; ağaçta kök önde gezinmenin aynısıdır. BFS: 0 1 2 3 4 5 6; düzey düzey gezinmenin aynısıdır.

4. Sekiz düğümlü örnek çizgede bfs(6) ne yazar?

   Cevap

   6 2 7 0 5 3 4 1. 6'nın komşuları 2 ve 7'dir. 2 alınınca 0 ve 5, 7 alınınca 3 ve 4 eklenir. 0 alınınca 1 eklenir; kalanların komşuları işaretlidir.

5. Sekiz düğümlü örnek çizge (e = 10) dizi ile sıralı gösterimle tutuluyor. Dizi kaç hücrelidir ve 7'nin komşuları hangi indislerdedir?

   Cevap

   n + 2e + 1 = 8 + 20 + 1 = 29 hücre. Başlangıç indisleri 9, 11, 14, 17, 19, 21, 23, 25, 29'dur. dugum[7] = 25, dugum[8] = 29: 7'nin komşuları 25–28 indislerinde, 3, 4, 5 ve 6'dır.

6. G1'in kenarları (0,1), (0,2), (0,3), (1,2), (1,3), (2,3) sırasıyla ml_ekle ile çok bağlı listeye ekleniyor. komsulari_yaz(0) ne yazar?

   Cevap

   3 2 1. Her kenar listelerin başına girer; 0'ın listesinde en son eklenen (0,3) öndedir.

7. G5'e (11 düğüm; kenarlar (1,4) ve (7,8)) bitisik_bilesenler(11) uygulanırsa kaç satır yazılır? if'e kaç kez girilir?

   Cevap

   9 satır: 0, 1 4, 2, 3, 5, 6, 7 8, 9, 10. if'e 9 kez girilir; i = 4 ve i = 8'de düğümler önceki gezinmelerde işaretlenmiştir.

8. dongu_var'da else if (w->dugum != ata) yerine yalnız else yazılırsa ağaç olan G2 için yordam ne döndürür? Neden?

   Cevap

   TRUE döndürür, oysa G2'de döngü yoktur. dongu_var(1, 0), 1'in listesindeki ilk öğe olan 0'ı işaretli görür ve onu geri kenar sayar. Yönsüz çizgede gelinen kenar, öteki ucun listesinde de bulunur; ebeveyn denetimi bu kenarı ayırmak içindir.

15.12İleri okuma

• E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2. baskı, Bölüm 6. Bu notun gösterimleri, dfs, bfs ve bağlantılı bileşen yordamları oradaki biçimiyle izlenmiştir; çok bağlı liste ve sıralı gösterimin ayrıntıları da oradadır.
• T. H. Cormen ve ark., Introduction to Algorithms, 4. baskı, Bölüm 20. DFS'nin beyaz/gri/siyah renklendirmesi, kenar sınıflandırması ve BFS'nin en kısa yol özelliğinin kanıtları verilir.
• R. Sedgewick, Algorithms in C, Part 5: Graph Algorithms, 3. baskı. Çizge gösterimleri ve gezinmeler C koduyla, büyük çizgeler üzerindeki deneylerle birlikte ele alınır.

15.13Kaynaklar

1. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2. bs., Silicon Press, 2008. Bölüm 6, Graphs.
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. bs., MIT Press, 2022. Bölüm 20, Elementary Graph Algorithms.
3. R. Sedgewick, Algorithms in C, Part 5: Graph Algorithms, 3. bs., Addison-Wesley, 2002.

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