Çizge Gösterimleri

Çizge kavramı soyuttur; kodda bir gösterime dönüşmesi gerekir. İki temel seçenek vardır ve aralarındaki fark, bu kursun tekrarlayan temasının bir örneğidir: aynı veri, farklı yerleşim, farklı maliyet.

Seçim, çizgenin kenar yoğunluğuna ve hangi işlemlerin sık yapılacağına bağlıdır. Bu iki ölçüt bilinmeden yapılan seçim, algoritmanın maliyetini gereksiz yere bir mertebe yukarı taşıyabilir.

Komşuluk Matrisi

Komşuluk matrisi, $\lvert V \rvert \times \lvert V \rvert$ boyutunda bir tablodur. Satır $i$, sütun $j$ hücresi, $i$ ile $j$ arasında kenar olup olmadığını söyler; ağırlıklı çizgede ağırlığı taşır.

INF = float("inf")
dugumler = ["bati", "dogu", "guney", "kuzey", "merkez"]
dizin = {ad: i for i, ad in enumerate(dugumler)}
n = len(dugumler)

matris = [[INF] * n for _ in range(n)]
for i in range(n):
    matris[i][i] = 0

for a, b, agirlik in [("kuzey", "merkez", 4), ("guney", "merkez", 2),
                      ("dogu", "merkez", 7), ("bati", "kuzey", 3),
                      ("bati", "guney", 5)]:
    matris[dizin[a]][dizin[b]] = agirlik
    matris[dizin[b]][dizin[a]] = agirlik          # yönsüz: iki hücre birden

print(matris[dizin["bati"]][dizin["kuzey"]])      # 3    — kenar var
print(matris[dizin["bati"]][dizin["dogu"]])       # inf  — kenar yok
print(sum(1 for x in matris[dizin["merkez"]] if x not in (0, INF)))   # 3 — derece

Üstünlüğü: İki düğüm arasında kenar olup olmadığı tek bir okumayla, $O(1)$’de yanıtlanır.

Bedeli: Bellek her zaman $O(\lvert V \rvert^2)$’dir — kenar sayısından bağımsız. Ayrıca bir düğümün komşularını listelemek, o satırın tamamını taramayı gerektirir: $O(\lvert V \rvert)$.

Yönsüz çizgede matris köşegene göre bakışımlıdır; yalnızca yarısını saklamak belleği yarıya indirir ama mertebeyi değiştirmez.

Komşuluk Listesi

Komşuluk listesi, her düğüm için yalnızca komşularının listesini tutar.

from collections import defaultdict

komsuluk: dict[str, list[tuple[str, int]]] = defaultdict(list)
for a, b, agirlik in [("kuzey", "merkez", 4), ("guney", "merkez", 2),
                      ("dogu", "merkez", 7), ("bati", "kuzey", 3),
                      ("bati", "guney", 5)]:
    komsuluk[a].append((b, agirlik))
    komsuluk[b].append((a, agirlik))              # yönsüz: iki yöne de eklenir

print(sorted(komsuluk["merkez"]))
# [('dogu', 7), ('guney', 2), ('kuzey', 4)]
print(len(komsuluk["bati"]))                      # 2   — derece doğrudan okunur
print(any(komsu == "dogu" for komsu, _ in komsuluk["bati"]))   # False

Üstünlüğü: Bellek $O(\lvert V \rvert + \lvert E \rvert)$’dir; yalnızca var olan kenarlar saklanır. Bir düğümün komşularını gezmek, derecesi kadar sürer.

Bedeli: İki düğüm arasında kenar olup olmadığı, listenin taranmasıyla bulunur — $O(\text{derece})$.

Seyreklik Belirleyicidir

Karar ölçütü, kenar sayısının düğüm sayısına oranıdır.

Bir çizge yoğunsa ($\lvert E \rvert \approx \lvert V \rvert^2$) matris hem bellek açısından makuldür hem sabit zamanlı kenar sorgusu verir.

Bir çizge seyrekse ($\lvert E \rvert \approx \lvert V \rvert$) matris neredeyse tümüyle boş kalır. On bin düğümlü ve otuz bin kenarlı bir yol ağında matris yüz milyon hücre ister; komşuluk listesi kırk bin girdiyle yetinir.

Gerçek çizgelerin büyük çoğunluğu seyrektir: her şehir birkaç şehre, her kişi birkaç yüz kişiye, her sayfa birkaç düzine sayfaya bağlanır. Bu nedenle varsayılan seçim komşuluk listesidir; matris, düğüm sayısı küçük veya çizge yoğun olduğunda tercih edilir.

Üçüncü Seçenek: Kenar Listesi

En yalın gösterim, kenarların düz bir listesidir — önceki dersteki kenarlar değişkeni buydu.

Gezinme için elverişsizdir: bir düğümün komşularını bulmak tüm listeyi taramayı gerektirir. Buna karşılık iki durumda doğru seçimdir: kenarların tümü üzerinde sırayla çalışan algoritmalarda (kenarları ağırlığa göre sıralayıp işleyen minimum kapsayan ağaç algoritması gibi) ve çizgenin saklanması veya aktarılması gerektiğinde.

Karşılaştırma

İşlem	Komşuluk matrisi	Komşuluk listesi	Kenar listesi
Bellek	$O(V^2)$	$O(V + E)$	$O(E)$
Kenar var mı	$O(1)$	$O(\text{derece})$	$O(E)$
Komşuları gezme	$O(V)$	$O(\text{derece})$	$O(E)$
Kenar ekleme	$O(1)$	$O(1)$	$O(1)$
Kenar silme	$O(1)$	$O(\text{derece})$	$O(E)$
Tüm kenarları gezme	$O(V^2)$	$O(V + E)$	$O(E)$

Tabloda $V$ ve $E$, düğüm ve kenar sayılarını gösterir; “derece” ilgili düğümün komşu sayısıdır ve seyrek çizgelerde küçük bir sabit gibi davranır.

Dördüncü satırdaki eşitlik yanıltıcı olmasın: matriste kenar eklemek sabit zamanlıdır ama matrisin kendisi baştan ayrılmıştır; düğüm eklemek matrisin yeniden oluşturulmasını gerektirir. Komşuluk listesinde düğüm eklemek yalnızca yeni bir girdi açar.

Düğüm Kimlikleri

Yukarıdaki örneklerde düğümler dizgi adlarla anıldı. Büyük çizgelerde bu, iki maliyet üretir: her erişimde dizgi karma hesabı yapılır ve her düğüm adı ayrı bir nesne olarak bellekte durur.

Yaygın çözüm, düğümlere tam sayı kimlikler vermektir. Adlar bir kez taranır, her ada sıralı bir numara atanır ve bundan sonra tüm yapılar dizin olarak bu numarayı kullanır.

adlar = ["bati", "dogu", "guney", "kuzey", "merkez"]
kimlik = {ad: i for i, ad in enumerate(adlar)}

komsu_listesi: list[list[int]] = [[] for _ in adlar]
for a, b in [("kuzey", "merkez"), ("guney", "merkez"), ("dogu", "merkez"),
             ("bati", "kuzey"), ("bati", "guney")]:
    komsu_listesi[kimlik[a]].append(kimlik[b])
    komsu_listesi[kimlik[b]].append(kimlik[a])

print(komsu_listesi[kimlik["merkez"]])       # [3, 2, 1]
print([adlar[i] for i in komsu_listesi[kimlik["merkez"]]])
# ['kuzey', 'guney', 'dogu']

Kazanç yalnızca hız değildir: ziyaret işaretleri, uzaklıklar ve ebeveyn kayıtları da eşleme yerine düz dizilerde tutulabilir. Bu, hem bellek hem önbellek davranışı açısından belirgin bir iyileşmedir ve büyük çizgelerle çalışan kütüphanelerin standart yaklaşımıdır.

Gezinme Maliyetine Etkisi

Sonraki iki derste ele alınacak gezinme algoritmalarının maliyeti, doğrudan gösterime bağlıdır. Her düğüm bir kez ziyaret edilir ve komşuları gezilir:

• Komşuluk listesiyle toplam maliyet $O(V + E)$’dir — her kenar iki kez incelenir.
• Komşuluk matrisiyle $O(V^2)$’dir — her düğüm için tüm satır taranır, kenar olmasa bile.

Seyrek bir çizgede bu, doğrusal ile karesel arasındaki farktır. Gösterim seçimi bu nedenle bir ayrıntı değil, algoritmanın maliyet sınıfını belirleyen bir karardır.

Üçüncü bir seçenek olarak, iki gösterim birlikte de tutulabilir: gezinme için komşuluk listesi, sık sorulan kenar sınamaları için ek bir küme. Bellek karşılığında iki işlemi de ucuzlatan bu yaklaşım, aynı verinin birden çok yapıda tutulmasının meşru olduğu durumlardan biridir — kursun ilk dersinden beri tekrarlanan ödünleşimin bilinçli kullanımıdır.

Özet

• Komşuluk matrisi kenar sorgusunu sabit zamanlı yapar; belleği kenar sayısından bağımsız olarak $O(V^2)$’dir.
• Komşuluk listesi yalnızca var olan kenarları saklar; bellek $O(V + E)$, komşu gezinmesi derece kadardır.
• Seyrek çizgelerde liste, yoğun çizgelerde matris uygundur; gerçek çizgelerin çoğu seyrektir.
• Kenar listesi gezinme için elverişsizdir ama tüm kenarlar üzerinde çalışan algoritmalar ve veri aktarımı için uygundur.
• Gezinme algoritmalarının maliyeti gösterime bağlıdır: listeyle $O(V+E)$, matrisle $O(V^2)$.

Sonraki Adım

Gösterim hazır olduğuna göre gezinmeye geçilebilir. Sonraki ders, bir başlangıç düğümünden başlayarak çizgeyi katman katman tarayan enine aramayı ve onun ağırlıksız en kısa yol problemini nasıl çözdüğünü ele alacak.