--- title: 'Çizge Gösterimleri' source: 'https://academia.sh/tr/kurslar/veri-yapilari/cizge-gosterimleri' course: 'Veri Yapıları' language: tr updated: '2026-08-17T18:07:54+00:00' license: 'CC BY-SA 4.0' --- # Çizge Gösterimleri Komşuluk matrisi ile komşuluk listesi, bellek ve işlem maliyetleri, seyreklik ölçütü ve kenar listesi. Ç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. ```python 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. ```python 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. ```python 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.