İçeriğe geç

Menü

Berk Akademi
Yorumlar Google yorumları Özel Ders Başvuru Ücretsiz ön görüşme Ana Sayfa

Graf Veri Yapısı Nasıl Gösterilir? Komşuluk Matrisi ve Listesi

graf-veri-yapisi-komsuluk-matrisi-ve-listesi
Bu yazıda neler var?
  1. Graf programda nasıl saklanır?
  2. Komşuluk matrisi nasıl kurulur ve sorgulanır?
  3. Komşuluk listesi sözlük ve listelerle nasıl tutulur?
  4. Bellek ve sorgu maliyeti hangi gösterimi belirler?
  5. Graf gösteriminde hangi hatalar sık yapılır?
  6. Sık Sorulan Sorular

Graf veri yapısı, düğümler arasındaki bağlantıları komşuluk matrisi veya komşuluk listesi kullanarak gösterebilir. İki gösterim de aynı ilişkileri tutar; temel fark, kullandıkları bellek miktarı ve bağlantı sorgularının hızıdır.

Bir graf, düğümlerden ve bu düğümleri birbirine bağlayan kenarlardan oluşur. Komşuluk matrisi iki boyutlu bir tabloyla çalışırken komşuluk listesi, her düğümün bağlı olduğu düğümleri liste veya sözlük içinde saklar.

Graf programda nasıl saklanır?

Graf programda saklanırken önce düğümlerin ve kenarların nasıl yorumlanacağı belirlenir. Yönlü grafta bir kenar tek yön taşır; A düğümünden B düğümüne bağlantı olması, B'den A'ya da bağlantı olduğu anlamına gelmez. Yönsüz grafta iki düğüm arasındaki ilişki karşılıklı kabul edilir.

Ağırlıklı grafta kenarlara mesafe, maliyet veya süre gibi bir değer eklenir. Örneğin iki şehir arasındaki bağlantı, yalnızca True bilgisiyle tutulabileceği gibi, örnek bir mesafe değeriyle de saklanabilir. Ağırlıksız graflarda kenarın varlığı önemlidir; ağırlıklı graflarda kenarın taşıdığı değer de hesaba katılır.

Big O gösterimi, girdinin büyümesiyle bir işlemin maliyetinin nasıl değiştiğini özetler. Graf gösteriminde V düğüm sayısını, E ise kenar sayısını ifade eder. Aynı graf, seçilen gösterime göre farklı bellek kullanımı ve sorgulama davranışı gösterebilir.

Sonraki örneklerde Ankara, Bursa, İzmir, Konya ve Muğla'dan oluşan beş şehirli bir ağ kullanılacak. Kodda yer alan şehir adları ve mesafe değerleri yalnızca veri yapısını öğretmek amacıyla seçilmiştir; gerçek ulaşım veya yol verisi olarak değerlendirilmemelidir.

Komşuluk matrisi nasıl kurulur ve sorgulanır?

Komşuluk matrisi nasıl kurulur ve sorgulanır?

Komşuluk matrisi, satırları ve sütunları düğümlere karşılık gelen iki boyutlu bir liste olarak kurulur. Bir hücre, satırdaki düğüm ile sütundaki düğüm arasında doğrudan bağlantı olup olmadığını veya varsa bu bağlantının ağırlığını taşır.

Aşağıdaki örnekte yokluk için None, ağırlıklı kenarlar için örnek mesafe değerleri kullanılmıştır. Graf yönsüz olduğu için bir kenar eklenirken hem matrix[a][b] hem de matrix[b][a] hücresi doldurulur.

cities = ["Ankara", "Bursa", "İzmir", "Konya", "Muğla"]
index = {city: i for i, city in enumerate(cities)}

matrix = [[None] * len(cities) for _ in cities]

def add_edge(city_a, city_b, distance):
    a = index[city_a]
    b = index[city_b]
    matrix[a][b] = distance
    matrix[b][a] = distance

add_edge("Ankara", "Bursa", 385)
add_edge("Ankara", "Konya", 265)
add_edge("Bursa", "İzmir", 330)
add_edge("İzmir", "Muğla", 215)

ankara = index["Ankara"]
izmir = index["İzmir"]

has_connection = matrix[ankara][index["Bursa"]] is not None
izmir_neighbors = [
    cities[i]
    for i, value in enumerate(matrix[izmir])
    if value is not None
]

print(has_connection)
print(izmir_neighbors)

Bu kodun çıktısı şöyledir:

True
['Bursa', 'Muğla']

İki düğüm arasında doğrudan bağlantı olup olmadığını kontrol etmek için ilgili hücrede is not None kullanılır. Bir şehrin komşularını bulmak için de o şehre karşılık gelen satır taranır ve değeri None olmayan sütunların adları alınır.

Ağırlıksız bir graf için hücrelerde True ve False değerleri tutulabilir. Ağırlıklı bir graf için hücreler mesafe veya maliyet gibi sayısal değerler taşıyabilir. Sıfırın gerçek bir ağırlık olarak kullanılabileceği durumlarda, bağlantı yokluğunu belirtmek için 0 yerine None seçmek daha güvenlidir; böylece sıfır değeri yanlışlıkla bağlantı yokmuş gibi yorumlanmaz.

Komşuluk listesi sözlük ve listelerle nasıl tutulur?

Komşuluk listesi sözlük ve listelerle nasıl tutulur?

Komşuluk listesi, her düğümü doğrudan bağlı olduğu düğümlerin listesiyle eşleştirir. Python'da şehir adlarını sözlük anahtarı, komşu şehir ve mesafe çiftlerini ise liste elemanı olarak tutabilirsin.

Aşağıdaki beş şehirli ağda adlar ve mesafeler öğretici amaçla seçilmiştir; gerçek ulaşım verisi olarak kullanılmamalıdır. kenar_ekle fonksiyonu, yönsüz kenarı iki şehrin listesine de ekler. Yönlü kenarda ise yalnızca kaynak şehrin listesi güncellenir.

graf = {
    "İzmir": [],
    "Bursa": [],
    "Muğla": [],
    "Ankara": [],
    "İstanbul": []
}

def kenar_ekle(kaynak, hedef, mesafe, yonlu=False):
    graf[kaynak].append((hedef, mesafe))
    if not yonlu:
        graf[hedef].append((kaynak, mesafe))

kenar_ekle("İzmir", "Bursa", 330)
kenar_ekle("İzmir", "Muğla", 210)
kenar_ekle("Bursa", "İstanbul", 150)
kenar_ekle("Ankara", "Bursa", 380, yonlu=True)

def komsulari_yazdir(sehir):
    for komsu, mesafe in graf[sehir]:
        print(f"{komsu}: {mesafe} km")

komsulari_yazdir("İzmir")

Beklenen çıktı:

Bursa: 330 km
Muğla: 210 km

Örnekte Ankara'dan Bursa'ya yönlü bir kenar vardır, ancak bu işlem Bursa'dan Ankara'ya dönüş kenarı oluşturmaz. İzmir ve Bursa arasındaki yönsüz kenar ise her iki şehrin komşuluk listesinde yer alır.

Ağırlıksız bir grafta liste elemanı olarak yalnızca komşu adlarını tutabilirsin. Ağırlıklı grafta ise örnekteki gibi (komşu, ağırlık) çiftleri, bağlantıyla birlikte mesafeyi de saklar.

Komşuluk matrisinde her düğüm çifti için bir hücre ayrılırken listede yalnızca mevcut bağlantılar tutulur. Bu nedenle olası bağlantılara göre az sayıda kenar içeren seyrek graflarda liste daha az yer kaplayabilir.

Bellek ve sorgu maliyeti hangi gösterimi belirler?

Gösterim seçimini grafın bağlantı yoğunluğu ve sık yapılacak işlemler birlikte belirler. Big O gösteriminde V düğüm sayısını, E kenar sayısını, d ise sorgulanan düğümün komşu sayısını ifade eder.

Gösterim Bellek maliyeti İki düğüm arasında kenar sorgusu Bir düğümün komşularını dolaşma Uygun kullanım durumu
Komşuluk matrisi O(V²) O(1) O(V) Çok bağlantılı graflar ve sık kenar sorguları
Komşuluk listesi O(V+E) O(d), temel listede arama O(d) Seyrek graflar ve komşuların sık dolaşılması

Matrisin ilgili hücresine erişerek iki düğüm arasında kenar bulunup bulunmadığını doğrudan sorgulayabilirsin. Temel komşuluk listesinde ise hedefi bulmak için kaynak düğümün listesini taraman gerekir. Komşuları dolaşırken matrisin ilgili satırı bütünüyle incelenir; listede ise mevcut komşular üzerinden geçilir.

Ağırlıkların hücrelerde saklandığı matriste bellek davranışı O(V²), komşu ve ağırlık çiftlerinin saklandığı listede ise O(V+E) olarak kalır. Gerçek bellek tüketimi kullanılan veri yapılarına ve tutulan değerlere de bağlıdır.

BFS ve DFS gibi dolaşmalarda, sıradaki düğümün komşularına erişme biçimi bu maliyet farkını etkiler. Dijkstra gibi ağırlıklardan yararlanan bir algoritmada ise her kenarın ağırlığı matris hücresinden veya listedeki komşu ve ağırlık çiftinden alınabilir; ayrıca algoritmanın ağırlıklara ilişkin koşullarına dikkat edilmelidir.

Graf gösteriminde hangi hatalar sık yapılır?

Graf gösteriminde en sık yapılan hatalar, bağlantı yönünü eksik tutmak, düğüm sırasını karıştırmak ve grafın yapısına uygun olmayan veri yapısını seçmektir. Yönsüz bir kenar iki taraflı kabul edildiği için A-B bağlantısı hem A'nın komşularında B'yi hem de B'nin komşularında A'yı göstermelidir.

Düğüm indeksleri de baştan belirlenmelidir. Python listeleri çoğunlukla 0'dan başladığı için bir düğümün 1'den başlayan etiketini doğrudan liste indeksi gibi kullanmak yanlış konuma erişmeye yol açabilir. Matris kullanıyorsan satır ve sütunların aynı düğüm sırasını izlemesi gerekir. Örneğin satırlarda A, B, C sırası kullanılırken sütunlarda B, A, C sırasına geçilirse matris teknik olarak çalışsa bile bağlantılar yanlış yorumlanır.

Ağırlıklı graflarda kenar yokluğunu gerçek bir ağırlık değeriyle karıştırmamak gerekir. Kullanılan modelde 0 geçerli bir ağırlıksa, kenar yokluğunu 0 ile göstermek iki durumu birbirinden ayıramaz. Bu nedenle None gibi ayrı bir değer kullanılabilir.

matris = [
    [None, 5, None],
    [5, None, 2],
    [None, 2, None]
]

print(matris[0][2])
print(matris[1][2])

Bu kodun çıktısı şöyledir:

None
2

İlk değer A ile C arasında kenar bulunmadığını, ikinci değer ise B ile C arasındaki kenarın ağırlığının 2 olduğunu gösterir. Komşuluk listelerinde de sözlükte bulunmayan bir düğüme doğrudan erişmek KeyError oluşturabilir. Düğümün graf içinde bulunup bulunmadığı kontrol edilmeli veya güvenli bir varsayılan değer kullanılmalıdır.

Çok sayıda düğüm içeren seyrek graflarda her olası düğüm çifti için matris hücresi ayırmak gereksiz bellek kullanımına neden olabilir. Böyle durumlarda yalnızca mevcut komşulukları tutan liste yapısı daha uygun olabilir. Yoğun graflarda ise matrisin düzenli yapısı doğrudan kenar sorgularını kolaylaştırabilir.

  1. Doğrudan kenar sorgusunun ne sıklıkta yapılacağını değerlendir.
  2. Grafın seyrek mi yoksa yoğun mu olduğunu belirle.
  3. Kenar ağırlığı varsa kenar yokluğunu hangi değerle göstereceğine karar ver.
  4. Düğüm indekslerinin 0'dan mı yoksa 1'den mi başlayacağını baştan sabitle.
  5. Küçük bir örnekte beklenen komşulukları ve çıktıları kontrol et.

Bu ölçütler, tek bir gösterimi her durumda seçmek yerine graf üzerinde yapılacak işlemlere göre karar vermeyi sağlar. Matris ve liste arasındaki tercih, verinin yapısı ile sorguların niteliği birlikte değerlendirilerek yapılmalıdır.

Sık Sorulan Sorular

Yönsüz grafta bir kenarı neden iki komşuluk yönüne eklemek gerekir?

Yönsüz grafta A ile B arasındaki bağlantı iki yönde de geçerli olduğu için A'nın komşuluklarında B, B'nin komşuluklarında A bulunmalıdır. Kenarı yalnızca bir tarafa eklemek grafı eksik ve hatalı gösterir.

Komşuluk matrisinde kenar yokluğunu neden 0 yerine None ile göstermek daha güvenli olabilir?

Kullanılan ağırlık modelinde 0 geçerli bir kenarsa, 0 değeri hem gerçek ağırlığı hem de kenar yokluğunu gösterebilir. None kullanmak bu iki durumu açıkça ayırır.

Seyrek graf için komşuluk listesi neden genellikle daha uygun bir bellek seçeneğidir?

Komşuluk listesi yalnızca gerçekten bulunan kenarları sakladığı için seyrek graflarda boş bağlantı alanları için yer ayırmaz. Bu yapı, düğüm sayısı yüksek ancak bağlantı sayısı görece düşük olduğunda belleği daha verimli kullanabilir.

Komşuluk matrisi ve komşuluk listesi arasında doğrudan kenar sorgusu nasıl farklılaşır?

Komşuluk matrisinde iki düğümün kesişim hücresine erişilerek doğrudan kontrol yapılır. Komşuluk listesinde ise bir düğümün komşuları arasındaki liste veya küme içinde hedef düğüm aranır.

Grafın yönünü, ağırlıklarını, düğüm sırasını ve beklenen sorguları baştan netleştirmek, seçilen gösterimin doğru kullanılmasını kolaylaştırır.

Bu içerik aradığın cevabı verdi mi?
Yanıtın, hangi yazıları geliştirmemiz gerektiğini anlamamıza yardımcı olur.
Bu içeriğin üretilmesinde yapay zeka araçlarından destek alınmıştır.

Bu konudan sonra ne okuyabilirsin?

Tüm yazılar

İlgili Eğitimler

Berk Keskin, yazılım geliştirici ve eğitmen
Yazar

Berk Keskin Kimdir?

Yazılıma 12 yaşında başladı; İzmir Ekonomi Üniversitesi'ni bölüm birincisi ve yüksek şeref öğrencisi olarak tamamladı. Bugün yalnızca eğitim vermekle kalmıyor, sektörde aktif olarak yazılım projeleri geliştiriyor ve gerçek dünya deneyimini birebir derslerine taşıyor. Ezberden uzak, mühendislik zihniyetini merkeze alan sürdürülebilir öğrenme sistemleri tasarlayarak sorgulayan, üreten ve problem çözebilen yeni nesil yazılımcılar yetiştiriyor.

Sektörel Deneyim & Projeler

  • Ticarify Entegrasyon Yazılım logosu CEO Ticarify Entegrasyon YazılımPazaryerleri ve e-ticaret sitelerine otomatik e-fatura kesimi, sipariş ve kargo takibi hizmetleri sunan e-Dönüşüm platformunun API mimarisini ve yazılım ekibini yönetmektedir.
  • Benim Düğünüm logosu CEO Benim DüğünümDijital etkinlik ve anı paylaşım platformu.
  • Siberdizayn logosu Yazılım Ekibi Lideri SiberdizaynYüksek anlık oyuncu trafiğine sahip oyun kontrol panelleri ve sunucu altyapıları geliştiren yazılım ekibine liderlik etmektedir.
  • MEDYOGRAFYA 360° Dijital Çözümler logosu Dijital Strateji Lideri MEDYOGRAFYA 360° Dijital ÇözümlerŞirketlerin dijital çözümlerde uzun vadede nasıl ilerlemesi gerektiği ve dijital dönüşüm süreçlerinin yönetilmesine destek olmaktadır.
  • İzmir Ekonomi Üniversitesi logosu Danışma Kurulu Üyesi İzmir Ekonomi ÜniversitesiMezun olduğu üniversitesinde, Bilgisayar Programcılığı bölümünün akademik müfredatını güncel sektör ihtiyaçlarına göre şekillendirmek adına Danışma Kurulu'nda görev almaktadır.
WhatsApp Hemen Ara